Применение ЭВМ в электроэнергетике: Текст лекций. Медведева С.Н. - 26 стр.

                                                  4         2            3          -38
                                                                                                              Начинается распределение по методу северно-западного угла с верхней
Решение в правом столбце: х8=3 х2=2 х7=2 х1=2 х3=6                                                            левой клетки. Первый потребитель требует 20 единиц груза. С
Остальные переменные – нулевые: х4=0 х5=0 х6=0                                                                одинаковой стоимостью груз можно перевезти от 1 и 2 поставщиков.
Минимум ЦФ = 38 (см. в табл. и подставив в равенство)                                                         Пусть взяли груз от первого поставщика. Тогда от 2 и 3-го поставщиков
                                                                                                              берем по 0 груза. Второй потребитель может взять с самой дешевой
                                                                                                              стоимостью перевозки от 1 поставщика только 40 единиц груза,
    Транспортная задача. Частный случай ЗЛП, т.е. формулируется                                               остальные потребители от 1 поставщика уже ничего не возьмут, т.к.
следующим образом: найти неотрицательные переменные x1 , x2 ,..., x n ,                                       резерв 1 поставщика исчерпан.
                                                                                                              2-й потребитель недостающие 70 единиц груза возьмет от 3 поставщика,
удовлетворяющие заданной системе ограничений
                                                                                                              т.к. у него стоимость дешевле. Оставшиеся 30 единиц груза у 3-го
       n
                                                                                                              поставщика выгоднее взять 4 потребителю, недостающий остаток в 80
      ∑ x ji = M i ,         i =1..m,
                                                                                                              единиц он возьмет у 2-го поставщика. Тогда 3-й потребитель получит
      j =1
      m                                                                                                       свой груз у 2-го поставщика. В такой раскладке ЦФ=790.
      ∑ x ji = N j ,         j =1..n                                                                               Возможный вариант начала со 2 поставщика (перемена строк)
      i =1
                                                                    n m
                                                                                                                           Запросы
при     которых             целевая     функция       F ( X ) = ∑∑ rij xij принимала                     бы           потребителей
                                                                    j =1i =1                                                             20             110            40            110
минимальное значение.                                                                                         возможности
                                                                                                              поставщиков
           m         n
Если    ∑ M i = ∑ N j , то транспортная задача называется закрытой.                                                                  1              2              5             3
                                                                                                                       60
        i =1         j =1                                                                                                                      0              50            0              10
    Типичная транспортная задача – задача перевозок. Допустим,                                                                       1              6              5             2
                                                                                                                      120
имеются 3 поставщика и 4 потребителя, известны стоимости перевозок                                                                             20             0             0          100
груза от любого поставщика к любому потребителю. Это удобно                                                                          6              3              7             4
                                                                                                                      100
показать в виде таблицы:                                                                                                                       0              60            40             0

                    Запросы                                                                                   Здесь ЦФ=810. Лучше вариант 1.
               потребителей
                                        20            110                      40             110
возможности                                                                                                   Оценим вариант такой перестановки столбцов
поставщиков
                                1                 2                  5                    3                                Запросы
               60                                                                                                     потребителей
                                             20             40                      0               0
                                                                                                                                         110            20             40            110
                                1                 6                  5                    2                   возможности
               120
                                             0                  0                   40              80        поставщиков
                                6                 3                  7                    4                                          2              1              5             3
               100                                                                                                     60
                                             0              70                      0               30                                         60             0             0              0