20. Симплекс-метод решения злп. Построение начальной симплекс-таблицы.

Симплексный метод применим к решению любой задачи линейного программирования. Из геометрического смысла задачи линейного программирования следует, что для ее решения необходимо вычислить координаты всех вершин многогранника ограничений и значения линейной формы в них. Решение задачи симплексным методом включает в себя два этапа. Первый состоит в нахождении одной произвольной вершины многогранника ограничений, координаты которого определяют начальный опорный план . Второй этап состоит в последовательном упорядоченном переходе от одной вершины многогранника к другой, смежной данной. Так как прилегающих вершин много, то каждый раз выбирается такая вершина, при переходе к которой обеспечивается наибольшее возрастание линейной формы. На каждом шаге процесса улучшения плана производится проверка на оптимальность. Очевидно, что план будет оптимальным, если среди вершин, прилегающих к данной, нет такой, при переходе к которой происходит возрастание линейной формы.

Задача: Предприятие производит краски 2-х видов: I – для внутренних работ, E – для внешних работ. A,B – исходные продукты, использующиеся для производства I,E.

Доход от реализации 1т краски I – 2000$, E – 3000$

Коэффициенты расхода исходных продуктов A и B на производство 1т краски I и E:

	I	E	Суточный запас, тонн
A	2	1	6
B	1	2	8

Известно, что суточная потребность краски для внутренних работ не превышает 2т, т.е. суточный спрос на I <=2т. Суточный спрос I не превышает суточного спроса на E больше чем на 1т.

Найти: оптимальный суточный план производства красок, максимизирующий ожидаемый максимальный доход.

Математическая постановка задачи:

Обозначим X_I(т/сут) – краски I ; X_E(т/сут) – краски E.

Целевая функция: - ожидаемый максимальный доход

Ограничения на запас продукта А:

Ограничения на запас продукта В:

, ,

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

Формируем начальную симплекс-таблицу. Для этого приводим задачу к стандартному виду: Ax=b

с – вектор целевой функции,

Введем дополнительные переменные:

- неиспользуемый остаток ресурса А

- неиспользуемый остаток ресурса В

- показывает, на сколько меньше максимального суточного производства мы произвели.

Замечание: каждому ограничению задачи (грани многоугольника дополнительных значений) соответствует уравнение вида x_i=0. Поэтому для выбора краеугольной точки многогранника достаточно выбрать 2 свободные переменные = 0. Остальные переменные называются базисными и определяются автоматически из системы ограничений. Однако не любая пара свободных переменных дает допустимую точку.

		XI		XE	S1	S2	S3	S4	решение
Z		-2		-3	0	0	0	0	0
S1		2		1	1	0	0	0	6
S2		1		2	0	1	0	0	8
S3		1		0	0	0	1	0	2
S4	1		-1		0	0	0	1		1

(строки – базисные переменные, столбцы – все переменные)