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.
Эти значения соответственно равны 6/i и 21/4- Следовательно, исключению подлежит строка р(4>.Сектор В составляет р<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.
Два вектора ? q J и ? ^ J линейно независимы; точки (1, 0) и (0, 1) образуют^ базис двумерного пространства. Любую точку (xlt х2) можно представить в виде линейной их комбинации. Показать, что эта комбинация отыскивается с помощью следующего уравнения: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].
Еще по теме 15.9. РЕШЕНИЕ СИМПЛЕКСНЫМ МЕТОДОМ ПРОСТОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ:
- ГЛАВА 15 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
- 15.1. ПРОСТОЙ ПРИМЕР ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- 15.2. ПРОСТОЙ ПРИМЕР: ДВОЙСТВЕННАЯ ЗАДАЧА
- 15.3. ПРИВЕДЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К РЕШЕНИЮ ИГРЫ
- 15.4. ОБЩАЯ ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- 15.5. ЭКВИВАЛЕНТНОСТЬ ОБЩИХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИГРЫ С ДВУМЯ УЧАСТНИКАМИ И НУЛЕВОЙ СУММОЙ
- 15.6. ПРЕОБРАЗОВАНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ ОПЕРАЦИЙ
- 15.8. СИМПЛЕКСНЫЙ МЕТОД
- 15.9. РЕШЕНИЕ СИМПЛЕКСНЫМ МЕТОДОМ ПРОСТОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- 16.3. ПРЕДСТАВЛЕНИЕ ОТКРЫТОЙ СИСТЕМЫ ЛЕОНТЬЕВА В ВИДЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРОИЗВОДСТВЕННЫХ ОТРАСЛЕЙ
- 17.3. ПРЕДЕЛЬНЫЙ АНАЛИЗ И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ДЕЯТЕЛЬНОСТИ ФИРМЫ
- 17.5. ДВЕ ИЛЛЮСТРАТИВНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ