Симплекс-метод. Характеристика метода

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

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

В симплекс-методе можно выделить три основные компоненты:

1) Способ построения начального базисного решения.

2) Процедуру перехода от одного базисного решения к другому.

3) Признак оптимальности.

Неразрешимость задачи определяется по ходу работы алгоритма.

Этапы симплекс-метода:

1. Построение начального неотрицательного базисного решения.

2. Анализ оценок. При этом возможны три ситуации:

а) все оценки неотрицательны, следовательно, вычисления прекращаются, так как выполнился признак оптимальности.

б) имеются отрицательные оценки, но, по крайней мере, одной их них (например, Δ _j) соответствует вектор, для которого все коэффициенты разложения неположительны (" a_ij £ 0). В этом случае q не ограничено сверху и, как следует, критерий неограниченно возрастает. Решение прекращается.

в) для каждой отрицательной оценки есть a_ij > 0. Решение может быть улучшено выполнением 3 этапа.

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

Этапы 2 и 3 повторяются до выполнения одного из условий останова.

Модифицированный алгоритм симплекс-метода

Отличается от простого симплекс-метода тем, что основан на обратной матрице базиса.

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

5. Модели управления транспортными потоками.

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

Простейшая транспортная задача (Т-задача)

В общем случае исходными данными являются:

m – число пунктов отправления (ПО) или производства;

n – число пунктов назначения (ПН) или потребления;

C_ij – затраты на перевозку единицы груза из пункта i в пункт j, " ij;

a_i – количество груза в пункте i, " i (возможности ПО);

b_j – потребность в грузе в пункте j, " j.

Критерием задачи являются суммарные затраты на перевозку. Безотносительно к значениям a_i и b_j модель записывается в виде

Однако такая запись модели корректна только тогда, когда Напомним, что задача, в которой суммарные потребности равны суммарной возможности, то есть (1) называется сбалансированной или закрытой. Любая несбалансированная задача легко приводится к закрытой. Рассмотрим только сбалансированную задачу:

	(2)		(3)
	(4)	" Xij ³ 0.	(5)

Элементы модели:

– матрица перевозок;

– матрица транспортных затрат;

a=(a1, a2,..., am) – вектор возможностей ПО;

b=(b1, b2,..., bn) – вектор потребностей ПН.

Особенности рассматриваемой задачи:

- модель содержит две группы условий, размерность которых равна соответствующему числу ПО и ПН; число переменных равно произведению m ´ n;

- все коэффициенты при переменных в условиях (3), (4) равны единице;

- каждая переменная входит в условия ровно 2 раза, один и только один раз в группу (3) и также один раз в группу (4);

- задача имеет простые условия разрешимости, которые определяются следующей теоремой.

Теорема. Для разрешимости Т-задачи необходимо и достаточно, чтобы она была сбалансированной.

Замечание. Теорема справедлива при конечных значениях Сij.

Доказательство. Необходимость доказывается исходя из того, что задача (2)-(5) разрешима. В этом случае все условия задачи выполняются. Просуммируем условия (3) по i, а условия (4) по j: Так как левые части равенств равны, то равны и правые.

Достаточность. Задача линейного программирования всегда разрешима, если допустимое множество – выпуклый многогранник, то есть непустое и ограниченное. Ограниченность переменных снизу задана явно, а ограничение сверху следует из конечности всех a_i и b_j, больше которых переменные быть не могут. Следовательно, множество ограничено. Множество непустое. Для этого достаточно найти хотя бы одно допустимое решение. Одно из таких решений всегда можно построить, если задача сбалансирована, следующим образом: (6) Очевидно, что оно неотрицательно. Остается проверить выполнение основных условий задачи. Подставив (6) в левую часть(3), получим: Þ решение удовлетворяет условиям (3). Подставив первый вариант (6) в (4), также убеждаемся в выполнении этих условий:

. Таким образом, допустимое множество сбалансированной задачи непустое и ограниченное, а, значит, задача всегда разрешима. Число линейно-независимых уравнений или, иначе, ранг системы (3), (4) равен m+n- 1. Следовательно, такую размерность имеют базис и базисное решение Т-задачи.

Транспортная задача с ограниченными пропускными способностями (Td - задача)

Учет ограничений на пропускные возможности коммуникаций. В реальных условиях пропускные способности дорог, воздушных коридоров, линий связи и т.п. всегда ограничены сверху. Учет этих ограничений приводит Т_d-задаче. Ее модель имеет вид

	(7)		(8)
	(9)	0 £ Xij £ dij, " i, j,	(10)

где d_ij –пропускная способность коммуникации i j. В Т_d-задаче условие сбалансированности не является достаточным для разрешимости задачи. Более того, в число необходимых условий существования решения помимо его входят еще две группы условий, отражающих физическую реализуемость решения: (11) (12) Они требуют, чтобы суммарная пропускная способность коммуникаций, входящих в каждый ПН была не меньше объема поставок, а выходящих из ПО – не меньше количества вывозимого груза. Если хотя бы одно из них нарушается, задача заведомо неразрешима. Но и выполнение всех необходимых условий не гарантирует разрешимость Т_d-задачи.