Линейное программирование в примерах и задачах. Методические указания

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Восточно-Сибирский государственный технологический университет

И.В.Корытов С.С.Дашиева

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ в примерах и задачах

Симплекс-метод Метод искусственного базиса Двойственные задачи Решение двойственной задачи с использованием теорем двойственности Типовой расчет (задания из 20 вариантов)

Улан-Удэ 2002

Введение Пособие содержит материал, относящийся к основным вопросам темы «Линейное программирование». Здесь рассматривается только алгебраический подход к решению задач. Предполагается, что студент знаком с теоретическими сведениями, касающимися излагаемых вопросов, и умеет решать основную задачу линейного программирования геометрическим методом. Основным математическим аппаратом решаемых ниже задач являются элементарные преобразования матриц, применяемые в виде метода Жордана – Гаусса с выбором ведущего элемента. Пособие посвящено практическому решению задач. Ход решения построен с выделением этапов и шагов, снабженных необходимыми комментариями, и может одновременно служить образцом оформления при выполнении студентом самостоятельной работы. Разбираемые примеры подобраны в определенной последовательности по схеме: решение исходной задачи линейного программирования – составление условий двойственной задачи – решение двойственной задачи двумя способами. Метод искусственного базиса с точки зрения вычислительных процедур не отличается от стандартного симплекс-метода, дополнительные действия связаны с видоизменением целевой функции путем добавления специального слагаемого, называемого штрафной функцией. Смысл этих действий понятен из примера, поэтому метод искусственного базиса рассматривался не под отдельным заголовком, а в ходе решения одной из задач. Задания типового расчета составлены таким образом, что одна из взаимно двойственных задач решается обычным симплекс-методом, а другая – методом искусственного базиса. Пособие адресовано студентам третьего курса экономических специальностей. 2

Решение задачи линейного программирования симплекс-методом Пример 1. Решить задачу линейного программирования симплекс-методом, введя при необходимости искусственный базис. F = 3 x1 + 5 x2 → min ⎧2 x1 + 4 x2 ≥ 12 ⎪ 3 x + 2 x ≥ 10 ⎪ 1 2 ⎨ x ≤ 6 2 ⎪ ⎪⎩ x1 ≤ 5 x1 ≥ 0, x2 ≥ 0

Приведение условия к каноническому виду Так как система ограничений состоит из неравенств, для приведения условия к каноническому виду нужно ввести в каждое неравенство балансовые переменные x3 , x 4 , x5 , x 6 : ⎧2 x1 ⎪3x ⎪ 1 ⎨ ⎪ ⎪⎩ x1

+ 4 x2 + 2 x2 x2

− x3 − x4 + x5 + x6

= 12 = 10 = 6 = 5

x j ≥ 0, j = 1,K ,6 Матрица системы ограничений

3

⎛2 ⎜ ⎜3 ⎜0 ⎜ ⎜1 ⎝

4 −1 0 0 2 0 −1 0 1 0 0 1 0 0 0 0

0 12 ⎞ ⎟ 0 10 ⎟ 0 6⎟ ⎟ 1 5 ⎟⎠

F = 3x1 + 5 x 2 + M (22 − 5 x1 − 6 x6 + x3 + x 4 ) =

= (3 − 5M ) x1 + (5 − 6M ) x 2 + Mx3 + Mx 4 + 22 M .

не содержит в себе единичную матрицу, следовательно балансовые переменные не образуют базиса. Умножение на − 1 обеих частей первого и второго уравнений приведет к недопустимому базисному решению. Поэтому необходимо ввести в эти уравнения искусственные переменные r1 и r2 :

⎧2 x1 ⎪3x ⎪ 1 ⎨ ⎪ ⎪⎩ x1

+ 4 x2 + 2 x2 x2

− x3

+ r1 − x4

+ r2 + x5 + x6

= 12 = 10 = 6 = 5

x j ≥ 0, j = 1,K,6; r1 ≥ 0, r2 ≥ 0

Выражение искусственных переменных через свободные: r1 = 12 − 2 x1 − 4 x 2 + x3 , r2 = 10 − 3 x1 − 2 x 2 + x 4 .

Составление штрафной функции: M (r1 + r2 ) = M (12 − 2 x1 − 4 x2 + x3 + 10 − 3x1 − 2 x2 + x4 ) =

= M (22 − 5 x1 − 6 x6 + x3 + x4 ). В задаче минимизации штрафная функция вводится в целевую функцию со знаком «+»1: 1

Условие задачи с искусственным базисом в каноническом виде: F − (3 − 5M ) x1 − (5 − 6 M ) x 2 − Mx3 − Mx 4 = 22M

⎧2 x1 ⎪3x ⎪ 1 ⎨ ⎪ ⎪⎩ x1

+ 4 x2 + 2 x2 x2

− x3

+ r1 − x4

+ r2 + x5 + x6

= 12 = 10 = 6 = 5

x j ≥ 0, j = 1,K ,6; r1 ≥ 0, r2 ≥ 0

Расширенная матрица задачи линейного программирования: ⎛ 1 5M − 3 6 M − 5 − M − M 0 0 0 ⎜ −1 2 4 0 0 0 1 ⎜0 ⎜0 −1 0 0 0 3 2 0 ⎜ 0 1 0 0 1 0 0 ⎜0 ⎜0 1 0 0 0 0 1 0 ⎝

0 22M ⎞ ⎟ 0 12 ⎟ 1 10 ⎟ ⎟ 0 6⎟ 0 5 ⎟⎠

В матрице отделены сплошными линиями: столбец, соответствующий переменной F , строка коэффициентов целевой функции и столбец свободных членов. Пунктирной линией отделены столбцы единичной матрицы. Ранг расширенной матрицы rang = 5 , следовательно, количество базисных переменных равно пяти. Базисные переменные: F , x5 , x6 , r1 , r2 .

В задаче максимизации, соответственно, со знаком «–».

4

5

Свободные переменные: x1 , x 2 , x3 , x 4 . Шаг 1. Составление первой симплекс-таблицы В задаче с искусственным базисом первая симплекстаблица соответствует первому искусственному базисному решению.

Симплекс-таблица 1 БП

F

F r1

1

x1

x2

x3 x 4

5M-3 6M-5 -M -M

x5 x6

Реше r1 r2 ние Отношение

0

0

0

0

22M

0

2

4

-1

0

0

0

1

0

12

12:4=3

r2 x5

0

3

2

0

-1

0

0

0

1

10

10:2=5

0

0

1

0

0

1

0

0

0

6

6:1=6

x6

0

1

0

0

0

0

1

0

0

5

5:0 → ∞

Выбор включаемой в базис переменной: наибольший положительный коэффициент с 2 = 6 M − 5 при переменной x2 . Проверка критерия допустимости: среди оценочных отношений (последний столбец таблицы) встречаются конечные положительные, следовательно, возможен выбор исключаемой из базиса переменной. Выбор исключаемой переменной: среди оценочных отношений минимальным является отношение, соответствующее переменной r1 , которая и будет исключена из базиса на этом шаге. Ведущим элементом при пересчете будет элемент, стоящий на пересечении строки, соответствующей исключаемой переменной r1 (ведущей строки), и столбца, соответствующего включаемой переменной x 2 (ведущего столбца). В таблице ведущий элемент обведен рамкой.

Комментарий к симплекс-таблице 1.

Пересчет таблицы в матричной записи.

Решение (искусственное базисное) в 8-мерном пространстве X =(0,0,0,0,6,5,12,10). Решение в двумерном (по количеству исходных переменных в условии задачи) пространстве X =(0,0). Данная точка находится за пределами многоугольника решений. Значение целевой функции F (0,0)=22 M – «штрафное», так как точка не принадлежит многоугольнику решений. Проверка критерия оптимальности: задача на минимизацию, в строке целевой функции имеются положительные коэффициенты при свободных переменных x1 и x 2 , следовательно, оптимальное решение не достигнуто. Необходимо выбрать среди свободных включаемую в базис переменную.

Элементы ведущей строки делятся на ведущий элемент:

6

⎛ ⎜ 1 5M − 3 6 M − 5 − M − M 0 0 0 ⎜ 1 1 1 ⎜0 1 − 0 0 0 ⎜ 2 4 4 ⎜ 3 2 0 −1 0 0 0 ⎜0 ⎜ ⎜0 0 1 0 0 1 0 0 ⎜ ⎜ 1 0 0 0 0 1 0 ⎜0 ⎝

⎞ 0 22 M ⎟ ⎟ 0 3⎟ ⎟ ⎟ 1 10 ⎟ ⎟ 0 6⎟ ⎟ ⎟ 0 5⎟ ⎠

7

Далее выполняются элементарные преобразования над строками матрицы, в результате которых на месте ведущего столбца окажется столбец единичной матрицы: 1 1 5 3 5 ⎞ ⎛ 0 0 4M + 15 ⎟ M− −M 0 0 − M + ⎜ 1 2M − 2 2 4 2 4 ⎟ ⎜ 1 1 1 ⎜0 1 0 0 0 0 3⎟ − ⎟ ⎜ 2 4 4 ⎟ ⎜ 1 1 2 0 1 4⎟ −1 0 0 − ⎜0 2 2 ⎟ ⎜ 1 1 1 ⎜0 0 0 1 0 0 3⎟ − − ⎟ ⎜ 2 4 4 ⎟ ⎜ 1 0 0 0 0 1 0 0 5⎟ ⎜0 ⎠ ⎝

Базисные переменные: F , x 2 , x5 , x 6 , r2 . Свободные переменные: x1 , x3 , x 4 , r1 . Шаг 2. Составление следующей симплекс-таблицы Так как в базисе осталась еще одна искусственная переменная, то новая таблица соответствует второму искусственному базисному решению.

Симплекс-таблица 2 БП F

x1

F 1

2M −

x2 1 2

0

x3

x 4 x5 x6

1 5 M− -M 0 2 4 1 − 0 0 4

0

r1 −

3 5 M+ 2 4 1 4

x2 0

1 2

1

r2 0

2

0

1 2

-1

0

0

−

0

1 4

0

1

0

−

0

0

0

0

1

x5 0 x6 0 8

−

1 2

1

0

Отношеr2 Решение ние 0 4M + 15 0

3

1 2

1

4

1 4

0

3

0

5

0

3:

1 =6 2

4:2=2 3: −

1 <0 2

5:1=5

Комментарий к симплекс-таблице 2.

Решение (искусственное базисное) в 8-мерном пространстве X =(0,3,0,0,3,5,0,4). Решение в двумерном пространстве X =(0,3). Данная точка также находится за пределами многоугольника решений. Значение целевой функции F (0,3)=4 M +15 – «штрафное», так как точка не принадлежит многоугольнику решений. Проверка критерия оптимальности: задача на минимизацию, в строке целевой функции имеются положительные коэффициенты при свободных переменных x1 и x3 , следовательно, оптимальное решение не достигнуто. Необходимо выбрать среди свободных включаемую в базис переменную. Выбор включаемой в базис переменной: наибольший 1 положительный коэффициент с1 = 2M − при переменной 2 x1 . Проверка критерия допустимости: среди оценочных отношений (последний столбец таблицы) встречаются конечные положительные, следовательно, возможен выбор исключаемой из базиса переменной. Выбор исключаемой переменной: среди оценочных отношений минимальным является отношение, соответствующее переменной r2 , которая и будет исключена из базиса на этом шаге. Ведущим элементом при пересчете будет элемент, стоящий на пересечении ведущей строки, соответствующей исключаемой переменной r2 , и ведущего столбца, соответствующего включаемой переменной x1 . Пересчет таблицы в матричной записи.

9

Элементы ведущей строки делятся на ведущий элемент: 3 5 1 5 1 ⎞ ⎛ M− −M 0 0 − M + 0 4 M + 15 ⎟ 0 ⎜ 1 2M − 2 4 2 4 2 ⎟ ⎜ 1 1 1 ⎜0 − 0 3⎟ 1 0 0 0 ⎟ ⎜ 4 4 2 ⎟ ⎜ 1 1 1 1 − − 2⎟ 0 0 1 0 ⎜0 4 2 4 2 ⎟ ⎜ 1 1 1 ⎜0 − − 0 3⎟ 0 1 0 0 ⎟ ⎜ 4 4 2 ⎟ ⎜ 1 0 0 0 0 1 0 0 5⎟ ⎜0 ⎠ ⎝

Далее выполняются элементарные преобразования над строками матрицы, в результате которых на месте ведущего столбца окажется столбец единичной матрицы: ⎛ ⎜1 ⎜ ⎜0 ⎜ ⎜ ⎜0 ⎜ ⎜0 ⎜ ⎜ ⎜0 ⎝

9 1 − 8 4 3 1 − 8 4 1 1 − 4 2 3 1 − 8 4 1 1 − 4 2

9 1 ⎞ −M + 16 ⎟ 8 4 ⎟ 3 1 − 2⎟ ⎟ 8 4 ⎟ 1 1 − 2⎟ 4 2 ⎟ 3 1 − 4⎟ ⎟ 8 4 ⎟ 1 1 3⎟ − 4 2 ⎠

0 0 −

0 0 −M +

0 1

0 0

1 0 0 0 0 0

0 0 1 0 0

1

Базисные переменные: F , x1 , x 2 , x5 , x6 . Свободные переменные: x3 , x 4 , r1 , r2 .

10

Шаг 3. Составление очередной симплекс-таблицы Искусственных переменных в базисе нет, следовательно, новая таблица соответствует первому допустимому базисному решению.

Симплекс-таблица 3 БП

F x1 x 2

F 1

0

0

x2 0

0

1

x1 0

1

0

x5 0

0

0

x6 0

0

0

x3 9 8 3 − 8 1 4 3 8 1 − 4 −

x 4 x5 x6 1 4 1 4 1 − 2 1 4 1 2

−

0

0

0

0

0

0

1

0

0

1

r1 −M + 1 4 1 − 2 1 − 4 1 4

Решение

r2 9 8

−M + 1 4 1 2 1 4 1 − 2 −

1 4

16 2 2 4 3

Комментарий к симплекс-таблице 3.

Решение (допустимое базисное) в 8-мерном пространстве X =(2,2,0,0,4,3,0,0). Решение в двумерном пространстве X =(2,2). Данная точка является угловой точкой многоугольника решений. Значение целевой функции F (2,2)=16 свободно от «штрафа», так как точка принадлежит многоугольнику решений. Проверка критерия оптимальности: задача на минимизацию, в строке целевой функции все коэффициенты при свободных переменных отрицательны, следовательно, получено оптимальное решение. Таким образом, решение X =(2,2), при котором целевая функция достигает своего минимального значения F (2,2)=16, будет ответом в данной задаче. 11

Составление условия двойственной задачи Пример 2. Составить условие задачи, двойственной к данной. F = 3 x1 + 5 x 2 → min ⎧2 x1 + 4 x 2 ≥ 12 ⎪ 3 x + 2 x ≥ 10 ⎪ 1 2 ⎨ ≤ 6 x 2 ⎪ ⎪⎩ x1 ≤ 5 x1 ≥ 0, x 2 ≥ 0

Приведение условия к стандартному виду Поскольку в исходной задаче требуется найти минимум целевой функции, то ограничения в системе необходимо привести к неравенствам типа "≥" . F = 3 x1 + 5 x 2 → min ⎧ 2 x1 + 4 x 2 ≥ 12 ⎪ 3 x + 2 x ≥ 10 ⎪ 1 2 ⎨ − x ≥ −6 2 ⎪ ⎪⎩− x1 ≥ −5 x1 ≥ 0, x 2 ≥ 0

Работа с расширенными матрицами Расширенная матрица исходной задачи:

12

⎛ 3 5 F⎞ ⎜ ⎟ ⎜ 2 4 12 ⎟ ⎜ 3 2 10 ⎟ ⎜ ⎟ ⎜ 0 −1 − 6⎟ ⎜ − 1 0 − 5⎟ ⎝ ⎠ Матрица, транспонированная к матрице исходной задачи (расширенная матрица двойственной задачи): 0 − 1⎞ ⎛3 2 3 ⎜ ⎟ ⎜ 5 4 2 −1 0⎟ ⎜ Z 12 10 − 6 − 5 ⎟ ⎝ ⎠

Составление ограничений и целевой функции двойственной задачи Ограничения двойственной задачи (на основе первых двух строк расширенной матрицы): − y4 ⎧3 ≥ 2 y1 + 3 y 2 ⎨ ⎩5 ≥ 4 y1 + 2 y 2 − y 3

Целевая функция двойственной задачи (на основе последней строки расширенной матрицы): Z = 12 y1 + 10 y 2 − 6 y 3 − 5 y 4 → max Условие двойственной задачи Z = 12 y1 + 10 y 2 − 6 y 3 − 5 y 4 → max

− y4 ≤ 3 ⎧2 y1 + 3 y 2 ⎨ 2 y 2 − y3 ≤ 5 ⎩4 y1 y j ≥ 0, j = 1, K,4.

13

Z − 12 y1 − 10 y 2 + 6 y 3 + 5 y 4 = 0

Решение двойственной задачи симплексметодом

− y 4 + y5 = 3 ⎧2 y1 + 3 y 2 ⎨ + y6 = 5 2 y 2 − y3 ⎩4 y1 y j ≥ 0, j = 1, K,6.

Пример 3. Решить двойственную задачу, построенную в примере 2, симплекс-методом.

Z = 12 y1 + 10 y 2 − 6 y 3 − 5 y 4 → max

Расширенная матрица канонической формы двойственной задачи:

− y4 ≤ 3 ⎧2 y1 + 3 y 2 ⎨ ≤ 5 2 y 2 − y3 ⎩4 y1 y j ≥ 0, j = 1, K ,4. Приведение условия к каноническому виду Так как система ограничений состоит из неравенств, для приведения условия к каноническому виду нужно ввести в каждое неравенство балансовые переменные y 4 , y 5 :

− y 4 + y5 = 3 ⎧2 y1 + 3 y 2 ⎨ + y6 = 5 2 y 2 − y3 ⎩4 y1 y j ≥ 0, j = 1,K,6. Матрица системы ограничений ⎛ 2 3 0 − 1 1 0 3⎞ ⎜⎜ ⎟⎟ ⎝ 4 2 − 1 0 0 1 5⎠ содержит в себе единичную матрицу, следовательно, балансовые переменные образуют естественный базис. Условие задачи в каноническом виде:

14

⎛ 1 − 12 − 10 6 5 0 0 0 ⎞ ⎜ ⎟ 2 3 0 − 1 1 0 3⎟ ⎜0 ⎜0 4 2 − 1 0 0 1 5 ⎟⎠ ⎝

Ранг расширенной матрицы rang = 3 , следовательно, количество базисных переменных равно трем. Базисные переменные: Z , y 5 , y 6 . Свободные переменные: y1 , y 2 , y 3 , y 4 . Шаг 1. Составление первой симплекс-таблицы В задаче с естественным базисом первая симплекстаблица соответствует первому допустимому базисному решению.

БП

Z

y1

y2

y3

y4

y5

Z

1

-12

-10

6

5

0

y5

0

2

3

0

-1

1

y6

0

4

2

-1

0

0

Симплекс-таблица 1 y 6 Реше- Отношение ние 0 0 3 3:2= 0 3 2 5 5:4= 1 5 4 15

Комментарий к симплекс-таблице 1.

Решение (допустимое базисное) в 6-мерном пространстве Y =(0,0,0,0,3,5). Решение в 4-мерном (по количеству исходных переменных в условии двойственной задачи) пространстве Y =(0,0,0,0). Данная точка является угловой в многограннике решений. Значение целевой функции в начальной точке Z (0,0,0,0)=0. Проверка критерия оптимальности: задача на максимизацию, в строке целевой функции имеются отрицательные коэффициенты при свободных переменных y1 и y 2 , следовательно, оптимальное решение не достигнуто. Необходимо выбрать среди свободных включаемую в базис переменную. Выбор включаемой в базис переменной: наибольший по модулю отрицательный коэффициент b1 = −12 при переменной y1 . Проверка критерия допустимости: все оценочные отношения конечные положительные, следовательно, возможен выбор исключаемой из базиса переменной. Выбор исключаемой переменной: среди оценочных отношений минимальным является отношение, соответствующее переменной y 6 , которая и будет исключена из базиса на этом шаге. Ведущим элементом при пересчете будет элемент, стоящий на пересечении ведущей строки, соответствующей исключаемой переменной y 6 , и ведущего столбца, соответствующего включаемой переменной y1 . Пересчет таблицы в матричной записи.

Элементы ведущей строки делятся на ведущий элемент: 16

⎛ 6 5 0 0 ⎜ 1 − 12 − 10 ⎜ ⎜0 2 3 0 −1 1 0 ⎜ ⎜ 1 1 1 − 0 0 1 ⎜0 2 4 4 ⎝

⎞ 0⎟ ⎟ 3⎟ ⎟ 5⎟ ⎟ 4⎠

Далее выполняются элементарные преобразования над строками матрицы, ⎛ ⎜1 + 0 ⋅12 −12 +1⋅12 ⎜ ⎜ 0 + 0 ⋅ (−2) 2 +1⋅ ( −2) ⎜ ⎜ 1 ⎜0 ⎝

1 1 −10 + ⋅12 6 − ⋅12 5 + 0 ⋅12 0 + 0 ⋅12 2 4 1 1 3 + ⋅ (−2) 0 − ⋅ (−2) −1+ 0 ⋅ (−2) 1+ 0 ⋅ (−2) 2 4 1 1 − 0 0 2 4

1 0 + ⋅12 4 1 0 + ⋅ ( −2) 4 1 4

5 ⎞ 0 + ⋅12 ⎟ 4 ⎟ 5 3 + ⋅ (−2) ⎟ ⎟ 4 ⎟ 5 ⎟ 4 ⎠

в результате которых на месте ведущего столбца окажется столбец единичной матрицы: ⎛ ⎞ 3 5 0 3 15 ⎟ ⎜1 0 −4 ⎜ ⎟ 1 1 1⎟ ⎜0 0 −1 1 − 2 ⎜ 2 2 2⎟ ⎜ 1 1 1 5⎟ − 0 0 ⎜0 1 ⎟ 2 4 4 4⎠ ⎝

Базисные переменные: Z , y1 , y 5 . Свободные переменные: y 2 , y 3 , y 4 , y 6 . Шаг 2. Составление следующей симплекс-таблицы Новая таблица соответствует допустимому базисному решению.

17

БП

Z

y1

y2

y3

y4

y5

Z

1

0

-4

5

0

y5

0

0

2

-1

1

y1

0

1

1 2

3 1 2 1 − 4

0

0

Симплекс-таблица 2 y 6 Реше- Отношение ние 3 15 1 1 1 1 :2= − 2 2 2 4 1 5 5 1 5 : = 4 4 4 2 2

Комментарий к симплекс-таблице 2.

Решение (допустимое базисное) в 6-мерном простран5 1 стве Y =( ,0,0,0, ,0). 4 2 5 Решение в 4-мерном пространстве Y =( ,0,0,0). Дан4 ная точка является угловой в многограннике решений. Значение целевой функции в начальной точке 5 Z ( ,0,0,0)=15. 4 Проверка критерия оптимальности: задача на максимизацию, в строке целевой функции имеется отрицательный коэффициент при свободной переменной y 2 , следовательно, оптимальное решение не достигнуто. Необходимо выбрать среди свободных включаемую в базис переменную. Выбор включаемой в базис переменной: единственный отрицательный коэффициент b2 = −4 при переменной y 2 . Проверка критерия допустимости: все оценочные отношения конечные положительные, следовательно, возможен выбор исключаемой из базиса переменной. Выбор исключаемой переменной: среди оценочных отношений минимальным является отношение, соответствующее переменной y 5 , которая и будет исключена из базиса на этом шаге. 18

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

Элементы ведущей строки делятся на ведущий элемент: ⎞ ⎛ 3 5 0 3 15 ⎟ ⎜1 0 −4 ⎟ ⎜ 1 1 1 1 1⎟ ⎜0 0 1 − − ⎜ 4 2 2 4 4⎟ ⎜ 1 1 1 5⎟ − 0 0 ⎟ ⎜0 1 2 4 4 4⎠ ⎝ Далее выполняются элементарные преобразования над строками матрицы, ⎛ ⎜1 + 0 ⋅ 4 0 + 0⋅4 ⎜ ⎜ ⎜0 0 ⎜ ⎜ ⎛ 1⎞ ⎛ 1⎞ ⎜⎜ 0 + 0 ⋅ ⎜ − ⎟ 1 + 0 ⋅ ⎜ − ⎟ ⎝ 2⎠ ⎝ 2⎠ ⎝

1 1 3+ ⋅4 5− ⋅4 4 2 1 1 1 − 4 2 1 1 ⎛ 1⎞ ⎛ 1⎞ 1 1 ⎛ 1⎞ + 1⋅ ⎜ − ⎟ − + ⋅ ⎜ − ⎟ 0 − ⋅ ⎜ − ⎟ 2 2 ⎝ 2⎠ ⎝ 2⎠ 4 4 ⎝ 2⎠ − 4 + 1⋅ 4

1 0 + ⋅4 2 1 2 1 ⎛ 1⎞ 0 + ⋅⎜ − ⎟ 2 ⎝ 2⎠

1 3− ⋅4 4 1 − 4 1 1 ⎛ 1⎞ − ⋅⎜ − ⎟ 4 4 ⎝ 2⎠

⎞ 1 ⎟ 15 + ⋅ 4 4 ⎟ ⎟ 1 ⎟ 4 ⎟ 5 1 ⎛ 1 ⎞⎟ + ⋅⎜ − ⎟ ⎟ 4 4 ⎝ 2 ⎠ ⎟⎠

в результате которых на месте ведущего столбца окажется столбец единичной матрицы: ⎛ ⎞ 4 3 2 2 16 ⎟ ⎜1 0 0 ⎜ ⎟ 1 1 1 1 1⎟ ⎜0 0 1 − − ⎜ 4 2 2 4 4⎟ ⎜ 3 1 1 3 9⎟ − ⎜0 1 0 − ⎟ 8 4 4 8 8⎠ ⎝

19

Базисные переменные: Z , y1 , y 2 . Свободные переменные: y 3 , y 4 , y 5 , y 6 . Шаг 3. Составление следующей симплекс-таблицы Новая таблица соответствует допустимому базисному решению.

БП

Z

y1

y2

y3

Z

1

0

0

y2

0

0

1

y1

0

1

0

4 1 4 3 − 8

9 1 Таким образом, решение Y =( , ,0,0), при котором 8 4 целевая функция достигает своего максимального значения 9 1 Z ( , ,0,0)=16, будет ответом в данной задаче. 8 4

Симплекс-таблица 3 y 5 y 6 Решеy4 ние 3 2 2 16 1 1 1 1 − − 2 2 4 4 1 1 3 9 − 4 4 8 8

Комментарий к симплекс-таблице 3.

Решение (допустимое базисное) в 6-мерном простран9 1 стве Y =( , ,0,0,0,0). 8 4 9 1 Решение в 4-мерном пространстве Y =( , ,0,0). Дан8 4 ная точка является угловой в многограннике решений. Значение целевой функции в начальной точке 9 1 Z ( , ,0,0)=16. 8 4 Проверка критерия оптимальности: задача на максимизацию, в строке целевой функции все коэффициенты при свободных переменных положительны, следовательно, получено оптимальное решение.

20

21

Решение двойственной задачи с использованием теорем двойственности Пример 4. Решить двойственную задачу, построенную в примере 2, используя теоремы двойственности. Использование первой теоремы двойственности Информация для решения двойственной задачи с использованием теорем двойственности содержится в симплекс-таблице, полученной на последнем шаге решения исходной задачи: БП F

x1 x 2

F 1

0

0

x2 0

0

1

x1 0

1

0

x5 0

0

0

x6 0

0

0

x3 9 8 3 − 8 1 4 3 8 1 − 4 −

x 4 x5 x6 Решение 1 4 1 4 1 − 2 1 4 1 2 −

0

0

16

0

0

2

0

0

2

1

0

4

0

1

3

Таблица взята без столбцов, соответствующих искусственным переменным. Первая теорема двойственности. Если одна из двойственных задач имеет решение, то другая также имеет решение, причем оптимальные значения их целевых функций равны. Согласно первой теореме двойственности в данной задаче max Z = min F = 16 . 22

Использование теоремы о соответствии переменных исходной и двойственной задач Таблица соответствия переменных:

Переменные исходной задачи Основные Балансовые x1 x2 x3 x4 x5 y5 y6 y1 y2 y3 Балансовые Основные Переменные двойственной задачи

x6 y4

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

Компоненты оптимального решения исходной задачи x1 =2 x 2 =2 x 4 =0 x3 =0 x5 =4 x6 =3 y 5 =0 y 6 =0 y1 >0 y 2 >0 y 3 =0 y 4 =0 Знаки компонент оптимального решения двойственной задачи Использование второй теоремы двойственности Вторая теорема двойственности позволяет найти оставшиеся ненулевые значения компонент оптимального решения двойственной задачи. Вторая теорема двойственности. Компоненты оптимального решения одной из двойственных задач равны

23

абсолютным значениям коэффициентов при соответствующих переменных, находящихся в сроке целевой функции симплекс-таблицы, содержащей оптимальное решение другой задачи. Согласно второй теореме двойственности таблицу соответствия значений и знаков переменных можно дополнить значениями переменных y1 и y 2 :

мальное решение двойственной задачи, базисными будут принимающие ненулевое значение переменные y1 и y 2 . Строки в последней симплекс-таблице исходной задачи удобнее переставить таким образом, чтобы они следовали в порядке возрастания номеров соответствующих переменных двойственной задачи, а строка целевой функции находилась внизу таблицы:

Компоненты оптимального решения исходной задачи x1 =2 x 2 =2 x3 =0 x 4 =0 x5 =4 x6 =3 9 1 y 5 =0 y 6 =0 y 3 =0 y1 = y2 = y 4 =0 8 4 Компоненты оптимального решения двойственной задачи Эта таблица и содержит окончательное решение двой9 1 ственной задачи Y =( , ,0,0). 8 4 Таким образом, первая теорема двойственности дает оптимальное значение целевой функции, а вторая теорема двойственности – значения всех компонент оптимального плана двойственной задачи. Эти значения, как видно, совпадают со значениями, полученными с помощью симплексметода (см. пример 3). Восстановление последней симплекс-таблицы двойственной задачи Решение двойственной задачи уже получено, однако, его можно представить более наглядно, а именно в виде симплекс-таблицы, соответствующей оптимальному решению двойственной задачи. Согласно теореме и таблице соответствия переменных, а также условию, в симплекс-таблице, содержащей опти-

24

БП F

x1 x 2

y 3 x5 0

0

0

y 4 x6 0

0

0

y 5 x1 0

1

0

y6 x2 0

0

1

F 1

0

0

x 4 x5 x6 Решение

x3

1 4 1 2 1 − 2 1 4 1 − 4

3 8 1 − 4 1 4 3 − 8 9 − 8

1

0

4

0

1

3

0

0

2

0

0

2

0

0

16

Затем нужно подготовить бланк таблицы двойственной задачи с таким же порядком расположения строк и с учетом количества ограничений и, следовательно, базисных переменных:

x3 x4

БП

Z

y1

y2

y1 y2 Z

0 0 1

1 0 0

0 1 0

y3

y4

y5

y 6 Решение

Далее транспонируются «неединичные» столбцы измененной последней симплекс-таблицы исходной задачи: 25

БП

Z

y1

y2

y1

0

1

0

y2

0

0

1

Z

1

0

0

y3

3 8 1 − 4 4

y 6 Решение 1 1 3 9 − − 4 4 8 8 1 1 1 1 − 2 2 4 4 3 2 2 16 y4

y5

Для окончательного получения последней симплекстаблицы двойственной задачи остается умножить элементы столбцов y 3 , y 4 , y 5 и y 6 во всех строках, кроме строки целевой функции2, на (–1): БП

Z

y1

y2

y1

0

1

0

y2

0

0

1

Z

1

0

0

y3

3 8 1 4 4

−

y 6 Решение 1 3 9 1 − 4 4 8 8 1 1 1 1 − − 2 2 4 4 3 2 2 16 y4

y5

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

Типовой расчет «Основная задача линейного программирования» Задание для самостоятельной работы Дано условие задачи линейного программирования. Требуется: 1) Решить исходную задачу графическим методом. 2) Решить исходную задачу симплекс-методом, введя при необходимости искусственный базис. 3) Составить условие задачи, двойственной к данной. 4) Решить двойственную задачу симплекс-методом, введя при необходимости искусственный базис. 5) Решить двойственную задачу с использованием теорем двойственности. Индивидуальные условия (в 20 вариантах)

Вариант 1 F = x1 − 3x 2 → max

⎧ x1 ⎪ ⎨− x1 ⎪ x ⎩ 1

+ x2 + 2 x2 + x2

≥ 2 ≤ 4 ≤ 8

x1 ≥ 0, x 2 ≥ 0

Вариант 2 F = 2 x1 − x 2 → min

⎧ x1 ⎪ ⎨− x1 ⎪ x ⎩ 1

+ x2 + 2 x2 + 2 x2

≥ 4 ≤ 2 ≤ 10

x1 ≥ 0, x 2 ≥ 0

2

Коэффициенты в строке целевой функции умножаются на (–1) в двойственной задаче на минимизацию, в нашем примере двойственная задача – на максимизацию.

26

27

Вариант 3 F = x1 − 3x 2 → min

≥ 4 ≥ 2 ≤ 10

x1 ≥ 0, x 2 ≥ 0

Вариант 5 F = x1 − x 2 → max

Вариант 6 F = x1 + x 2 → max

Вариант 11 F = x1 + 3 x 2 → max

+ x2 + 2 x2 + x2

≤ 2 ≥ 8 ≤ 5

⎧ x1 ⎪ ⎨2 x1 ⎪ x ⎩ 1

⎧− 3x1 ⎪ ⎨ 3x1 ⎪ x 1 ⎩

+ 2 x2 + x2

≤ 2 ≥ 3 ≤ 3

x1 ≥ 0, x 2 ≥ 0

x1 ≥ 0, x 2 ≥ 0

Вариант 7 F = 3 x1 + x 2 → min

Вариант 8 F = x1 + 3x 2 → max

⎧ x1 + x 2 ≥ 2 ⎪ ⎨ x1 − x 2 ≤ 0 ⎪ x2 ≤ 4 ⎩ x1 ≥ 0, x 2 ≥ 0

28

+ x2 − x2 + 2 x2

x1 ≥ 0, x 2 ≥ 0

⎧− 2 x1 ⎪ ⎨ − x1 ⎪ x 1 ⎩

≤ 4 ≥ 0 ≥ 4

Вариант 9 F = x1 − x 2 → min

⎧ x1 + x 2 ≥ 3 ⎪ ⎨ x1 + x 2 ≤ 7 ⎪ x2 ≤ 4 ⎩ x1 ≥ 0, x 2 ≥ 0

⎧ x1 ⎪ ⎨3x1 ⎪ x ⎩ 1

− 4 x2 − x2 + x2

Вариант 4 F = 2 x1 − x 2 → max

⎧ x1 + 4 x 2 ⎪ + x2 ⎨ x1 ⎪ x2 ⎩ x1 ≥ 0, x 2

≥ 4 ≤ 6 ≤ 2 ≥0

⎧ ⎪ ⎨ x1 ⎪3x ⎩ 1

x2 + 2 x2 + x2

≤ 5 ≤ 12 ≤ 21

x1 ≥ 0, x 2 ≥ 0 Вариант 13 F = x1 + 4 x 2 → max

⎧ ⎪ ⎨ x1 ⎪3x ⎩ 1

x2 + x2 + x2

≤ 6 ≤ 8 ≤ 18

x1 ≥ 0, x 2 ≥ 0

Вариант 10 F = 3x1 − 4 x 2 → max

⎧ x1 − 2 x 2 ⎪ ⎨ x1 + 2 x 2 ⎪ x2 ⎩ x1 ≥ 0, x 2

≥ 2 ≥ 2 ≤ 3 ≥0

Вариант 12 F = 2 x1 + x 2 → max

⎧ x1 ⎪ ⎨3x1 ⎪ x ⎩ 1

+ 3x2 + 2 x2

≤ 21 ≤ 21 ≤ 5

x1 ≥ 0, x 2 ≥ 0 Вариант 14 F = x1 + x 2 → max

⎧ x1 ⎪ ⎨3x1 ⎪ x ⎩ 1

+ 2 x2 + 4 x2

≤ 12 ≤ 26 ≤ 6

x1 ≥ 0, x 2 ≥ 0

29

Вариант 15 F = x1 + 2 x 2 → max

⎧ ⎪ ⎨3x1 ⎪3x ⎩ 1

x2 + 2 x2 + x2

≤ 6 ≤ 21 ≤ 18

⎧ x1 ⎪ ⎨2 x1 ⎪ x ⎩ 1

+ 3x2 + x2

≤ 21 ≤ 12 ≤ 5

x1 ≥ 0, x 2 ≥ 0

x1 ≥ 0, x 2 ≥ 0

Вариант 17 F = x1 + 2 x 2 → max

Вариант 18 F = 4 x1 + x 2 → max

⎧ ⎪ ⎨2 x1 ⎪3x ⎩ 1

x2 + 3x2 + x2

≤ 5 ≤ 21 ≤ 21

x1 ≥ 0, x 2 ≥ 0 Вариант 19 F = x1 + x 2 → max

⎧ ⎪ ⎨4 x1 ⎪2 x ⎩ 1

x2 + 3x2 + x2

≤ 6 ≤ 26 ≤ 12

x1 ≥ 0, x 2 ≥ 0

30

Вариант 16 F = 3 x1 + x 2 → max

⎧ x1 ⎪ ⎨ x1 ⎪x ⎩ 1

+ 3x2 + x2

≤ 18 ≤ 8 ≤ 6

x1 ≥ 0, x 2 ≥ 0 Вариант 20 F = 2 x1 + x 2 → max

⎧ x1 ⎪ ⎨2 x1 ⎪ x ⎩ 1

+ 3x2 + 3x2

Литература

1. Вентцель Е.С. Исследование операций. – М.: Советское радио, 1972. 2. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в примерах и задачах. В 2-х ч. Ч.2: Учеб. пособие для втузов. – М.: Высшая школа, 1999. 3. Исследование операций в экономике / Н.Ш. Кремер, Б.А.Путко и др.; под ред. Н.Ш.Кремера. – М.: Банки и биржи, ЮНИТИ, 1997. 4. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. – М.: Высшая школа, 1986. 5. Сборник задач по математике для втузов. Ч.4. Методы оптимизации. Уравнения в частных производных. Интегральные уравнения / Вуколов Э.А., Ефимов А.В. и др.; под ред. А.В.Ефимова. – М.: Наука, 1990. 6. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике: Учебник: В 2-х ч. Ч.1. – М.: Финансы и статистика, 1999.

≤ 18 ≤ 21 ≤ 6

x1 ≥ 0, x 2 ≥ 0

31