Составление плана производства изделий А и В, обеспечивающий максимальную прибыль готовой продукции предприятия

Размещено на http://www.allbest.ru/

Задача

Предприятие выпускает два вида продукция А и В, для производства которых используется сырье трех видов. На изготовление единицы изделия А требуется затратить сырья каждого вида а_1, а₂ , а₃ кг соответственно, а для единицы изделия В -- b₁, b₂, b₃ кг. Производство обеспечено сырьем каждого вида в количестве P₁, P₂, P₃ кг, соответственно. Прибыль от реализации изделия А составляет б руб., а единицы изделия В -- в руб. Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль готовой продукции.

а) решите задачу симплекс-методом;

б) сформулируйте двойственную задачу и найдите ее решение;

в) решите исходную задачу геометрически.

А) Симплекс-метод.

Производственная задача сформулируется следующим образом: «Найти такие объемы производства продукции А и В, при которых потребление ресурсов в соответствии с нормативами не превышало бы их наличия, и при этом прибыль от продажи продукции была бы максимальна».

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

	Изделие А (х1)	Изделие В (х2)	Наличие
Ресурс 1	5	4	810
Ресурс 2	4	2	980
Ресурс 3	2	6	786
Прибыль	34	36

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

(I) 5х1+4х2810

(II) 4х1+2х2980

(III) 2х1+6х2786

Х10, х20

F = 34х1+36х2max

Система неравенств отражает ограничения на потребялемые ресурсы, а целевая функция F определяет прибыль, которую необходимо максимизировать. Значение целевой функции и есть оптимальный план (решение). симплекс задача линейный программирование

Введем дополнительные переменные X3, X4, X5.

F(X)= 34X1+36X2 (max).

Ограничения:

5X1+4X2+X3=810

4X1+2X2+X4=980

2X1+6X2+X5=786

Xi?0

Составим симплекс таблицу:

Базисные переменные	Свободные переменные	Х1	Х2
Х3	810	5	4
Х4	980	4	2
Х5	786	2	6
F	0	-34	-36

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-36). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.

Пересчитаем cимплекс-таблицу:

Базисные переменные	Свободные переменные	Х1	Х5
Х3	286	11/3	-2/3
Х4	718	10/3	-1/3
Х2	131	1/3	1/6
F	4716	-22	6

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-22). А ведущая строка та, у которой найменьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.

Пересчитаем таблицу:

Базисные переменные	Свободные переменные	Х3	Х5
Х1	78	3/11	-2/11
Х4	458	-10/11	3/11
Х2	105	-1/11	5/22
F	6432	6	2

Найдено оптимальное решение. (оптимальное решение найдено тогда, когда все члены строки F и столбца свободных членов положительны).

Б) двойственная задача.

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

F(X)=34X1+36X2 (max)

Ограничения:

5X1+4X2?810

4X1+2X2?980

2X1+6X2?786

X1?0

X2?0

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

{F(x) = СT x| Ax?B, xi ?0, i = 1,m}

В результате получим следующие матрицы:

Для составления двойственной задачи линейного программирования найдем матрицы

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

F(Y)=810Y1+980Y2+786Y3 (min)

Ограничения:

5Y1+4Y2+2Y3?34

4Y1+2Y2+6Y3?36

Y1?0

Y2?0

Y3?0

Оптимальный план можно записать так:

x1 = 78

x4 = 458

x2 = 105

F(X) = 34*78 + 36*105 = 6432

Оптимальный план двойственной задачи равен:

y1 = 6

y2 = 0

y3 = 2

Z(Y) = 810*6+980*0+786*2 = 6432

В) геометрическое решение.

Необходимо найти максимальное значение целевой функции F=34X1+36X2=>max, при системе ограничений:

5x1+4x2?810 (1)

4x1+2x2?980 (2)

2x1+6x2?786 (3)

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

Обозначим границы области многоугольника решений.

Равный масштаб:



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

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых 1 и 3, то ее координаты удовлетворяют уравнениям этих прямых:

5x1+4x2?810

2x1+6x2?786

Решив систему уравнений, получим: x1 = 78, x2 = 105

Откуда найдем максимальное значение целевой функции:

F(X) = 34*78 + 36*105 = 6432

Ответ. 6432.

Задача 18. На трех базах А₁, А₂, А₃ находится однородный груз в количестве a₁, a₂, а₃ т. Этот груз необходимо развести пяти потребителям В_1, В₂, В₃, B₄, B₅, потребности которых в данном грузе составляют b₁ b₂, b₃, Ь₄, Ь₅ т соответственно. Стоимость перевозок пропорциональна расстоянию н количеству перевозимого груза. Матрица тарифов и значения a₁, a₂, a₃ и b₁, b₂, b₃ приведены в таблице. Требуется спланировать перевозки так, чтобы их общая стоимость была минимальной.

потребители Базы	B1	B2	B3	B4	B5	Запасы (ai)
A1	16	7	10	9	14	220
A2	11	5	3	8	15	180
A3	9	20	15	11	6	200
Потребности (bj)	80	140	200	60	120	600

Решение. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	1	2	3	4	5	Запасы
1	16	7	10	9	14	220
2	11	5	3	8	15	180
3	9	20	15	11	6	200
Потребности	80	140	200	60	120

Проверим необходимое и достаточное условие разрешимости задачи.

? a = 220 + 180 + 200 = 600

? b = 80 + 140 + 200 + 60 + 120 = 600

Условие баланса соблюдается. Запасы равны потребностям.

Занесем исходные данные в распределительную таблицу.

	1	2	3	4	5	Запасы
1	16	7	10	9	14	220
2	11	5	3	8	15	180
3	9	20	15	11	6	200
Потребности	80	140	200	60	120

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

	1	2	3	4	5	Запасы
1	16	7[140]	10[20]	9[60]	14	220
2	11	5	3[180]	8	15	180
3	9[80]	20	15	11	6[120]	200
Потребности	80	140	200	60	120

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным. Строим новый план.

	1	2	3	4	5	Запасы
1	16	7[140]	10[20]	9[60]	14	220
2	11[80]	5	3[100]	8	15	180
3	9	20	15[80]	11	6[120]	200
Потребности	80	140	200	60	120

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

3. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

4. Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=18	v2=7	v3=10	v4=9	v5=1
u1=0	16	7[140]	10[20]	9[60]	14
u2=-7	11[80]	5	3[100]	8	15
u3=5	9	20	15[80]	11	6[120]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

(1;1): 0 + 18 > 16

(3;1): 5 + 18 > 9

(3;4): 5 + 9 > 11

Выбираем максимальную оценку свободной клетки (3;1): 9

Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

	1	2	3	4	5	Запасы
1	16	7[140]	10[20]	9[60]	14	220
2	11[80][-]	5	3[100][+]	8	15	180
3	9[+]	20	15[80][-]	11	6[120]	200
Потребности	80	140	200	60	120

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 80. Прибавляем 80 к объемам грузов, стоящих в плюсовых клетках и вычитаем 80 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	16	7[140]	10[20]	9[60]	14	220
2	11	5	3[180]	8	15	180
3	9[80]	20	15[0]	11	6[120]	200
Потребности	80	140	200	60	120

Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=4	v2=7	v3=10	v4=9	v5=1
u1=0	16	7[140]	10[20]	9[60]	14
u2=-7	11	5	3[180]	8	15
u3=5	9[80]	20	15[0]	11	6[120]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

(3;4): 5 + 9 > 11

Выбираем максимальную оценку свободной клетки (3;4): 11

Для этого в перспективную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

	1	2	3	4	5	Запасы
1	16	7[140]	10[20][+]	9[60][-]	14	220
2	11	5	3[180]	8	15	180
3	9[80]	20	15[0][-]	11[+]	6[120]	200
Потребности	80	140	200	60	120

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	16	7[140]	10[20]	9[60]	14	220
2	11	5	3[180]	8	15	180
3	9[80]	20	15	11[0]	6[120]	200
Потребности	80	140	200	60	120

Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=7	v2=7	v3=10	v4=9	v5=4
u1=0	16	7[140]	10[20]	9[60]	14
u2=-7	11	5	3[180]		15
u3=2	9[80]	20	15	11[0	6[120]

Опорный план является оптимальным.

Минимальные затраты составят:

F(x) = 7*140 + 10*20 + 9*60 + 3*180 + 9*80 + 6*120 = 3700

Задача 28. Найти оптимальные стратегии (чистые и смешанную) игроков, верхнюю и нижнюю цены игры, заданной матрицей:

Решение.

Решение матричной игры определяется на основе минимаксной стратегии или решением симплекс-методом.

Решим приведенную задача тремя способами:

1) С позиции проигрышей игрока В стратегия B3 доминирует над стратегией B1, следовательно исключаем 3-й столбец матрицы.

Игроки	B1	B2	B3	a = min(Ai)
A1	1	5	2	1
A2	3	1	0	0
A3	2	1	3	1
b = max(Bi )	3	5	3	0

Находим гарантированный выигрыш, определяемый нижней ценой игры a=max(ai)=1, которая указывает на максимальную чистую стратегию A1.

Верхняя цена игры b = min(bj) = 3.

Что свидетельствует об отсутствии седловой точки, так как a<>b, тогда цена игры находится в пределах 1 <= y <= 3. Находим решение игры в смешанных стратегиях.

Запишем систему уравнений.

Для игрока I:

p₁+3p₂+p₃ = y

5p₁+p₂+p₃ = y

2p₁+p₃ = y

p₁+p₂+p₃ = 1

Для игрока II:

q₁+5q₂+2q₃ = y

3q₁+q₂ = y

q₁+q₂+q₃ = y

q₁+q₂+q₃ = 1

Решая эти системы методом Гаусса, находим:

p1 = 0 (вероятность применения 1-ой стратегии).

p2 = 0 (вероятность применения 2-ой стратегии).

p3 = 1 (вероятность применения 3-ой стратегии).

q1 = ²/₅ (вероятность применения 1-ой стратегии).

q2 = ^-1/₅ (вероятность применения 2-ой стратегии).

q3 = ⁴/₅ (вероятность применения 3-ой стратегии).

Цена игры

y = 1.

С позиции проигрышей игрока В стратегия B3 доминирует над стратегией B1, следовательно исключаем 3-й столбец матрицы.

Игроки	B1	B2	B3	a = min(Ai)
A1	1	5	2	1
A2	3	1	0	0
A3	2	1	3	1
b = max(Bi )	3	5	3	0

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 1, которая указывает на максимальную чистую стратегию A1.

Верхняя цена игры b = min(bj) = 3.

Что свидетельствует об отсутствии седловой точки, так как a<>b, тогда цена игры находится в пределах 1 <= y <= 3. Находим решение игры в смешанных стратегиях.

Математические модели пары двойственных задач линейного программирования можно записать так:

найти минимум функции F(x) при ограничениях:

x₁+3x₂+2x₃ >= 1

5x₁+x₂+x₃ >= 1

2x₁+3x₃ >= 1

F(x) = x₁+x₂+x₃ = min

найти максимум функции Ф(y) при ограничениях:

y₁+5y₂+2y₃ <= 1

3y₁+y₂ <= 1

2y₁+y₂+3y₃ <= 1

Ф(y) = y₁+y₂+y₃ = max

Решаем эти системы симплексным методом. Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим минимальное значение целевой функции F(X) = x₁ + x₂ + x₃ при следующих условиях - ограничений.

x₁ + 3x₂ + 2x₃?1

5x₁ + x₂ + x₃?1

2x₁ + 3x₃?1

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

1x₁ + 3x₂ + 2x₃-1x₄ + 0x₅ + 0x₆ = 1

5x₁ + 1x₂ + 1x₃ + 0x₄-1x₅ + 0x₆ = 1

2x₁ + 0x₂ + 3x₃ + 0x₄ + 0x₅-1x₆ = 1

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

-1x₁-3x₂-2x₃ + 1x₄ + 0x₅ + 0x₆ = -1

-5x₁-1x₂-1x₃ + 0x₄ + 1x₅ + 0x₆ = -1

-2x₁ + 0x₂-3x₃ + 0x₄ + 0x₅ + 1x₆ = -1

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

Решим систему уравнений относительно базисных переменных:

x₄, x₅, x₆,

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

План	Базис	B	x1	x2	x3	x4	x5	x6
0	x4	-1	-1	-3	-2		0	0
	x5	-1	-5	-1	-1	0		0
	x6	-1	-2	0	-3	0	0	1
Индексная строка	F(X0)	0	1	1	1	0	0	0

X1 = (0,0,0,-1,-1,-1)

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

В качестве ведущего выберем столбец, соответствующий переменной x₁. 1-ая строка является ведущей.

План	Базис	B	x1	x2	x3	x4	x5	x6
	x1	1	1	3	2	-1	0	0
	x	4	0	14	9	-5	1	0
	x6	1	0	6	1	-2	0	1
Индексная строка	F(X)	-1	0	-2	-1	1	0	0

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6
1 : 1	1 : 1	3 : 1	2 : 1	-1 : 1	0 : 1	0 : 1
4-(1 * 0):1	0-(1 * 0):1	14-(3 * 0):1	9-(2 * 0):1	-5-(-1 * 0):1	1-(0 * 0):1	0-(0 * 0):1
1-(1 * 0):1	0-(1 * 0):1	6-(3 * 0):1	1-(2 * 0):1	-2-(-1 * 0):1	0-(0 * 0):1	1-(0 * 0):1
-1-(1 * 0):1	0-(1 * 0):1	-2-(3 * 0):1	-1-(2 * 0):1	1-(-1 * 0):1	0-(0 * 0):1	0-(0 * 0):1

В базисном столбце все элементы положительные.

Переходим к основному алгоритму симплекс-метода.

План	Базис	B	x1	x2	x3	x4	x5	x6	min
1	x1	1	1	3	2	-1	0	0	1/
	x5	4	0	14	9	-5	1	0	2/7
	x6	1	0	6	1	-2	0	1	1/6
Индексная строка	F(X1)	-1	0	-2	-1	1	0	0	0

Итерация №0. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления:

и из них выберем наименьшее:

min (1 : 3 , 4 : 14 , 1 : 6 ) = ¹/₆

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (6) и находится на пересечении ведущего столбца и ведущей строки.

Формируем следующую часть симплексной таблицы. Вместо переменной x в план 1 войдет переменная x₂ .

Строка, соответствующая переменной x₂ в плане 1, получена в результате деления всех элементов строки x₆ плана 0 на разрешающий элемент РЭ=6

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₂ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₂ и столбец x₂ .

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.

НЭ = СЭ - (А*В)/РЭ

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

B	x 1	x 2	x 3	x 4	x 5	x 6
1-(1 * 3):6	1-(0 * 3):6	3-(6 * 3):6	2-(1 * 3):6	-1-(-2 * 3):6	0-(0 * 3):6	0-(1 * 3):6
4-(1 * 14):6	0-(0 * 14):6	14-(6 * 14):6	9-(1 * 14):6	-5-(-2 * 14):6	1-(0 * 14):6	0-(1 * 14):6
1 : 6	0 : 6	6 : 6	1 : 6	-2 : 6	0 : 6	1 : 6
-1-(1 * -2):6	0-(0 * -2):6	-2-(6 * -2):6	-1-(1 * -2):6	1-(-2 * -2):6	0-(0 * -2):6	0-(1 * -2):6

План	Базис	B	x1	x2	x3	x4	x5	x6	min
2	x1	1/2	1	0	11/2	0	0	-1/2	1/3
	x5	12/3	0	0	62/3	-1/3	1	-21/3	1/4
	x2	1/6	0	1	1/6	-1/3	0	1/6	1
Индексная строка	F(X2)	-2/3	0	0	-2/3	1/3	0	1/3	0

Итерация №1. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления:

и из них выберем наименьшее:

min (¹/₂ : 1¹/₂ , 1²/₃ : 6²/₃ , ¹/₆ : ¹/₆ ) = ^?

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (6²/₃) и находится на пересечении ведущего столбца и ведущей строки.

Формируем следующую часть симплексной таблицы.

Вместо переменной x в план 2 войдет переменная x₃ .

Строка, соответствующая переменной x₃ в плане 2, получена в результате деления всех элементов строки x₅ плана 1 на разрешающий элемент РЭ=6²/₃

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₃ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₃ и столбец x₃ .

Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (6²/₃), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6
1/2-(12/3 * 11/2):62/3	1-(0 * 11/2):62/3	0-(0 * 11/2):62/3	11/2-(62/3 * 11/2):62/3	0-(-1/3 * 11/2):62/3	0-(1 * 11/2):62/3	-1/2-(-21/3 * 11/2):62/3
12/3 : 62/3	0 : 62/3	0 : 62/3	62/3 : 62/3	-1/3 : 62/3	1 : 62/3	-21/3 : 62/3
1/6-(12/3 * 1/6):62/3	0-(0 * 1/6):62/3	1-(0 * 1/6):62/3	1/6-(62/3 * 1/6):62/3	-1/3-(-1/3 * 1/6):62/3	0-(1 * 1/6):62/3	1/6-(-21/3 * 1/6):62/3
-2/3-(12/3 * -2/3):62/3	0-(0 * -2/3):62/3	0-(0 * -2/3):62/3	-2/3-(62/3 * -2/3):62/3	1/3-(-1/3 * -2/3):62/3	0-(1 * -2/3):62/3	1/3-(-21/3 * -2/3):62/3

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план. Окончательный вариант симплекс-таблицы:

План	Базис	B	x1	x2	x3	x4	x5	x6
3	x1	1/8	1	0	0	3/40	-9/40	1/40
	x3	1/4	0	0	1	-1/20	3/20	-7/20
	x2	1/8	0	1	0	-13/40	-1/40	9/40
Индексная строка	F(X3)	-1/2	0	0	0	3/10	1/10	1/10

Оптимальный план можно записать так:

x₁ = ¹/₈

x₃ = ¹/₄

x₂ = ¹/₈

F(X) = 1*¹/₈ + 1*¹/₄ + 1*¹/₈ = ^?

Составим двойственную задачу к прямой задаче.

y₁ + 5y₂ + 2y₃?1

3y₁ + y₂?1

2y₁ + y₂ + 3y₃?1

y₁ + y₂ + y₃ => max

y₁ ? 0

y₂ ? 0

y₃ ? 0

Решение двойственной задачи дает оптимальную систему оценок ресурсов.

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

Из теоремы двойственности следует, что Y = C*A^-1.

Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу А^-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных

Тогда Y = C*A^-1 =

Оптимальный план двойственной задачи равен:

y₁ = ³/₁₀

y₂ = ¹/₁₀

y₃ = ¹/₁₀

Z(Y) = 1*³/₁₀+1*¹/₁₀+1*¹/₁₀ = ^?

Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:

pi = g*xi; qi = g*yi.

Цена игры: g = 1 : ¹/₂ = 2

p1 = 2 * ¹/₈ = ¹/₄

p2 = 2 * ¹/₈ = ¹/₄

p3 = 2 * ¹/₄ = ¹/₂

q1 = 2 * ³/₁₀ = ³/₅

q2 = 2 * ¹/₁₀ = ¹/₅

q3 = 2 * ¹/₁₀ = ¹/₅

Размещено на Allbest.ru