Решение линейной распределительной задачи симплекс-методом.

Симплекс-метод является наиболее распространенным общим методом линейного программирования. Метод реализует направленный перебор допустимых базисных решений по соответствующим им крайним точкам выпуклого многогранника допустимых решений.

Основная задача линейного программирования (ЛП) имеет следующий в рід (2.6)-(2.7):

пррі огранріченрїях:

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

Рассмотрим эту задачу на конкретном примере.

Пусть имеются заявки 3-х типов — А, В и С, которые проходят обслуживание на приборах 4-х типов. Известно время прохождения заявки каждого типа на каждом приборе. Известен фонд времени каждого прибора, известна прибыль от обслуживания заявки каждого типа. Необходимо определить оптимальное количество обслуживаемых заявок каждого типа.

Исходные данные задачи занесены в табл. 2.6.

Таблица 2.6

Введя дополнительные переменные, получим основную задачу ЛП для решения.

F = 0 — (— 10.ХД — 14x9 — 12жз),

тц = 120 — (2т і + 4x9 + 5жз),

ж5 = 280 — (х\ + 8x9 + блд),

xq = 240 — (7х\ + 4x9 + 5т*з),

Xj = 350 — (4.гд + 6x9 + 7х3).

Здесь базисные переменные хц,..., xj имеют смысл неисполь- зованного ресурса. Заполняем симплекс-таблицу 2.7. Задача

решается в 2 этапа:

Таблица 2.7

• получение опорного плана;

• получение оптимального плана.

Если столбец свободных членов bj положительный, то имеем опорный план. Если в последней строке (для критерия F) нет отрицательных элементов, то имеем оптимальный план. В данном конкретном случае имеем опорный план.

Построение оптимального плана.

Находим любой из отрицательных элементов в последней строке, например (—12). Столбец, в котором расположен этот элемент, называется разрешающим столбцом. Для разрешающего столбца найдем отношение каждой строки, за исключением последней, к элементу столбца. Среди этих отношений находим минимальное положительное число. Строка, в которой расположен этот элемент, называется разрешающей строкой. Элемент Srk (т — номер строки, к — номер столбца) на пересечении разрешающей строки и разрешающего столбца называется разрешающим элементом.

Преобразуем таблицу по следующим правилам.

1. Для разрешающего элемента

2. Для всех элементов г-й строки, кроме разрешающего элемента.

3. Для всех элементов fc-ro столбца, кроме разрешающего элемента,

4. Для всех остальных элементов таблицы

5. Необходимо выполнить обмен переменных, находящихся при разрешающем столбце и разрешающей строке, — в данном случае это жз, щ (табл. 2.8).

Таблица 2.8

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

Последующие этапы отражены в соответствующих симплекс- таблицах 2.9 и 2.10.

Таблица 2.9

Таблица 2.10

Выпишем оптимальное решение из последней таблицы: ж 9 = 18, ж 5 = 112, х\ = 24, ж 7 = 156,

F = 492, же = жз = Ж4 = 0.

Таким образом, заявки 3-го типа при оптимальном плане не обслуживаются. Кроме того, остаются неиспользованными 112 единиц ресурса прибора второго типа и 156 единиц ресурса прибора четвертого типа.

2.5.1.