Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
|
[1] Оглавление [2] Задание № 1 [3] Задание № 2 [4] Задание № 3 [5] Вывод |
Данные для задачи № 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
Сформулировать математическую постановку и решить следующую транспортную задачу. На трех складах поставщиков нефтепродуктов А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 |
В3 |
В4 |
Запасы у поставщиков |
|
|
А1 |
1 100 |
7 |
4 150 |
4 150 |
400 |
|
А2 |
4 |
1 200 |
6 |
7 |
200 |
|
А3 |
2 |
2 |
9 |
6 150 |
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
|
В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 |
Найти наилучшее решение задачи принятия решений в условиях частичной неопределенности методом теории матричных игр.
Требуется:
Решение для задачи № 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.
В ходе работы была решена задача линейного программирования, транспортная задача и задача по принятию решений в условиях неопределенности.
PAGE 16