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

 

Оглавление

 

 

 

 

 

 

 

 

 

 

 

Задание № 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	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