§ 3. Геометрическая интерпретация решения задачи лп.

Графический способ решения задачи ЛП.

Ответы

Пример.

Дана общая задача ЛП:

(1)

при условиях:

;

;

;

;

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

Базис ; свободные переменные

Пусть тогда В выражении дляFможно увеличиватьпри этомFбудет уменьшаться. Примембудет увеличивать до 5, т.к. при этомПоскольку«ненадежнее» всех в базисе, выведем его из базиса, а в базис введемВыразимFи новые базисные переменные черезнайдёми подставим его в выражения (1) ,(2) ,(3).

В итоге получим :

min(*)

при условиях:

.

Допустимое базисное решение следующее: Свободные переменные.

Решая пример далее, видим, что увеличивать нельзя, так какбудет возрастатать (а нам нужноминимизировать). Значит. Свободную переменнуюможно увеличивать, но доиначебудет отрицательна.)

Итак, самая «ненадёжная » переменная Выводимиз базиса, а вместо её в базис вводим «провокатора» переменную Свободные переменные.

Из «ненадёжного» уравнения для

находим

и подставляем*). Получим:

Рис.2

min

при условиях:

Допустимое базисное решение:

Здесь можно увеличивать до 6, так как

При этом

Достигнуто оптимальное решение: В процессе перехода от одного базисного решения к другому значение F постоянно уменьшалось.

Покажем решение данного примера графически.

На координатные оси нанесем систему неравенств (см. пример). Выпуклая область (рис.2) соответствует совокупности решений системы неравенств. Минимальное и максимальное значения целевой функциидостигаются в точках пересечения этого многогранника решений с «опорными» прямыми, проведенными перпендикулярно векторуВыпишемиз базисных решений:

Вектор указывает положительное направление, при движении в которомFувеличивается. Целевая функция задачи ЛП достигает минимума (максимума) в крайней точке выпуклой области. ЕслиFпринимает оптимальное значение в нескольких точках, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек (случай, когда целевая функция достигает минимума на грани многогранника) [1].Множество всех планов задачи ЛП выпукло [1-4]. Отыскание оптимума целевой функции сводится к перебору крайних точек выпуклого многогранника.

§4. Алгоритм решения канонической задачи лп симплексным методом.

Основная задача ЛП называется канонической, если система уравнений каноническая, а целевая функция выражена через свободные неизвестные.

Рассмотрим алгоритм решения канонической задачи ЛП симплексным методом:

Минимизировать

при условиях:

;

Это общая задача ЛП. Переходим к каноническому виду:

при условиях

;

.

Здесь , апеременные. Нетрудно убедиться, чтоr(A) =r(R) , т.е. система ограничений совместна. Кроме того,r(A) = 4,n= 6. Составим исходную симплексную таблицу.

Исходная симплексная таблица

Базисные переменные	Свободные члены ()	Коэффициенты при неизвестных
	19	2	3	1				25
	13	2	1		1			17
	15		3			1		19
	18	3					1	22
F	0	7	5					12

Пустые клетки соответствуют нулям. Столбец контрольной суммы () включает в себя алгебраические суммы коэффициентов каждой строки и служит для контроля арифметических действий при последующем преобразовании данной таблицы. Последняя строка таблицы называется индексной. При ее заполнении свободный член целевой функции выписывается со своим знаком, а коэффициенты при неизвестных (оценки) – с противоположным.Выберем так называемый разрешающий столбец с положительной оценкой. Но таких столбцов два. Выбираем, например, столбец с оценкой 5. Далее выбирается так называемая разрешающая строка. Из отношений свободных членов к положительным коэффициентам разрешающего столбца () выбираемнаименьшее т.е. . Это отношение и соответствует разрешающей строке.Коэффициент 3, находящийся на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом. Выведемиз базиса, а(провокатор) введем в базис. В результате получим новые наборы базисных и свободных переменных. Необходимо выразить базисные переменные и целевую функцию через свободные переменные. Для этого разрешающую строку в исходной симплексной таблице делим на разрешающий элемент. Результат заноситься в новую симплексную таблицу “Итерация 1”.

Итерация 1

Базисные переменные	Свободные члены	Коэффициенты при неизвестных
	4	2		1		-1			6
	8	2			1	-1/3			32/3
	5		1			1/3			19/3
	18	3						1	22
F	-25	7				-5/3			-59/3

Коэффициенты данной симплексной таблицы вычисляются таким образом, чтобы в разрешающем столбце исходной таблицы все элементы, кроме разрешающего, стали нулевыми. Например, для того что бы в исходной таблице в уравнении 2+3+=19 получить коэффициент принуль, надо третью строку в таблице «Итерация 1» умножить на (-3) и сложить с первой строкой исходной таблицы. Результат записывается в первую строку таблицы «Итерация 1». Получим 2+-=4, откуда базисное переменноелегко можно выразить через свободные переменные. Аналогично вычисляется в этой строке и контрольная сумма: (. Алгебраическим сложением коэффициентов строки убеждаемся, что арифметической ошибки нет. В полученной таблице «Итерация 1» выбираетсяположительная оценка. В частности, столбец, соответствующий оценке 7, будет разрешающим. Затем выбирается разрешающая строка и т.д. Столбец контрольной суммы для простоты можно опустить. Продолжим решение. В итоге получим следующие симплексные таблицы:

Итерация 2

Базисные переменные	Свободные члены ()	Коэффициенты при неизвестных
	2	1		1/2		-1/2
	4			-1	1	2/3
	5		1			1/3
	12			-3/2		3/2	1
F	-39			-7/2		11/6

Итерация 3

Базисные переменные	Свободные члены ()	Коэффициенты при неизвестных
	5	1		-1/4	3/4
	6			-3/2	3/2	1
	3		1	1/2	-1/2
	3			3/4	-9/4		1
F	-50			-3/4	-11/4

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

Решая задачу максимизации при тех же условиях, что и раньше, получим. Оптимальное решение этой задачи совпадает с оптимальным решением задачи минимизации.

Алгоритм решения канонической задачи ЛП

симплексным методом (общий случай).

Запишем в общем случае алгоритм решения канонической задачи ЛП симплексным методом [1-4].

1. Дано

при условиях:

;

		Коэффициенты при неизвестных
			…		…			…		…
		1
				1
						1
F

.

2. Составим исходную симплексную таблицу.

3. Выберем разрешающий столбец из условия

(в задаче максимизации) .

4. Выберем q – ю разрешающую строчку из условия

для

5. Формируем новую симплексную таблицу.

Пересчитываем элементы разрешающей q-й строки по формуле:

Вычисляем элементы остальных строк:

Основная теорема симплексного метода формулируется следующим образом [3].

Если после выполнения очередной итерации задачи

при условиях:

;

.