Расчет матрицы перевозимых объемов грузов при известной матрице стоимостей перевозок, доставляющую минимум целевой функции

Алгоритм транспортной задачи

Математическую модель транспортной задачи можно записать в следующем виде.

Найти матрицу перевозимых объемов грузов X = (xij) при известной матрице стоимостей перевозок C = (cij), доставляющую минимум целевой функции

                               n   m

                       F =  S  S cij xij

                              i=1 j=1

смен формулу при следующих ограничениях.

1. Все грузы должен быть вывезены

n

    S  xij = ai( i = 1, m; ai ³ 0 )  .

                          j=1

2.           Все потребности должны быть удовлетворены

m

    S  xij = bj( j = 1, n; bj ³ 0 )  .

                          i=1

3.           Движение грузов должно происходить от пунктов отправления к пунктам назначения

xij ³ 0  ( i = 1, m; j = 1, n )   .

4.           Выполнено условие сбалансированности, или, по-другому, замкнутости задачи

m                n

    S  ai = S bj .

                         i=1              j=1

Контрольный пример

                         Т Р А Н С П О Р Т Н А Я  З А Д А Ч А

                  Таблица - Транспортная задача

               ============================================================

               |     Наименование показателя                |  Величина   |

               |==========================================================|

               |     ВХОДНЫЕ ДАННЫЕ                         |             |

               | Целевая функция                            |Максимальная |

               | Количество поставщиков                     |           4 |

               | Количество потребителей                    |           6 |

               ============================================================

                                                    Т а б л и ц а  -  З а п а с

=====================================================================================================

|    1    |    2    |    3    |    4    |    5    |    6    |    7    |    8    |    9    |   10    |

           =====================================================================================================

     20.0      30.0      40.0      10.0

=====================================================================================================

                                                    Т а б л и ц а  -  С п р о с

=====================================================================================================

|    1    |    2    |    3    |    4    |    5    |    6    |    7    |    8    |    9    |   10    |

=====================================================================================================

     17.0      15.0      12.0       8.0       3.0       4.0

           =====================================================================================================

                                 Т а б л и ц а  -  С т о и м о с т ь  п е р е в о з к и

===========================================================================================================

|  №  |    1    |    2    |    3    |    4    |    5    |    6    |    7    |    8    |    9    |   10    |

===========================================================================================================

   1        2.0       3.0       4.0       2.0       1.0       3.0

   2        2.0       4.0       1.0       1.0       2.0       1.0

   3        3.0       1.0       1.0       4.0       2.0       1.0

   4        1.0       1.0       2.0       2.0       2.0       3.0

===========================================================================================================

                       Таблица - Транспортная задача

               ============================================

               | Поставщик | Потребитель |   Количество   |

               |==========================================|

               |           |             |                |

               |      1    |      3      |        12.0000 |

               |      1    |      6      |         4.0000 |

               |           |             |                |

               |      2    |      2      |        15.0000 |

               |      2    |      5      |         3.0000 |