Табличный симплекс-метод. 
Линейное программирование

Универсальным вычислительным методом решения задачи ЛП является так называемый симплекс-метод. Идея метода состоит в последовательном «улучшении» планов задачи по определенному критерию до получения оптимального решения.

Как уже было отмечено, оптимальное значение линейная целевая функция может достигать в крайних (граничных) точках ОДР, а именно в угловых точках. Важно заметить, что, если размерность задачи (количество переменных и количество ограничений) велики, то угловых точек может быть очень много и указать нужную становится весьма затруднительным делом, а определять оптимальное решение простым перебором весьма долгое и рутинное занятие.

Этих недостатков и лишен симплекс-метод, согласно которому: находясь в одной из вершин многогранной области — из всех соседних Соседняя вершина ОДР — смежное допустимое решение. вершин выбирается та, которая «улучшает» целевую функцию.

Рассмотрим процесс подготовки исходных данных и алгоритм решения задачи этим методом. Для решения задачи ЛП.

необходимо предварительно выполнить следующие процедуры:

привести математическую модель задачи к каноническому виду (систему активных ограничений типа неравенств привести к уравнениям путем введения дополнительных «искусственных» переменных);

определить начальное допустимое решение задачи;

ввести в исходную таблицу параметры, соответствующие начальному опорному плану;

весовые коэффициенты переменных целевой функции; переменные текущего базиса; значения базисных переменных (столбец); элементы матрицы условий задачи (столбцы); оценки «дефект» ;

Оценки определяются по формулам:

Весовые коэффициенты при базисных переменных проставляются в левый столбец таблицы. Значение целевой функции при текущем базисе.

заносятся в последнюю строку столбца.

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

Шаг I: Выбор начального базисного решения.

Шаг II: Переход от начального решения к другому допустимому базисному решению с лучшим значением целевой функции (все решения, которые «хуже» исключаются).

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

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

Критерий оптимальности. Обозначим относительную оценку небазисной переменной через.

оценки базисных переменных.

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

Проиллюстрируем все выше сказанное примером.

Приведем задачу к каноническому виду:

Здесь мы ввели в рассмотрение дополнительные переменные и, которые «уравновешивают» активные ограничения. Они же и образуют начальный базис.

Последовательные итерации удобно вести в компактном виде в таблице (см. таблицу I.).

Таблица I.

№ 1.
	— 1.
		— 1.

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

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

Далее элементарные гауссовы преобразования строк приведут исследователя к новому базису и новой таблице (таблица II).

Таблица II.

№ 2.
					— 3.
		— 1.
				— 3.

Сформулируем последовательность операций перехода к таблице II.

Прибавить разрешающую строку к первой строке таблицы I. Результат записать в первую строку таблицы II.

Умножить разрешающую строку на -3 и прибавить ко второй строке таблицы I. Результат записать во вторую строку таблицы II.

Третья строка таблицы II — это разрешающая строка таблицы I, элементы которой разделены на разрешающий элемент (в клетке на пересечении разрешающей строки и разрешающего столбца).

Строка так же вычисляется с помощью элементарных преобразований. По-прежнему, и это чрезвычайно важно, — рабочей строкой является разрешающая строка. Умножить третью строку таблицы I на -3 и прибавить к строке. Результат записать в строку таблицы II.

Работа со строками таблиц осуществляется так, что последним (замыкающим строку) элементом является соответствующий элемент столбца .

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

Далее процесс продолжается до тех пор пока не будет выполнен критерий оптимальности (см. таблицу III).

Таблица III.

№ 3.
			— 1.

Таким образом,.

Изобразим графически полученную ситуацию (см. рисунок I. 2.5).

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

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

Составить математическую модель, определения максимальной прибыли от реализации всей продукции видов и. Решить задачу симплекс-методом. Дать геометрическую интерпретацию математической формулировки. Данные приведены в таблице данных I.

Таблица данных I.

№. Варианта.
I.
II.
III.
IV.
V.
VI.
VII.
VIII.
IX.
X.

II. Предположим, что для производства двух видов продукции и можно использовать только материал трех сортов. При этом на изготовление единицы изделия вида расходуется кг материала 1-го сорта, кг материала 2-го сорта и кг материала 3-го сорта. На изготовление единицы изделия вида расходуется кг материала 1-го сорта, кг материала 2-го сорта и кг материала 3-го сорта. На складе фабрики имеется всего материала первого сорта кг, материала второго сорта и материала третьего сорта кг. От реализации единицы готовой продукции вида фабрика имеет прибыль, а от реализации продукции вида прибыль составляет денежных единиц.

Составить математическую модель, определения максимальной прибыли от реализации всей продукции видов и. Решить задачу симплекс-методом. Дать геометрическую интерпретацию математической формулировки. Данные приведены в таблице данных II.

Таблица данных II.

№. Варианта.
I.
II.
III.
IV.
V.
VI.
VII.
VIII.
IX.
X.