Теория игр

Задача 1. Задача оптимального производства продукции.

Предприятие планирует выпуск двух видов продукции I и II, на производство которых расходуется три вида сырья А, В и С. Потребность a_ij на каждую единицу j-го вида продукции i-го вида сырья, запас b_i соответствующего вида сырья и прибыль c_j от реализации единицы j-го вида продукции заданы таблицей.

Виды сырья	Виды продукции		Запасы сырья
	I	II
А	5	2	30
В	1	1	9
С	2	2	18
прибыль	3	6
план (ед.)	х1	х2

Для производства двух видов продукции I и II с планом х₁ и х₂ единиц составить целевую функцию прибыли Z и соответствующую систему ограничений по запасам сырья, предполагая, что требуется изготовить в сумме не менее n = 5 единиц обоих видов продукции.

В условиях задачи составить оптимальный план (х₁; х₂) производства продукции, обеспечивающий максимальную прибыль Z_max. Определить остатки каждого вида сырья. (Задачу решить симплекс-методом)

 

Решение.

Если производственный план –  ед. продукции I и ед. продукции II, то сырья будет израсходовано ед., сырья – ед., сырья – ед. Запасы сырья составляют 30, 9 и 18 ед. соответственно. Таким образом, получаем ограничения:

Требуется изготовить в сумме не менее 5 единиц обоих видов продукции:

.

Согласно смыслу задачи, и должны быть неотрицательными:

.

План  принесёт прибыль ден. ед. Поскольку надо найти такой план, при котором прибыль будет максимальна, то целевая функция будет иметь вид:

.

Запишем математическую модель задачи:

;

Решим задачу симплекс-методом.

Введём в систему ограничений дополнительные неотрицательные переменные так, чтобы получить систему уравнений:

.

Система уравнений имеет 4 независимых уравнения и 6 переменных, то есть, можно выразить 4 переменные (базисные) через 2 оставшиеся (свободные). В качестве базисных переменных выберем , , и . Тогда и − свободные.

Приведём систему к единичному базису: 

.

Мы получили новую систему уравнений, эквивалентную исходной:

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

;

.

Запишем задачу в стандартной форме:

,

Теперь можно применять симплексный  метод.

Составим первую симплекс-таблицу.

 

	Базис	Сбаз	Переменные
1		0	0	-3	1	0	0	5	5
2		0	0	0	0	1	0	1	4
3		0	0	0	0	0	1	2	8
4		3	1	1	0	0	0	-1	5
5		−	0	-3	0	0	0	-3	15

Начальное базисное решение  − допустимое; .

В последней строке есть отрицательные оценки − решение неоптимальное.

Отрицательные оценки одинаковые, поэтому выбираем любую оценку, например, стоящую в шестом столбце. Шестой столбец – разрешающий.

Для положительных коэффициентов  разрешающего столбца составляем оценочные  отношения – отношения свободного члена к коэффициенту:

для первой строки:   ;

для второй строки:   ;

для третьей строки:   .

В качестве разрешающей  выбираем первую строку с наименьшим отношением.

Таким образом, разрешающий элемент:

.

Производим замену базиса – переводим  в базис  вместо .

Заполняем вторую симплекс-таблицу.

Элементы первой строки делим на разрешающий элемент:

.

Из второй строки вычитаем новую первую строку:

 

Из третьей строки вычитаем новую первую строку, умноженную на 2:

К четвёртой строке прибавляем новую первую строку:

К последней строке прибавляем новую  первую строку, умноженную на 3:

 

	Базис	Сбаз	Переменные
1		0	0	-3/5	1/5	0	0	1	1
2		0	0	3/5	-1/5	1	0	0	3
3		0	0	6/5	-2/5	0	1	0	6
4		3	1	2/5	1/5	0	0	0	6
5		−	0	-24/5	3/5	0	0	0	18

Второе базисное решение − допустимое; .

В последней строке есть отрицательная  оценка − решение неоптимальное.

Второй столбец – разрешающий.

Оценочные отношения:

для второй строки:   ;

для третьей строки:   ;

для четвёртой строки:  .

Вторая строка – разрешающая.

Разрешающий элемент:

.

Производим замену базиса – переводим  в базис  вместо .

Заполняем третью симплекс-таблицу.

 

	Базис	Сбаз	Переменные
1		0	0	0	0	1	0	1	4
2		6	0	1	-1/3	5/3	0	0	5
3		0	0	0	0	-2	1	0	0
4		3	1	0	1/3	-2/3	0	0	4
5		−	0	0	-1	8	0	0	42

 

Третье базисное решение − допустимое; .

В последней строке есть отрицательная  оценка − решение неоптимальное.

Третий столбец – разрешающий.

Оценочные отношения:

для четвёртой строки:  .

Четвёртая строка – разрешающая.

Разрешающий элемент:

.

Производим замену базиса – переводим  в базис  вместо .

Заполняем четвёртую симплекс-таблицу.

 

	Базис	Сбаз	Переменные
1		0	0	0	0	1	0	1	4
2		6	1	1	0	1	0	0	9
3		0	0	0	0	-2	1	0	0
4		0	3	0	1	-2	0	0	12
5		−	3	0	0	6	0	0	54

Четвёртое базисное решение − допустимое; .

В последней строке нет отрицательных  оценок − решение оптимальное.

 

Выводы:

максимальная прибыль в размере  ден. ед. будет получена при производственном плане ед. продукции I и ед. продукции II;