Транспортная задача. Филькин Г.В. - 4 стр.

UptoLike

ВУЗ: 

ИСОиП ДГТУ | Шахты

Составители: 

Рубрика: 

3
35
10 25
Виды циклов:
, , .
Решение задачи также как и задачи линейного программирования пред-
полагает вначале отыскание опорного плана, а затем отыскание оптималь-
ного.
Для отыскания опорного плана рассмотрим два метода:
1)
метод «северо-западного угла»
2)
метод наименьшей стоимости.
Метод «северо-западного угла».
Определить опорное решение для задачи, заданной таблицей:
B
A
40
25
20
50
60
5 4 1 2
40
4 2 6 3
35
7 3 5 4
Заполнение таблицы начинаем с клетки (1,1). Сравниваем a
1
=60 и
b
1
=40. Выбираем min {а
1
, b
1
} = 40. Это значение x
11
=40 записываем в пер-
вую клетку. Потребности первого потребителя В
1
полностью удовлетворе-
ны. Поэтому остальные клетки первого столбца мы уже заполнять не бу-
дем. У первого поставщика остались не вывезенными 60-40=20 единиц гру-
за.
Следующей для заполнения будет клетка (1,2) – вторая в первой стро-
ке. Заполняем её по min {25, 60-40} = 20. Таким образом, все запасы перво-
го поставщика будут вывезены, и остальные клетки первой строки
запол-
нять уже не нужно. 
                                              3



       35                   10            25



   Виды циклов:


                        ,                 ,                 .

   Решение задачи также как и задачи линейного программирования пред-
полагает вначале отыскание опорного плана, а затем отыскание оптималь-
ного.
   Для отыскания опорного плана рассмотрим два метода:
   1) метод «северо-западного угла»
   2) метод наименьшей стоимости.

                            Метод «северо-западного угла».

   Определить опорное решение для задачи, заданной таблицей:

                        B
                                 40           25       20           50
               A
                             5        4            1            2
                   60

                             4        2            6            3
                   40

                             7        3            5            4
                   35


    Заполнение таблицы начинаем с клетки (1,1). Сравниваем a1=60 и
b1=40. Выбираем min {а1, b1} = 40. Это значение x11=40 записываем в пер-
вую клетку. Потребности первого потребителя В1 полностью удовлетворе-
ны. Поэтому остальные клетки первого столбца мы уже заполнять не бу-
дем. У первого поставщика остались не вывезенными 60-40=20 единиц гру-
за.
    Следующей для заполнения будет клетка (1,2) – вторая в первой стро-
ке. Заполняем её по min {25, 60-40} = 20. Таким образом, все запасы перво-
го поставщика будут вывезены, и остальные клетки первой строки запол-
нять уже не нужно.

Страницы