Алгоритм симплекс-метода

1. Заполняем симплекс таблицу по данным задачи в каноническом виде.

2. Если выполнено условие оптимальности, то базисный план задачи оптимален.

3. Если выполняется условие неограниченности целевой функции, то задача не имеет решения.

4. Выбираем направляющий столбец по S по наименьшему или наибольшему по модулю положительному (отрицательному) элементу строки оценок для задачи минимизации (максимизации).

5. Составляем отношения положительных элементов столбца свободных членов b к соответствующим положительным элементам направляющего столбца. Среди них выбираем наименьшее, т.е. если ; j=s , то r – направляющая строка, и элемент a_rs - это генеральный или ключевой элемент на данном шаге.

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

1. Элементы направляющей строки умножаются на 1/a_rs

2. Все остальные элементы пересчитываются по правилу прямоугольника

7. Возвращаемся к пункту 2.

Теоремы.

1. Если все оценки некоторого базиса опорного решения задачи минимизации (максимизации) являются неположительными (неотрицательными), то это опорное решение является оптимальным, причем С_о=min f (С_о=max f ) (признак оптимальности).

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

Замечание.

1. Любую задачу максимизации можно свести к задаче минимизации, умножив целевую функцию на (-1), и наоборот.

2. При заполнении симплекс таблицы нужно обратить внимание на строку оценок: С₀ берется со своим знаком, а коэффициенты С_j с противоположным из целевой функции

Транспортная задача

Частный случай ЗЛП или частный случай задачи оптимизации сетей. Применяется при решении плановых задач выбора маршрутов перевозок. В общем виде формулируется следующим образом. Пусть рассмотрено m различных поставщиков (пунктов отправления) P_{i ,} располагающих некоторой однородной продукций соответственно в количествах a_i i=1,m и рассматривается отправление этой продукции в n пунктов потребления Q_j , потребности которых равны b_j cсоответственно. Известны тарифы перевозок этой продукции из пункта P_i в пункт Q_j (затраты на перевозку единицы груза) C_ij. Требуется составить такой план перевозок чтобы общая стоимость затрат была минимальной. К этой задаче возможно дополнение об ограничениях по пропускным способностям, о существовании промежуточных пунктов перезагрузки, источников и стоков груза. Математическая модель этой задачи имеет вид:

X_ij – количество едениц груза из i в j пункт.

ƒ= →min

x_ij≥0; Чаще всего ∑a_i=∑b_j

Учитывая, что эта задача является частным случаем ЗЛП, рассматриваются специальные способы решения этих задач.

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

Qj Pi	Q1	Q2	…	Qn	Запасы
P1	X11 c11	X12 c12	…	X1n c1n	a1
P2	X21 c21	X22 c22	…	X2n c2n	a2
…	…	…	…	…	…
Pm	Xm1 cm1	Xm2 cm2	…	Xmn cmn	am
Потребность	b1	b2	…	bn

Транспортная задача имеет решение т.к ∑a_i=∑b_j (закрытая модель).

Если ∑a_i < ∑b_j , то вводят фиктивный пункт производства и не все пункты в оптимальном решении будут удовлетворены в потребности.

Если ∑a_i>∑b_{j ,} то не все запасы будут вывезены из пунктов производства, в решении вводят фиктивный пункт потребления. Заметим, что объем продукции в фиктивном пункте равен разности │∑a_i -∑b_j│.

Циклом в транспортной таблице называют замкнутую ломаную линию, удовлетворяющую следующим условиям:

1. Все вершины ломаной находятся в клетках транспортной таблицы.

2. Ребра расположены по строкам или столбцам, но не диагоналям.

3. К каждой вершине подходят 2 ребра: одно - по строке, другое - по столбцу транспортной таблицы.

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

Теорема:

Допустимое решение транспортной задачи является опорным, т.и.т.т.к. набор заполненных клеток ацикличен, т.е в него входит m+n-1 клетка.

Определение. Потенциалом опорного решения α транспортной задачи называют числа U_i i=1,m; V_j j=1,n такие что U_i+V_j=C_ij – тариф заполненной клетки.

Теорема:

Достаточное условие оптимальности опорного решения. Если для всех незаполненных клеток (i,j) U_i+V_j=C_ij, где U_i и V_j - потенциалы опорного решения α, тогда это опорное решение является оптимальным.