Ой способ решения (симплексным методом)

Представим задачу в виде основной задачи линейного программирования:

max, при .

С помощью дополнительных неотрицательных переменных перейдём к системе уравнений. Введём новые переменные и добавим их к левым частям ограничений. Получим систему уравнений вместо системы неравенств.

.

Функция цели имеет вид: max,

Запишем эту систему уравнений в виде:

Запишем теперь эту систему ограничений в форме векторного уравнения:

Введём векторы:

; ; ; ; ;

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

Получим систему: ,

из которой следует . Итак, получаем первоначальный опорный план; . Для проверки плана на оптимальность составим симплексную таблицу, которая имеет общий вид:

№	Базис	Сj (базисные)	А0	С1	С2	С3	С4	С5
А1	А2	А3	А4	А5
	А3	С3	x3	x31	x32	x33	x34	x35
	А4	С4	x4	x41	x42	x43	x44	x45
	А5	С5	x5	x51	x52	x53	x54	x55
		П(Х0)	Z1-C1	Z2-C2	Z3-C3	Z4-C4	Z5-C5

В этой таблице записаны координаты векторов А₁, А₂, А₃, А₄, А₅ в базисе А₃, А₄, А₅, то есть разложение всех векторов , где

Критерий оптимальности плана: если для некоторого плана Х₀ разложения всех векторов в данном базисе удовлетворяют условию то план Х₀ является оптимальным и доставляет линейной функции максимальное значение. При невыполнении условия оптимальности в базис включают в первую очередь тот вектор, которому соответствует min (Z_j –C_j), где минимум берется по тем j, для которых (Z_j-C_j)<0.

Первая симплексная таблица имеет вид:

№	Базис	Сj (базисные)	А0
А1	А2	А3	А4	А5
	А3
	А4
	А5
			-4	-2

Поясним вычисления последней строки и последнего столбца.

,

,

, ,

,

,

Для векторов базиса оценки . Среди оценок имеются две отрицательные: и . Это означает, что первоначальный опорный план не является оптимальным, и его необходимо улучшить. Базис нового плана будет содержать два вектора старого плана и новый вектор А₁, которому соответствует . Столбец, соответствующий вектору А₁, является разрешающим(ведущим).

Для того, чтобы определить какой вектор нужно исключить из первоначального базиса, подсчитаем отношения координат исходного плана соответственно к элементам разрешающего столбца, то есть . Для координат вектора А₁: , , . Выбираем , что соответствует третьей строке, следовательно, из базиса исключаем вектор А₅. Новый базис состоит из векторов . Третья строка является разрешающей. Элемент , стоящий на пересечении разрешающей строки и разрешающего столбца, называется разрешающим.

Найдём коэффициенты разложения всех векторов в новом базисе. Поставленная задача решается просто. Разрешающий элемент 5 стоит на пересечении третьей строки и столбца А_1.. Подсчитаем новые элементы третьей строки. Для этого старые элементы этой строки (№3) разделим на разрешающий элемент 5 и запишем в строчку с номером 7 второй симплексной таблицы. Так как вектор А₁ входит в базис, то его координаты кроме одной сделаем нулевыми. Для этого из всех элементов строки №1 вычтем соответствующие элементы строки №7 и результат запишем в строку №5.

Затем все элементы строки №7 умноженные на 3 вычтем соответственно из элементов строки №2 и результат запишем в строку №6

№	Базис	Сj (базисные)	А0
А1	А2	А3	А4	А5
	А3
	А4
	А1

Итак, получили новый опорный план: и новое разложение векторов () в базисе А₃,А₄,А₁.

Вторая симплексная таблица в условных обозначениях имеет вид:

№	Базис	Сj (базисные)	А0	С1	С2	С3	С4	С5
А1	А2	А3	А4	А5
	А3	С3	x3	x31	x32	x33	x34	x35
	А4	С4	x4	x41	x42	x43	x44	x45
	А1	С1	х1	х11	х12	х13	х14	х15
		П(Х1)	Z1-C1	Z2-C2	Z3-C3	Z4-C4	Z5-C5

Для проверки плана на оптимальность вычисляем элементы строки №8:

П(Х₁)= ,

,

, ,

,

.

Оценочная строка №8 второй симплексной таблицы содержит один отрицательный элемент. Критерий оптимальности не выполнен. Столбец А₂ является разрешающим. Для того, чтобы определить какой вектор нужно исключить из базиса А₃,А₄,А₁, подсчитаем отношения координат к элементам разрешающего столбца А₂, то есть : , , . Выбираем , что соответствует строке №6, которая является разрешающей. Из базиса исключаем вектор А₄, вместо него вводим вектор А₂. Новый базис состоит из векторов . Элемент , стоящий на пересечении разрешающей строки и разрешающего столбца, является разрешающим. Новый опорный план имеет вид: .

Аналогично как в прошлый раз, строим третью симплексную таблицу. Все элементы строки №6 делим на разрешающий элемент и записываем в строку №10. Все координаты вектора А₂, кроме одного, должны обратится в нуль. Для этого все элементы строки №10 умножим на и вычтем из соответствующих элементов строки №5, результат запишем в строку №9. Затем все элементы строки №10 умножим на и вычтем из соответствующих элементов строки №7, результат запишем в строку №11.

№	Базис	Сj (базисные)	А0
А1	А2	А3	А4	А5
	А3						-
	А2
	А1						-

Вычислим элементы строки №12:

П(Х₂)= ,

,

, ,

,

.

Оценочная строка №12 не содержит отрицательных элементов. Критерий оптимальности выполнен. Значит, Х₃=() - оптимальное базисное решение, при котором функция цели принимает максимальное значение. Переменные , и не входят в исходную задачу, Следовательно, и - решение задачи; наибольшая прибыль (денежных единиц).

Ответ: план производства изделий А и В таков: наибольшая

прибыль от реализации изделий – 70 денежных единиц будет при производстве 15 изделий А и 5 изделий В.

Поиск по сайту: