Будь умным!


У вас вопросы?
У нас ответы:) SamZan.ru

Задание 1 [3] Задание 2 [4] Задание 3 [5] Вывод

Работа добавлена на сайт samzan.ru: 2016-03-30


Оглавление

[1] Оглавление

[2] Задание № 1

[3] Задание № 2

[4] Задание № 3

[5] Вывод

Задание № 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х12-3x3 -2x4

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

Х7 = 170 –2x1 -4 х2 x3x4

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.

Неосновные переменные –х1367.

Выразим новые основные переменные через неосновные (х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;

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

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

В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

Данные для задачи № 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.

Вывод

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

PAGE  16




1. Культура и природа
2. Задача 721 Проект замещения
3. РЕФЕРАТ НА ТЕМУ- ldquo;Етіологія та клінічні прояви холериrdquo; Холера choler особливо небезпечна
4. Экология Группа 113310 ПСФ Отчет по лабораторной работе 4 по дисциплине ЗН и ХО а ЧС РБ ОПРЕДЕЛ
5.  Поставь пальчик на камыши
6. Практика возведения таможенных барьеров во внешнеэкономических отношениях привела в XX в
7. на тему- Государственный кредит Преподаватель Работу выполнила Финансовокредитный
8. Реферат- Організація підприємства дрібнооптової торгівлі ХОДАК
9. Стол для пайки 2 Вытяжная вентиляция 3 Приточная вентиляция
10. Стаття 3 Конституції України проголошує що людина її життя та здоров~я честь і гідність недоторканність і б
11. ФОРМЫ ОПИСАНИЯ ИНСТИТУТОВ И ИНСТИТУЦИОНАЛЬНЫХ ИЗМЕНЕНИЙ Как было показано в предыдущей главе одной из ба
12.  Проблема защиты информации
13. Роман ИС Тургенева Образ Базарова
14. Пер. с. англ. С. Потапенко
15. Vsemeissledovniyopyit-vliynievneshnihfktorovn
16. і м~ліктік ж~не жеке м~ліктік емес ~атынастар Азаматты~ ы~ты~ ы~ саласы ретінде негізгі реттеу т~
17. по теме- Самоменеджмент и имидж руководителя План семинарского заняти.html
18. завязать Я уже достаточно выпил в своей жизни
19. Реферат на тему- Поведінка медичного працівника з хворими Міжособистісні стосунки між лікарем та хвори
20. Честным Твоим крестом Христе- диавола посрамил еси- и воскресением Твоим жало греховное притупил еси- и с