2х, + Зх2 < 5, х х2>0.

c) Минимизировать г = 6х, + Зх2 при ограничениях

6х, - Зх2 + х3 > 2, Зх, + 4х2 + х3 > 5, х х2, х3>0.

d) Максимизировать z = х, + х2 при ограничениях

2х, + х2= 5, Зх,-х2 = 6,

х х2 - свободные переменные.

5. Вернитесь к задаче из примера 4.1.1. Применение симплекс-метода к прямой задаче ЛП, записанной в стандартной форме, требует введения искусственной переменной во второе ограничение для получения начального базисного решения. Покажите, что введение искусственной переменной не влияет на построение двойственной задачи, поскольку искусственная переменная прямой задачи порождает избыточное ограничение двойственной задачи.

6. Истинны или ложны следующие утверждения?

a) Задача, двойственная к двойственной, совпадает с исходной прямой задачей.

b) Если в прямой задаче есть ограничение в виде равенства, то соответствующая переменная двойственной задачи обязательно будет свободной.

c) Если в прямой задаче ограничение имеет вид неравенства типа < , то соответствующая переменная в двойственной задаче будет неотрицательной (неположительной), в зависимости от того, следует в прямой задаче максимизировать или минимизировать целевую функцию.

d) Если в прямой задаче ограничение является неравенством типа > , то соответствующая переменная в двойственной задаче будет неотрицательной (неположительной), в зависимости от того, следует в прямой задаче минимизировать или максимизировать целевую функцию.

e) Свободная переменная прямой задачи порождает в двойственной задаче ограничение в виде равенства.

7. В следующей таблице приведены правила построения двойственных задач, которые часто приводятся в литературе по исследованию операций и линейному программированию. Покажите, что эти правила являются частными случаями общих правил, приведенных в табл. 4.2.

4.2. СООТНОШЕНИЯ МЕЖДУ ПРЯМОЙ И ДВОЙСТВЕННОЙ ЗАДАЧАМИ

Изменение коэффициентов целевой функции и ограничений задачи ЛП влияет на оптимальность и допустимость текущего оптимального решения. Поэтому необходимо выяснить, как вычисления в симплекс-методе зависят от изменений коэффициентов исходной задачи. В частности, следует выяснить, как от этих изменений зависят оптимальность и допустимость решения, представленного в виде симплекс-таблицы.

Наиболее компактный способ записи вычислений, производимых при симплекс-методе, заключается в использовании матриц. Для этого в начале данного раздела приведем краткий обзор действий над матрицами, а затем рассмотрим соотношение между оптимальными решениями прямой и двойственной задач.

4.2.1. Обзор простых матричных операций

Нам необходимы только три элементарные матричные операции: умножение вектор-строки на матрицу, умножение матрицы на вектор-столбец и умножение скаляра (числа) на матрицу. Для удобства мы сформулируем определение этих операций, а также некоторые другие основополагающие определения.1

1. Матрица А порядка тхп - это прямоугольный массив элементов с т строками и п столбцами.

2. Вектор-строка V размерности п - матрица порядка 1 х п.

3. Вектор-столбец Р размерности т - матрица порядка mxl.

Эти определения математически можно представить следующим образом.

Теперь определим три матричные операции умножения.

1. Умножение вектор-строки V на матрицу А: V х А. Эта операция определена только тогда, когда количество элементов в вектор-строке V равно числу строк в матрице А.

Например,

(11,22,33) 3 4

ч5 6)

VxA = Xv £vyi,2,...,£v,a

= (1x11 + 3x22 + 5x33, 2x11+4x22 + 6x33) = (242,308).

2. Умножение матрицы А на вектор-столбец Р: А х Р. Эта операция определена только тогда, когда количество столбцов матрицы А равно количеству элементов вектор-столбца Р.

1 В приложении А приведен более полный обзор теории матриц.

АхР =

Например,

1 3 5

2 4 6

11x1 + 22x3 + 33x5 11x2 + 22x4 + 33x6

242 308

Умножение скаляра на матрицу. При умножении скаляра (константы) а на матрицу А, ссА, получаем матрицу порядка т х п, у которой (i, ;)-й элемент равен aatj. Например, для а = 10 имеем

Л 2 Ъ\ (10 20 301 (10)

4 5 6) {40 50 60

В общем случае ссА = Аа. Этим же свойством обладает операция умножения вектора на скаляр: aV = Va и aP = Pa.

УПРАЖНЕНИЯ 4.2.1

1. Даны следующие матрицы.

fl 4

V,-(ll,22), V2 = (-1,-2,-3).

В каждом из ниже перечисленных примеров укажите, допустима ли такая матричная операция, и если допустима, вычислите ее результат.

a) AV,.

b) АР,.

c) АР2.

d) V,A.

e) V2A. О Р,Р2. g) V.P..

4.2.2. Структура симплекс-таблицы

В главе 3 мы ввели стандартную форму для симплекс-таблиц. Такой формат симплекс-таблиц будет использоваться и в этой главе.

На рис. 4.1 показано схематическое представление структуры начальной и общей симплекс-таблиц. В начальной таблице коэффициенты ограничений под базисными переменными образуют единичную матрицу (в единичной матрице все ко-