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

Пример №3.1.

Решение.

Шаг1.

Данную задачу не требуется приводить к каноническому виду, т.к. система ограничений содержит только равенства.

Матрица условий-ограничений для данной задачи будет иметь вид:

m=2 n=5.

Для удобства решения исходные данные задачи следует представить в виде:

.

Шаг 2.

В качестве базисных неизвестных выбираются x₁ и x₂, т.к. каждая из них входит только в одно условие–ограничение с коэффициентом +1 и в остальные условия–ограничения с коэффициентом 0.

Одним из допустимых решений задачи ЛП (1*) – (3*) является базисное неотрицательное решение системы (2*)

Ему соответствует значение целевой функции, равное

.

Шаг 3.

определяется по формуле (3.7).

;

;

;

;

.

При использовании формулы вычисления имеют вид:

;

;

;

;

.

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

Симплексная таблица

	Базис	B			-9
x1	x2	x3	x4	x5
	x1					–6
	x2				–7
		87–F			-25	–30

Шаг 4.

В последней строке симплексной таблицы есть положительный коэффициент при свободной неизвестной x₅. При этой неизвестной в системе уравнений есть положительные коэффициенты. Следовательно, полученное базисное решение не является оптимальным и согласно правилу №3 необходимо искать оптимальное решение путем пересчета симплексной таблицы.

Шаг 5.

Выбор главного столбца симплексной таблицы:

,

s=5, главный столбец x₅.

Выбор главной строки:

,

r=1, главная строка x₁.

Неизвестная x₅ становится базисной, x₁— свободной.

Расчет новой симплексной таблицы производится в соответствии с формулами (3.13 – 3.18) алгоритма пересчета симплексной таблицы:

1) новые элементы главной строки:

, , , , ;

:

2) остальные новые элементы таблицы:

, , , , ; ;

, , , , ;

.

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

Симплексная таблица

В последней строке симплексной таблицы есть положительный коэффициент при свободной неизвестной x₄, и при этой неизвестной в системе уравнений есть один положительный коэффициент. Следовательно, полученное базисное решение не является оптимальным и согласно правилу №3 необходимо искать оптимальное решение путем пересчета симплексной таблицы.

Шаг 6.

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

Выбор главного столбца симплексной таблицы:

,

s=4, главный столбец x₄.

Выбор главной строки:

,

r=4, главная строка x₄.

Неизвестная x₄ становится базисной, x₂— свободной.

Расчет новой симплексной таблицы производится в соответствии с формулами (3.13 – 3.18) алгоритма пересчета симплексной таблицы:

1) новые элементы главной строки:

, , , , ;

;

2) остальные новые элементы таблицы:

, , , , ; ;

, , , , ;

.

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

Симплексная таблица

В третьей симплексной таблице среди элементов последней строки нет ни одного положительного. Поэтому данное базисное решение является оптимальным.

Ответ.

Оптимальное базисное решение:

Наименьшее значение линейной формы:

.

Пример №3.2.

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

.

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

Решение.

Для решения данной задачи необходимо составить ее математичкую модель:

найти производственную программу

(x₁, x₂, x₃, x₄)

максимизирующую прибыль

при ограничениях по ресурсам

и по смыслу задачи , , , .

Система ограничений состоит из неравенств. Следовательно, ее необходимо привести к каноническому виду при помощи дополнительных неотрицательных неизвестных x₅, x₆, x₇:

.

Дополнительные переменные x₅, x₆, x₇ имеют смысл остатков соответствующих ресурсов. Среди всех решений системы уравнений, удовлетворяющих условию неотрицательности

, , , , , ,

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

Базисными неизвестными являются дополнительные переменные x₅, x₆, x₇.

Одним из допустимых решений задачи является базисное неотрицательное решение системы ограничений

Ему соответствует значение целевой функции, равное

.

Для составления первой симплексной таблицы необходимо вычислить :

– коэффициенты при базисных неизвестных;

;

;

;

;

;

;

.

Симплексная таблица

	Базис	B
x1	x2	x3	x4	x5	x6	x7
	x5
	x6
	x7
		0–F	-40	-20	-29	-54

В последней строке симплексной таблицы есть отрицательные коэффициенты при свободных неизвестных x₁, x₂, x₃ и x₄. При любой из этих неизвестных в системе уравнений есть хотя бы один положительный коэффициент. Следовательно, согласно правилу №3 необходимо искать оптимальное решение путем пересчета симплексной таблицы.

Выбор главного столбца:

,

s=4, главный столбец x₄.

Выбор главной строки:

Т.к. две дроби равны и являются минимальными, то можно взять любую из них. Пусть r=2, главная строка x₆.

Неизвестная x₄ становится базисной, x₆— свободной.

Расчет новой симплексной таблицы производится в соответствии с формулами (3.13 – 3.18) алгоритма пересчета симплексной таблицы. Вторая симплексная таблица имеет вид:

Симплексная таблица

В получившейся симплексной таблице среди элементов последней строки нет ни одного отрицательного. Поэтому второе базисное решение является оптимальным:

Ответ.

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

При этом остаток ресурса первого вида , второго вида x₆ = 0, третьего вида .