Задачи по "Математическому моделированию экономике"

 

     3. "Линейный тест". В матрице  назначений провести минимальное  число линий (горизонталей (по  строкам) и/или вертикалей (по  столбцам)), вычеркивающих все нулевые  ячейки матрицы. Если минимальное число вычеркнутых строк и столбцов равно n, оптимальное решение найдено, т.к. назначения должны быть произведены в "пункты", соответствующие нулевым ячейкам матрицы. В противном случае, если минимальное число вычеркнутых строк и столбцов < n, перейти к шагу 4.

 

     Число линий, вычеркивающих все нулевые  ячейки, равно 5; т.к.n = 6, переходим к шагу 4.

     4. Среди невычеркнутых строк и  столбцов найти ячейку с наименьшим значением. Вычесть это значение из содержимого всех невычеркнутых ячеек и добавить это значение к содержимому всех ячеек, находящихся на пересечении линий.

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

 
 

     Повторяем шаг 3.

     Оптимальное решение, найденное с помощью "линейного" теста.

 

     Ответ:

Кандидату 1 – работу В с временем выполнения в 1 условную единицу. 

Кандидату 2 – работу C с временем выполнения в 2 условную единицу.        

Кандидату 3 – работу E с временем выполнения в 1 условную единицу.        

Кандидату 4 – работу F с временем выполнения в 2 условную единицу.        

Кандидату 5 – работу A с временем выполнения в 1 условную единицу.        

Кандидату 6 – работу D с временем выполнения в 2 условную единицу.        

Суммарная стоимость равна 9 условных единиц.

 

      4. Найти оптимальный план перевозок по критерию минимума транспортных затрат на основе следующих данных: А – вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза. Задачу решить двумя методами получения начального распределения.

     А = (50; 20; 75; 80)         В = (40; 50; 15; 75; 40)

                         1       2    3   2,5    3,5

            С =      0,4    3    1    2       3

                        0,7    1    1   0,8    1,5

                        1,2    2    2   1,5    2,5

     Составим  условие задачи в виде таблицы: 

    В данном случае Σai=225 >Σbj=220 => имеем  дело с открытой моделью транспортной задачи. Сведем ее к закрытой введением фиктивного магазина B6 с потребностью b5=225-220=5 и стоимостью перевозок сi6=0.

    Имеем таблицу: 

    Математическая  модель: обозначим xij – количество товара, перевозимого из Аi в Bj.  
 
 

    Тогда:

                 x11 x12 x13 x14 x15 x16

                x21 x22 x23 x24 x25 x26

    X =      x31 x32 x33 x34 x35 x36      - матрица перевозок. 

                x41 x42 x43 x44 x45 x46

    min(x11+2x12+3x13+2,5x14+3,5x15+0,4x21+3x22+x23+2x24+3x25+0,7x31+x32+x33+0,8x34+1,5x35++1,2x41+2x42+2x43+1,5x44+2,5x45)                    (1)

     x11+x12+x13+x14+x15+x16=50

    x21+x22+x23+x24+x25+x26=20

    x31+x32+x33+x34+x35+x36=75

    x41+x42+x43+x44+x45+x46=80

    x11+x21+x31+x41=40                                                                                   (2)

    x12+x22+x32+x42=50

    x13+x23+x33+x43=15

    x14+x24+x34+x44=75

    x15+x25+x35+x45=40

    x16+x26+x36+x46=5 

    xij≥0 (i=1,2,3,4 ; j=1,2,3,4,5,6 )                                                                     (3) 

    Двойственная  ЗЛП:

    max(50u1+20u2+75u3+80u4+40v1+50v2+15v3+75v4+40v5+5v6)           (1*)

     u1+v1≤1 

    u1+v2≤2 

    u1+v3≤3                                                                                                        (2*)

    u1+v4≤2,5

    u1+v5≤3,5

    u1+v6≤0  

    ui,vj – произвольные (i=1,2,3,4 ; j=1,2,3,4,5,6 ) (3*)

    Будем искать первоначальный план по методу наименьшей стоимости:

1. x21=20 и 2-ую строку исключаем.
2. 2) x31=20 и 1-ый столбец исключаем.
3. x34=55 и 3-ю строку исключаем.

4) x44=20 и 4-ый столбец исключаем.

4. x12=50 и 1-ю строку и 2-ой столбец исключаем и x32=0.
5. x43=150 и 3-ий столбец исключаем.

7) x45=40 и 5-ый столбец исключаем.x46=5.

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