15.9. РЕШЕНИЕ СИМПЛЕКСНЫМ МЕТОДОМ ПРОСТОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Требуется при неотрицательных значениях ^ и ?2 максимизировать выражение

С = 3?х + = max,

при условии

2|1 + 4|2<21.

Чтобы применить симплексный метод, необходимо привести задачу к канонической форме (см. 15.9), для чего введем две дополняющие переменные. Тогда число переменных увеличится до четырех: k1 = 1j)1y А;2 = ?2, причем к3 и — дополняющие переменные. В новой задаче требуется отыскать неотрицательные Xs (s = 1, 2, 3, 4), максимизирующие выражение

Z = + 4 Х2 = max

Пространство решений является четырехмерным и содержит точки

% = A/2j ^з» А/4),

являющиеся возможными решениями задачи. В этом же пространстве расположена также заданная точка с = (3, 4, 0, 0), которая определяет максимизируемую функцию z.

Все допустимые решения І,, удовлетворяющие двум ограничивающим уравнениям, образуют в четырехмерном пространстве выпуклое множество Г. В качестве исходного допустимого решения необходимо выбрать некоторую экстремальную точку множества Г, имеющую два положительных и два нулевых веса. В качестве такого решения удобно взять % = (0, 0, 6, 21), которая несомненно удовлетворяет поставленным условиям; точки р(3) = [і] и р(4> = имеющие положительные веса, линейно независимы.

Теперь построим шаг за шагом следующую симплексную таблицу. І p(!) P<2> p(3) P<4> C8 3 4 0 0 р(3) 0 6 1 1 1 0 р(4) 0 21 2 4 0 l А 0 0 0 0 CS ZS 3 4 0 0 Р(3) 0 3 4

1

2 0 1 1

4 В Р(2) 4 21 4 1

2 1 0 1

4 2 4 0 1 cs zs 1 0 0 -1 p(1) 3 3 2 1 0 2 2 p(2) 4 9 2 0 1 -1 1

2 С 1

2 3 4 2 CS zs 0 0 -2 1

2 Рассмотрим сектор А, то есть первый сектор таблицы, являющийся исходным допустимым решением. Первые две строки соответствуют точкам (здесь р(3> и р(4)), имеющим положительные веса в X = (0, 0, 6, 21); эти положительные веса проставлены в столбце X. Остальные четыре столбца соответствуют точкам р*1), р(2\ р(3> и р<4>. Против этих строк и столбцов указана соответствующая величина с = (3, 4, 0, 0). Важнейшей частью сектора А являются элементы двух строк р<3> и р<4> и четырех столбцов р^1), р<2>, р<3) и р<4>. Это — коэффициенты xrs уравнения (4) раздела 15.8. Они показывают, каким образом точка, изображаемая каждым из столбцов, представляется линейной комбинацией выбранного нами базиса р(3) и р<4>. Например,

Р(1) = ^ЗІР(3) + ^4ІР(4)»

или

Ш=Чо]+2х[?]-

По сути дела это — элементы заданной матрицы задачи (см. упражнение 1). В остальных двух строках сектора А проставлены вычисленные в соответствии с уравнением (6) раздела 15.8 значения: во-первых, выражения

2s = C3X3S + (5=1, 2, 3, 4)

и, во-вторых, cs — zs.

Чтобы перейти к сектору В, заменим в строках одно из р<3> и р<4> на одно из р^> и р<2>. Чтобы выбрать необходимый вариант замены: 1)

найдем наибольшее положительное значение (cs — rs); оно равно 4; следовательно, включению подлежит р<2>; 2)

на основе столбца р(2> найдем наименьшее из значений 0 (то есть 13/я32 или kjxi2) для положительных значений xrs.

Сектор В составляет р<3> и р<2>, новая пара линейно независимых точек, имеющих положительные веса в новом допустимом решении Элементы % определяются на основе уравнений 7 раздела 15.8; здесь % = (0,21/4> 3/4, 0). Положительные веса проставлены в столбце X сектора В. Затем находим коэффициенты xrs уравнения (4) раздела 15.8 и проставляем их в таблицу. Например,

Р(1) = *ЗІР(3) + *2ІР(2\

или

[гЬ^оЬ^і]-

Этому уравнению удовлетворяют значения х31 = 1/2, х21 = 1/2 (см. упражнение 2). Затем тем же методом, как и раньше, вычисляем значения элементов строк zs и с6 — zs.

Сектор С является результатом дальнейшего применения того же процесса. Пару точек р<3) и р<2\ являвшуюся базисом в решении В, заменяем новым базисом р(1> и р<2>. Сначала включаем р<4> на основе наибольшего положительного значения (cs—zs) в секторе В, а по сути дела единственного {cs — zs), оставшегося положительным. Затем исключаем р<3) на основе наименьшего из двух значений 0 = к3/х31 = 3/4 : 1/2 и 0 = Я2/ж21 = 21/4 : 1/2. Следовательно, 0 = 3/2, и на основе уравнения (7) раздела 15.8 вычисляем новую величину % = (3/2, 9/2, 0, 0). Остальные элементы сектора С получаются тем же методом, что и ранее.

Мы закончили решение, так как все (cs — zs) < 0, и получен конечный максимум выражения z. Максимальное допустимое решение есть % = (3/2, 9/2, 0, 0), при котором

z = + 4Х2 = 22 у .

465

30 Г. Аллеи

Это есть решение, полученное в разделе 15.2, а именно: ^ = 3/2, = 9/2 и ? = 221/а. Следует отметить, что задача, двойственная рассмотренной, то есть задача питания (см. 15.1), имеет решение, которое можно получить из симплексной таблицы. Это решение представляют элементы последней строки (с3 — zs), взятые с обратным знаком, после того как основные и дополняющие переменные обменены местами. Для этой задачи h — (2,х/2, 0, 0), то есть хг = 2, х2 = 1/2, откуда следует z = 221/2.

Задачи и упражнения

1.

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

базиса в предыдущей задаче. Примем за базис векторы ? q J и ? ^ J • Любая точка

(хІ9 хг) является их линейной комбинацией:

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

і _ Iі і _ 1

Лі — Хі — x2t л2— х2- 3.

Решить задачу питания (см. 15.1) непосредственно симплексным методом. Тем самым получить решение и ее двойственной задачи. Сверить этот результат с непосредственным решением указанной двойственной задачи. 4.

Решить симплексным методом модифицированные задачи питания — упражнение 5 раздела 15.1 и упражнение 4 раздела 15.2. Сверить результаты с решениями соответствующих задач из теории игр (упражнение 3 раздела 15.3). 5.

В транспортной задаче (см. упражнение 7 раздела 15.1) показать, что пять заданных точек в двумерном пространстве условий суть:

110 0 6,

[рау,р<з.р>]=[1 о J J

Сколько пар здесь линейно независимых и сколько линейно зависимых? 6.

Рассмотрим частный случай транспортной задачи (см. упражнение] 7 раздела 15.1):

Минимизировать выражение

1

z = xl+-^-(x2+x з)

при условии х\ + а?2 = Ю, х\ + а?3=20.

Показать непосредственным расчетом, что 2 = 15 для любых допустимых значений я?!, х2 и х3. Попытаться решить задачу: а) графически, б) на основе решения соответствующей игровой задачи, в) симплексным методом. Рассмотреть также двойственную задачу. Разъяснить проделанные операции и истолковать задачу с точки зрения необходимой численности судов для перевозки и продолжительности различных рейсов. 7.

В транспортной задаче (см. упражнение 8 раздела 15.1) рассмотрим частный случай, для которого количества грузов, перевезенных между портами, и стоимости перевозки единицы груза соответственно представляются следуїощими матрицами:

Г*п *1. 2 1

Ui ю и Г^ ; j L~6 6 j~12J 15 4J

Показать, что в этой задаче требуется минимизировать линейную функцию четырех неизвестных при условии соблюдения трех ограничивающих линейных уравнений. Каковы в этом случае результаты применения симплексного метода? Сравнить с результатом предыдущей задачи. Более общий анализ см. в статье Данцига (гл. XXIII) в сборнике под редакцией Купманса [9].