Пример решения ОЗЛП симплексным методом

Пусть необходимо найти оптимальный план производства двух видов продукции х ₁ и х ₂ (табл. 3.2).

Таблица 3.2 – Исходные данные примера

Вид продукции	Норма расхода ресурса на единицу прибыли	Прибыль на единицу изделия
	А	В
Объем ресурса

1. Построим ОМ

ограничение по ресурсу А;

ограничение по ресурсу В.

2. Преобразуем задачу в приведенную каноническую форму. Для этого достаточно ввести дополнительные переменные x ₃ и x ₄ . В результате неравенства преобразуются в строгие равенства:

Построим исходную симплексную таблицу и найдем начальное базисное решение. Им будет пара значений дополнительных переменных, которым соответствует единичная подматрица

и

Базисные переменные	Свободные члены (план)	x 1	x 2	x 3	x 4
x 3
x 4
F j - C j

1-я итерация. Находим генеральный столбец и генеральную строку:

Генеральный элемент равняется 5.

Базисные переменные	Свободные члены (план)	x 1	x 2	x 3	x 4
x 1			0,4	0,2
x 4			0,8	- 1,6
F j – C j			0,2	- 1,4

2-я итерация. Найденное базисное решение не является оптимальным, так как строка оценок (F _j - C _j ) содержит один положительный элемент. Находим генеральный столбец и генеральную строку:

(0, 0,3, - 1,4, 0)

Базисные переменные	Свободные члены (план)	x 1	x 2	x 3	x 4
x 1					- 0,5 0
x 2				- 2	1,25
F j - C j				- 1	- 0,25

Найденное решение оптимально, так как все специальные оценки целевой функции (F _j - C _j ) равны нулю или отрицательны. F (x) = 29; x ₁ = 2; x ₂ = 5.

Дата добавления: 2014-01-04