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

Методом искусственного базиса (симплекс-методом) решить ЗЛП:

.

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

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

Заполняем расчётную таблицу (симплекс) метода и подсчитываем значение индексных строк (пункт 3)

.Расчётная таблица (симплекс) метода. Нулевая итерация.

№ итерации

№ строки

-1

-1

Индексные строки

-24 M

-3M

-3M

M

M

-4

-2

Так как наиболее отрицательное значение показателя расположено в столбце , то переменную вводим в базис и исключаем из базиса ту переменную, для которой критерий будет минимальным. Критерий минимальный для четвёртой строки расчётной таблицы, базисная переменная которой . Эту переменную выводим из базиса. Таким образом, у нас разрешающим столбцом является первый столбец ( по индексу ), а разрешающей строкой- четвёртая строка. (p=1; q=4).

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

Расчётная таблица (симплекс) метода. Первая итерация

№ ите ра ции	№ ст ро ки
				-18		-3	-1
					-1
									--1
Индексные строки	18М		3М	М			-2М
+56		+6				-4

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

Расчётная таблица симплекс-метода. Вторая итерация.

№ ите ра ции	№ ст ро ки
				-9		-3/2	-1/2
					3/2	½
					½	½
					½	-1/2				-----
Индексная строка				-2

Расчётная таблица симплекс-метода. Третья итерация.

№ ите а ции	№ ст ро ки
										-2	----
					-1
									-1	-----
Индексная строка							-4

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

Расчётная таблица симплекс-метода. Четвёртая итерация.

							-1
				-1
Индексная строка

Индексная строка последней симплекс- таблицы не содержит отрицательных критериев. Получен оптимальный план. . Максимальное значение целевой функции

Экономическое истолкование решения задачи может быть таким: производится 14 единиц продукции первого вида и не производится продукция второго вида. Неиспользованные остатки сырья первого, второго, третьего и четвёртого видов составляют соответственно 18; 6; 0 и 0 единиц. Максимальная прибыль от реализации продукции составляет 56 (денежных) единиц.☻