Экономико-математические модели задач о назначениях

матрице (17) выделим независимые нули, построив цепочку (под­черкнутые нули). Работник А закреплен за работой 2, В — за работой IV) С — за работой III, D — за работой I. Оценка С_мах = 7 + 13 + 14 + 10 = 44 [2,c.252-256].

Вывод: задачи о назначении ставятся, в основном, как задачи линейного и дискретного программирования. И то и другое предполагает задание целевой функции и ограничений в линейной форме. Задачи о назначении – это одна из особенностей в моделировании задач распределения разных типов.

ПРАКТИЧЕСКАЯ  ЧАСТЬ

Вариант 8. Задача 1. Решить симплекс-методом:

                                                      Канонический вид:

Max z=X1+X2                                           Max z=X1+X2+0X3+0X4

3X1+2X25                                 3X1+2X2+X3=5

X22                                            X2+X4=2

Xi0;

* - ключевые столбец и строка

** - ключевое число

Ответ: X1=0,33;  X2=2;  Z(X)=2,33

Задача 2.  Решить симплекс-методом:

                                                                                  Канонический вид:

Min z=X1+X2                         Min z=X1+X2                           Min z=X1+X2+0X3+0X4

3X1+2X25                    -3X1-2X2-5                      -3X1-2X2+X3=-5

X22                                -X2 -2                              -X2+X4=-2

Xi0;

           * - ключевые столбец и строка

** - ключевое число

Ответ: X1=0,33;  X2=2;  Z(X)=2,33

Задача 3. Решить симплекс-методом с искусственным базисом:

                                                 Канонический вид:

MaxZ=7X1+2X2+3X3                   MaxZ=7X1+2X2+3X3+0S1+0S2+0S3+0S4                

          7X1+2X2+3X318                    7X1+2X2+3X3+S1=18

          4X1+3X210                             4X1+3X2+S2=10

          2X1+3X2+X39                        2X1+3X2+X3-S3=9

          X1+X2+X35                            X1+X2+X3-S4=5

          X10

                               M – задача:

                     MaxZ=7X1+2X2+3X3+0S1+0S2+0S3+0S4-MR1-MR2  

                                               7X1+2X2+3X3+S1=18

                                 4X1+3X2+S2=10

                                 2X1+3X2+X3-S3+R1=9

                                 X1+X2+X3-S4+R2=5                                        Таблица 1

                                                                                                          Таблица 2

                                                                                                     Таблица 3

                                                                                      Таблица 4

                                                                 Таблица 5

                                                        Таблица 6

* - ключевые столбец и строка   

** - ключевое числo

Ответ:  X1= -10,52;   X3=30,57 ;   Z(X)=18,07

Задача 4. Решить симплекс-методом с искусственным базисом:

                                                                Канонический вид:

Min z=6X1+5X2+X3                           Min z=6X1+5X2+X3+0S1+0S2+0S3                          

      7X1+2X2+4X321                          7X1+2X2+4X3+S1 =21

      5X1+3X2+X315                            5X1+3X2+X3+S2=15

      3X1+X2+4X39                              3X1+X2+4X3-S3=9

                                          M – задача:

                              Min z=6X1+5X2+X3+0S1+0S2+0S3 +MR1 

                                                         7X1+2X2+4X3+S1 =21

                                                        5X1+3X2+X3+S2=15

                                                        3X1+X2+4X3-S3+R1=9                             Таблица 1

                                                                                         Таблица 2

                                                                                                             Таблица 3

Задача 6.

Для производства 4 видов продукции затрачивается 3 вида ресурсов А, В, С. Затраты ресурсов на 1-цу продукции – в таблице. Известно, что от реализации 1-го вида продукции предприятие получает прибыль 3 рубля, 2-го – 4, 3-го – 3, 4-го – 1 рубль. Определить какие виды продукции предприятие должно производить и в каком объёме, чтобы получить максимум дохода, если предприятие затрачивает ресурса А – 12 единиц, В – 8 единиц, С – 48 единиц.

Виды продукции – х

Прибыль от 1-го вида продукции составит 3Х1, прибыль от 2-го вида продукции составит 4Х2,  прибыль от 3-го вида продукции составит 3Х3, прибыль от 4-го вида продукции составит 1Х4. Эта величина должна быть максимизирована.

Max Z=3X1+4X2+3X3+X4

Если затраты ресурса А на 1 - го вида продукцию составляет 3 единицы, 3 – го - 2 единицы, 4 – го – 1 единицу, то сопоставляя общие затраты ресурса А с наличными ресурсами можно записать следующее:

3X1+2X3+X412

Аналогично записываем ограничения и для 2 – х других ресурсов:

X1+2X2+4X48

3X1+5X2+4X3+2X448

Переменные Х не могут быть отрицательными по смыслу, значит:

X10;  X20;   X30;  X40

Таким образом, описанную выше экономическую ситуацию, можно записать в виде следующей модели линейного программирования в раз­вернутом виде:

Найти X1, X_{2, X3,} X40 максимизирующие функции 3X1+4X2+3X3+X4= Z, при огра­ничениях:

3X1+2X3+X412

X1+2X2+4X48

3X1+5X2+4X3+2X448

Cо­кращенная форма модели:

Xj - количество продукции j-ro вида, где j = 1 ...n;

Pj - прибыль от реализации продукции j-ro вида;

А_ij - нормы затрат сырья i-ro вида на единицу продукции j-ro вида;

S _i - запасы сырья i-ro вида (i = 1.. .m).

Тогда математическая модель задачи распределения за­пишется следующим образом:

Z=

Задача 7.

В смесь должно входить не менее 12 единиц вещества А, 21 единицы вещества В и 32 единицы вещества С. Вещества содержатся в 3-х продуктах в следующих пропорциях: в 1-ом продукте вещества А – 1 единица, вещества В – 3 единицы и вещества С – 4 единицы; во 2-ом продукте, соответственно, 1 – 2 – 3 и в 3-ем продукте – 2 – 1 – 2 . B каком количестве должны входить продукты в смесь, чтобы стоимость её была минимальной, если учесть, что весовая единица 1-го продукта стоит 20 рублей, 2-го – 20 рублей, 3-го – 10 рублей.

Продукты – Х, стоимость стремится к минимуму.

Тогда функция цели может быть записана так:

Z= 20X1+20X2+10X3 min

Ограничения по содержанию необходимых веществ:

X1+X2+2X312  - по веществу А

3X1+2X2+X321    - по веществу B

4X1+3X2+2X332   - по веществу C

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

В общем виде математическую модель задачи о смесях можно записать следующим образом:

Z=

при ограничениях:

 - ограничения на содержание необходимых веществ

    Aij - содержание j-ro вещества в единице i-ro продукта;

Yj - необходимое содержание j-ro вещества в продукте.    

Транспортная задача.

В 3-х пунктах отправления (на складах) находится соответственно 100,80,120т горючего. В пункты назначения требуется доставить соответственно 60,140,100т горючего. Стоимость перевозки тонны горючего из пункта а1 в пункты b1, b2, b3 соответственно 4,5,1 ден. ед., из пункта а2 – 6,3,4 ден. ед., а из пункта а3 – 3,2,4 ден. ед. Составить оптимальный план перевозок горючего так, чтобы общая сумма транспортных расходов была оптимальной.

Исходный опорный план

          Определение первоначального допустимого плана методом ”северо-западного угла”.                                                                                  Таблица 1

                                                                                                               Таблица 2

a1=0,  а1+с11= b1=1,  а1+с13= b3=7,  b3- с33= а3= 3,  а3+с34= b4= 11, b3- с23= а2= -1

а1+с12= b2=4

а1+с14 b4               0+3< 11 – не выполняется

а2+с21 b1               -1+7> 1 –  выполняется

а2+с22 b2               -1+6> 4 -  выполняется

а2+с24 b4               -1+9< 11 - не выполняется

а3+с31 b1               3+7> 1 -  выполняется

а3+с32 b2               3+2> 4 -  выполняется

Z=1860                                                                                    Таблица 3      

a1=0, а1+с11= b1=1, а1+с12= b2=4, а1+с14= b4= 3, b4- с34= а3=-5,  а3+с33= b3= -1,

b3- с23= а3=-9

а1+с13 b3               0+7> -1 –  выполняется

а2+с21 b1               -9+7< 1 – не  выполняется

а2+с22 b2               -9+6< 4 - не выполняется

а2+с24 b4               -9+9< 3 - не выполняется

а3+с31 b1               -5+7> 1 -  выполняется

а3+с32 b2               -5+2< 4 - не выполняется

Z=1650                                                                                  Таблица 4  

a1=0,  а1+с11= b1=1,  а1+с14= b4=3, b4- с34= а3= -5, а3+с33= b3= -1,  b3- с23= а2= -9

а2+с22= b2=-3

а1+с12 b2                  0+4>-3 - выполняется

а1+с13 b3                   0+7>-1 -  выполняется        

а2+с21 b1                   -9+7<1 -не выполняется  

а2+с24 b2                   -9+9<3 - не выполняется

а3+с31 b1                   -5+7>1 -  выполняется

а3+с32 b2                   -5+2=3 -  выполняется

Z=1480                                                                                  Таблица5        

a1=0,а1+с11=b1=1, b4- с24= а2= -6, а2+с22= b2=0, b2- с32=а3=-2, а2+с23=b3=2

а1+с14=b4=3,

а1+с12 b2                 0+4>0 – выполняется

а1+с13 b3                 0+7>2 – выполняется

а2+с21 b1                 -6+7=1 -   выполняется

а3+с31 b1                 -2+7>1 -   выполняется

а3+с32 b2                 -2+2=0 -   выполняется

а3+с34 b4                 -2+8>3 -   выполняется

Z=1330

Количество базисных клеток должно быть на единицу меньше суммарного количества поставщиков и потребителей вместе взятых(m+n-1) m=3;