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

Задание № 1

матричный игра двойственный транспортный

Данные для задачи № 1

Решение задач линейного программирования.

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

Тип сырья	Нормы расхода сырья на одно изделие	Запасы сырья
	А	Б	В	Г
1	2	1	3	2	200
2	1	2	4	8	160
3	2	4	1	1	170
Прибыль от реализации изделия	5	7	3	6

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

Требуется:

1) сформулировать математическую модель задачи линейного программирования;

2) решить задачу линейного программирования симплекс-методом;

3) решить задачу в программной среде MATLAB;

4) составить двойственную задачу, найти её решение.

Решение задачи № 1

Математическая модель:

Z=5x1 + 7x2+3x3+6x4 max

2x1 + x2+3x3 + 2x4 ? 200

x1 + 2x2 + 4x3 +8x4 ? 160

2x1 + 4x2 + x3 + x 4 ? 170

Применение симплекс-метода

2x1 + x2+3x3 + 2x4 = 200

x1 + 2x2 + 4x3 +8x4 = 160

2x1 + 4x2 + x3 + x 4 = 170

Z=5x1 + 7x2+3x3+6x4

1 шаг Вводим новые переменные:

Основные переменные - х5, х6, х7.

Неосновные переменные - х1, х2, x3, x4.

Выразить основные переменные через неосновные:

Х5 = 200 - 2х1 -х2-3x3 -2x4

Х6 = 160 -х1 -2 х2 -4x3-8x4

Х7 = 170 -2x1 -4 х2 -x3 -x4

Z=5x1 + 7x2+3x3+6x4

Х1 = (0, 0, 0, 0, 200, 160,170)

Шаг 2: Вводим ограничения для х2:

Х5 = 200 - х2 ? 0 х2 ? 200

Х6 = 160 - 2х2 ? 0 х2 ? 80

Х7 = 170 - 4х2 ? 0 х2 ? 42,5 - min => x7 в неосновной., x2 в основной.

Оcновные переменные - х2, х5, х6.

Неосновные переменные - х1, x3, x4, x7.

Выразим новые основные переменные через неосновные (х2 выражаем из урав-ия х7:

х2 = 85/2-x1/2-x3/4-x 4/4-x7/4

х5 = 315/2 -3/2* х1 - 11/4*х3-7/4*x4-x7/4

х6 = 75 - 7/2*х3 -15/2* х4 +x7/2

Z= 595/2+3/2*x1+ 5/4*x3 + 17/4*x4 +7/4*x7

Х2 = (0, 85/2, 0, 0, 315/2,75,0)

Шаг 3: Вводим ограничения для х4

Х2 = 85/2-1/4*х4 ? 0 х4 ? 170

Х6 = 75 - 15/2*х4 + х5 ? 0 х4 ? 10 - min=> x6- неосновная переменная, х4 основная

Х5= 315/2-7/4*х4?0 х4 ? 90

Оcновные переменные - х2, х4, х5.

Неосновные переменные -х1+х3+х6+х7.

Выразим новые основные переменные через неосновные (х4 из х6:

Х4 = 10 - 7/15*х3 -2/15x6 +1/15*x7

Х2 = 40-1/2*x1-2/15*x3-1/30*х6 - 4/15* х7

Х5 = 140 - 3/2*х1 - 29/15*х3+ 7/30*x6+2/15x7

Z= 340+ 3/2*х1 - 11/15*х3+ 1 7/30*x6+22/15x7

Х3 = (0, 40, 0, 10, 140, 0, 0)

Шаг 4: Вводим ограничения х1

Увеличение за счет х5, так как коэффициент положительный.

х2 =40-1/2* х1 ? 0 x1 ? 80 - min=> x2 в неосновной, х1 в основной

х5 = 140 - 3/2*х1 ? 0 x1? 280/3

5 шаг

Оcновные переменные - х1, х4, х5.

Неосновные переменные - х2, х3, х6, х7.

Выразим основные переменные через неосновные(х1из х2) :

Х1 = 80-2х2 -4/15*х3 + 1/15*х6-8/15х7

Х5 = 20+-3х2 -23/15*х3 + 2/15*х6-14/15х7

Х4 = 10 -7/15*х3 + 2/15*х6-1/15х7

Z= 460-3x2-17/15*х3 + 7/15*х6-34/15х7

Х4 = (80, 0, 0, 10, 20, 0,0)

X1=80

X2=0

X3=0

Z=5*80+7*0+3*0+6*10=460

Реализация в программной среде MATLAB задачи № 1

Код

clc;

f=[5 7 3 6];

f=-f;

A=[2 1 3 2

1 2 4 8

2 4 1 1];

b=[200;160;170];

lb=[0 0 0 0];

X=linprog(f,A,b,[],[],lb,[]);

disp(X);

fd=-f*X;

disp(fd);

Решение

Optimization terminated.

80.0000

0.0000

0.0000

10.0000

460.000

Результаты идентичны, следовательно, задача решена верно.

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

Код

clc;

f=[200 160 170];

A=[2 1 2

1 2 4

3 4 1

2 8 1];

A=-A;

b=[5;7;3;6];

b=-b;

lb=[0 0 0];

X=linprog(f,A,b,[],[],lb,[]);

disp(X);

fd=-f*X;

disp(fd)

Решение

Optimization terminated.

0.0000

0.4667

2.2667

460.0000

Задание № 2

Данные для задачи № 2

Сформулировать математическую постановку и решить следующую транспортную задачу. На трех складах поставщиков нефтепродуктов А1, А 2 и А3 находится по 400, 200 и 150 тонн нефтепродуктов соответственно. Перевозка одной тонны продуктов со склада А1 в пункты В1, В2, В3 и В4 потребеителей соответственно стоит с11, с12, с13, с14 у.е., перевозка одной тонны со склада А2 в те же пункты соответствено с21, с22, с23, с24 у.е., а перевозка одной тонны со склада А 3 в те же пункты соответственно с31, с32, с33, с34 (см. таблицу «Стоимость перевозки»). В пункты В1, В2, В3 и В4 надо доставить по 100, 200, 150, 300 тонн нефтепродуктов соответственно.

Таблица «Стоимость перевозки»

С11	1
С12	7
С13	4
С14	4
С21	4
С22	1
С23	6
С24	7
С31	2
С32	2
С33	9
С34	6

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

Требуется:

1) решить задачу методом потенциалов;

2) решить задача в программной среде MATLAB;

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

Метод наименьшего элемента в столбце:

	В1	В2	В3	В4	Запасы у поставщиков
А1	1 100	7	4 150	4 150	400
А2	4	1 200	6	7	200
А3	2	2	9	6150	150
Потребности потребителей	100	200	150	300

Z = 100*1 + 200*1 + 150*4 + 150*4 + 150*6= 2400 т/км

Метод потенциалов

u1 + v1 = 1 Предположим, что u1 = 0,

u2 + v2 = 1 тогда v1 = 1

u1 + v3= 4 v3 = 4

u1 + v4 = 4 v4 = 4

u3 + v4 = 6 u3 = 2

u3 + v4 = 2 u2=0

v2 = 1

Проверяем:

u1 + v2 ? 7 0 + 1 ? 7 - верно

u2 + v1 ? 4 0 + 1 ? 4 - верно

u2 + v3 ? 6 0 + 4 ? 6 - верно

u2 + v4 ? 7 0 + 4 ? 7 - верно

u3 + v1 ? 2 2 + 1 ? 2 - неверно

u3 + v3 ? 9 2 + 4 ? 9 - верно

-100 +150 0 250

0 -150 100 50

	В1	В2	В3	В4	Запасы у поставщиков
А1	1	7	4 150	4 250	400
А2	4	1 200	6	7	200
А3	2 100	2	9	6 50	150
Потребности потребителей	100	200	150	300

Z= 100*2 +200*1+150*4+250*4+50*6=2300

U1+V3=4 Пусть U1=0, тогда

U1+V4=4 V3=4

U2+V2=1 V4=4

U3+V1=2 V2=0

U3+V4=6 U2=1 U3=2 V1=0.

Проверяем:

U1+V1?1 0+0?1 - верно

u1+v2?7 0+0?7 - верно

U2 + V1? 4 1+0?4 - верно

U2+V3?6 1+4?6 - верно

U2+V4 ?7 1+4?7 - верно

U3+V2?2 2+0?2 - верно

U3+V3?9 2+4?9 - верно

Реализация в программной среде MATLAB задачи № 2

Код

clc;

f=[1 7 4 4 4 1 76 7 2 2 9 6];

Aeq=[1 1 1 1 0 0 0 0 0 0 0 0

0 0 0 0 1 1 1 1 0 0 0 0

0 0 0 0 0 0 0 0 1 1 1 1

1 0 0 0 1 0 0 0 1 0 0 0

0 1 0 0 0 1 0 0 0 1 0 0

0 0 1 0 0 0 1 0 0 0 1 0

0 0 0 1 0 0 0 1 0 0 0 1];

beq=[400 200 150 100 200 150 300];

lb=[0 0 0 0 0 0 0 0 0 0 0 0];

x=linprog (f,[],[],Aeq,beq,lb,[]);

disp(x);

fopt=f*x;

disp(fopt)



Результаты идентичны, следовательно задача решена верно.

Задание № 3

Данные для задачи № 3

	В1	В2	В3	В4	В5
А1	32	32	37	31	33
А2	29	40	34	33	34
А3	21	32	31	30	35
А4	35	34	25	30	35
А5	20	28	31	21	36

Найти наилучшее решение задачи принятия решений в условиях частичной неопределенности методом теории матричных игр.

Требуется:

1) Произвести упрощение платежной матрицы, упростив дублирующие и заведомо невыгодные стратегии (если таковые имеются);

2) Проверить, содержит ли матрица седловую точку;

3) Найти решение игры.

Решение для задачи № 3

Матричные игры - игры, где 2 игрока играют в игру с нулевой суммой, имея конечное число чистых стратегий и задан платеж второго игрока первому. Матрица задает выигрыш первого игрока и проигрыш второго.

	В1	В2	В3	В4	В5
А1	32	32	37	31	33
А2	29	40	34	33	34
А3	21	32	31	30	35
А4	35	34	25	30	35
А5	20	28	31	21	36

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

Реализация в программной среде MATLAB задачи № 3 Для игрока А

Код

f=[1 1 1 1 1];

A=[32 29 21 35 20

37 34 31 25 31

31 33 30 30 21];

A=-A;

b=[1;1;1];

b=-b;

lb=[0 0 0 0 0];

X=linprog(f,A,b,[],[],lb);

disp(X);

V=f*X;

disp(V);

Vopt=1/V;

disp(Vopt);

P=X*Vopt;

disp(P);

Оптимальным решением является 31 31,6000 33.

Реализация в программной среде MATLAB задачи № 3 для игрока В

Код

f=[1 1 1 ];

f=-f;

A=[32 37 31

29 34 33

21 31 30

35 25 30

20 31 21];

b=[1;1;1;1;1];

lb=[0 0 0];

X=linprog(f,A,b,[],[],lb);

disp(X);

V=-f*X;

disp(V);

Vopt=1/V;

disp(Vopt);

P=X*Vopt;

disp(P);

Оптимальным решением является 31 ? 31,6000 ? 33.

Вывод

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

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