лаба по лестридчеству. Лабораторная работа 2. Транспортная задача сведения из теории
![]()
|
ТРАНСПОРТНАЯ ЗАДАЧА 3.2. Сведения из теории Планирование перевозок грузов является важной экономической задачей, занимающей ключевое место среди других проблем планирования. Большое значение имеет задача о минимизации транспортных издержек при перевозках однородных грузов из пунктов производства в пункты потребления, например, древесины с нижних складов к деревообрабатывающим предприятиям, строительных материалов с баз на стройплощадки и т.п.Пусть ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Модель транспортной задачи называется закрытой (или сбалансированной), если суммарные запасы груза равны суммарным потребностям, т.е. ![]() Если это условие не выполняется, то модель называется открытой (или несбалансированной). Открытая модель легко сводится к закрытой путем введения фиктивного поставщика (если потребности превышают запасы) или фиктивного потребителя (если запасы превышают потребности). Поэтому мы ограничимся рассмотрением только закрытой модели. План перевозок транспортной задачи можно представить в виде матрицы ![]() ![]() ![]() ![]() ![]() ![]() ![]() Стоимость перевозки груза от ![]() ![]() ![]() Следовательно, суммарные транспортные расходы по плану ![]() |
Пункты отправления и запасы груза | Пункты назначения и потребности | |||||||
![]() | ![]() | … | ![]() | |||||
![]() | ![]() | … | ![]() | |||||
![]() | ![]() | | ![]() | | ![]() | … | | ![]() |
![]() | | ![]() | | ![]() | | |||
![]() | ![]() | | ![]() | | ![]() | … | | ![]() |
![]() | | ![]() | | ![]() | | |||
… | … | … | … | … | … | |||
![]() | ![]() | | ![]() | | ![]() | … | | ![]() |
![]() | | ![]() | | ![]() | |
3.3. Пример выполнения работы
Предположим, что запасы груза в пунктах отправления равны соответственно A1, A2 и A3 единиц. Потребности пунктов назначения составляют соответственно B1, B2, B3, B4, B5 единиц. Затраты на перевозку единицы груза (тарифы)
![](713906_html_342ca2c333965e7f.gif)
Вариант 1,7,13
![](713906_html_d304b389e49bf5c1.gif)
B: (100, 120, 110, 60, 50)
Вариант 2,8,14
![](713906_html_b04b3345b98d44b4.gif)
B: (100, 40, 100, 70, 130)
Вариант 3,9,15
![](713906_html_33cfb719c345dd91.gif)
B: (70, 100, 110, 100, 60)
Вариант 4,10,16
![](713906_html_2c6b7b6c2e99a357.gif)
B: (100, 70, 40, 120, 110)
Вариант 5,11,17
![](713906_html_c41f267e6593dd19.gif)
B: (50, 100, 100, 70,120)
Вариант 6,12,18
![](713906_html_33cfb719c345dd91.gif)
B: (100, 120, 110, 60, 50)
3.3.1. Таблица перевозок
Имеем транспортную задачу с тремя поставщиками и пятью потребителями, исходные данные которой можно представить в виде табл. 3.2.
Т а б л и ц а 3.2
-
Пункты отправления и запасы груза
Пункты назначения и потребности
120
100
110
70
40
200
3
2
4
6
7
160
2
3
1
2
6
80
5
4
7
6
3.3.2. Математическая модель
Определим сначала вид транспортной модели. Для этого вычислим сумарные запасы груза у поставщиков
![](713906_html_6e8088095732074e.gif)
и суммарные потребности
![](713906_html_5af82dbfaa952b.gif)
Так как
![](713906_html_d80c6d0fd4f88ec4.gif)
Суммарные транспортные затраты на перевозки груза от поставщиков к потребителям согласно (3.1) составляют
![](713906_html_50ad485c51bead3c.gif)
Ограничения (3.2) и (3.3) показывают, что все запасы должны быть вывезены от поставщиков
![](713906_html_d74ba317773e548f.gif)
и должны быть удовлетворены потребности пунктов назначения
![](713906_html_27b1b169d1f9e0db.gif)
Все поставки груза должны быть неотрицательными
![](713906_html_b06464151f70aa76.gif)
![](713906_html_1649e95a33acd05d.gif)
![](713906_html_6fedec2430d686ae.gif)
Соотношения (3.4)-(3.7) обрауют математическую модель транспортной задачи.
Замечание. Одно из уравнений системы (3.5)-(3.6) следует из остальных уравнений, и его можно опустить. Действительно, если сложить все уравнения (3.5) и из полученной суммы вычесть любые четыре уравнения системы (3.6), то получим пятое уравнение этой системы. Таким образом, одно из уравнений системы ограничений является линейной комбинацией остальных уравнений.
3.3.3. «Равномерный» план перевозок
В среде Excel на листе 1 в блоке ячеек B2 : F4 поместим тарифы на перевозки из табл. 3.2. Блок ячеек B7 : F9 предусмотрим для записи плана перевозок. В ячейки H7 : H9 запишем запасы груза у поставщиков, а в ячейки B11 : F11 – потребности пунктов назначения. Суммарные затраты на перевозку будем рассчитывать в ячейке G2, в которую поместим формулу
= СУММПРОИЗВ(B2 : F4; B7 : F9). Содержимое этой ячейки сначала равно нулю. Однако, постепенно заполняя ячейки B7 : F9 числами, содержимое ячейки G2 будет меняться в соответствии с формулой (3.2).
Чтобы получить «равномерный» план перевозок, запасы поставщика
![](713906_html_7348683d98838f5b.gif)
![](713906_html_7348683d98838f5b.gif)
![](713906_html_ea9e65f4b6b63dbd.gif)
![](713906_html_fad29eaca0b174c3.gif)
![](713906_html_dd8ddb18abb31cde.gif)
![](713906_html_738ee4e590e56995.gif)
![](713906_html_35ed619b343f65fa.gif)
Т а б л и ц а 3.3
| A | B | C | D | E | F | G | H |
1 | | Тарифы на перевозку груза | | | ||||
2 | | 3 | 2 | 4 | 6 | 7 | 1610 | |
3 | | 2 | 3 | 1 | 2 | 6 | | |
4 | | 5 | 4 | 7 | 6 | 8 | | |
5 | | "Равномерный" план перевозок | | | ||||
6 | | B1 | B2 | B3 | B4 | B5 | | Запасы |
7 | A1 | 40 | 40 | 40 | 40 | 40 | | 200 |
8 | A2 | 40 | 40 | 50 | 30 | 0 | | 160 |
9 | A3 | 40 | 20 | 20 | 0 | 0 | | 80 |
10 | | | | | | | | |
11 | Потребности | 120 | 100 | 110 | 70 | 40 | | |
После заполнения перевозок в клетке G2 мы автоматически получим суммарные затраты, равные 1610 руб.
3.3.4. План перевозок, полученный методом «северо-западного» угла
Следующий план перевозок получим в Excel на листе 2. Отличие от предыдущего плана состоит только в заполнении блока ячеек B7 : F9. Поэтому можно скопировать лист 1 на лист 2 и изменить только содержимое указанного блока. В ячейку B7 («северо-западная» клетка) поставим максимально допустимую перевозку, равную
![](713906_html_85a360bb1372e575.gif)
![](713906_html_8e28435aa55f17a0.gif)
![](713906_html_7348683d98838f5b.gif)
![](713906_html_b16d4a314bcbbc75.gif)
![](713906_html_7348683d98838f5b.gif)
![](713906_html_41d130b539b7e057.gif)
Т а б л и ц а 3.4
| A | B | C | D | E | F | G | H |
1 | | Тарифы на перевозку груза | | | ||||
2 | | 3 | 2 | 4 | 6 | 7 | 1310 | |
3 | | 2 | 3 | 1 | 2 | 6 | | |
4 | | 5 | 4 | 7 | 6 | 8 | | |
5 | | План по методу «северо-западного» угла | | | ||||
6 | | B1 | B2 | B3 | B4 | B5 | | Запасы |
7 | A1 | 120 | 80 | 0 | 0 | 0 | | 200 |
8 | A2 | 0 | 20 | 110 | 30 | 0 | | 160 |
9 | A3 | 0 | 0 | 0 | 40 | 40 | | 80 |
10 | | | | | | | | |
11 | Потребности | 120 | 100 | 110 | 70 | 40 | | |
После заполнения перевозок методом «северо-западного» угла в клетке G2 получим суммарные затраты для этого плана, равные 1310 руб.
3.3.5. План перевозок, полученный методом минимальной стоимости
На листе 3 составим план перевозок методом минимальной стоимости. Отличие от предыдущих планов состоит только в заполнении блока ячеек B7 : F9. Заполнение плана перевозок начнем с ячейки, имеющей минимальную стоимость, а именно, с ячейки D8, в которой тариф (ячейка D3) равен 1. В ячейку D8 поместим максимально допустимую перевозку, равную
![](713906_html_a2e46896b2fcdde0.gif)
![](713906_html_c88d4afc09e3fd01.gif)
![](713906_html_bcb11bd2046b78ac.gif)
![](713906_html_b20b821bff01e84a.gif)
![](713906_html_7348683d98838f5b.gif)
Продолжая этот процесс дальше, получим план перевозок, представленный в табл. 3.5.
Т а б л и ц а 3.5
| A | B | C | D | E | F | G | H |
1 | | Тарифы на перевозку груза | | | ||||
2 | | 3 | 2 | 4 | 6 | 7 | 1360 | |
3 | | 2 | 3 | 1 | 2 | 6 | | |
4 | | 5 | 4 | 7 | 6 | 8 | | |
5 | | План по методу минимальной стоимости | | | ||||
6 | | B1 | B2 | B3 | B4 | B5 | | Запасы |
7 | A1 | 70 | 100 | 0 | 30 | 0 | | 200 |
8 | A2 | 50 | 0 | 110 | 0 | 0 | | 160 |
9 | A3 | 0 | 0 | 0 | 40 | 40 | | 80 |
10 | | | | | | | | |
11 | Потребности | 120 | 100 | 110 | 70 | 40 | | |
После заполнения перевозок методом минимальной стоимости в клетке G2 получим суммарные затраты для этого плана, равные 1360 руб.
3.3.6. Определение оптимального плана перевозок
Планы перевозок груза, полученные ранее и содержащиеся в табл. 3.3-3.5, образованы без привлечения надлежащего математического аппарата, и потому, вряд ли являются оптимальными. Лучшим, т.е. наиболее близким к оптимальному, из трех рассмотренных планов является в данном случае план, полученный методом «северо-западного» угла, так как суммарные затраты по нему наименьшие и составляют 1310 руб.
Оптимальный план перевозок определим в Excel на листе 4 с помощью процедуры «Поиск решения». Скопируем один из предыдущих листов на лист 4 и дополним его двумя графами. В блок ячеек G7 : G9 поместим левые части системы (3.5). Для этого в ячейку G7 поместим формулу
= СУММ(B7 : F7),
которую протянем на ячейки G8 и G9. В блок ячеек B10 : F10 поместим левые части системы (3.6). Для этого в ячейку B10 поместим формулу
= СУММ(B7 : B9),
которую протянем на блок ячеек C10 : F10. Чтобы определить оптимальный план перевозок, следует обратиться к процедуре «Поиск решения», как показано на рис. 3.1.
![](713906_html_bbca630cb468ff0c.png)
Рис.3.1. Обращение к процедуре «Поиск решения» в транспортной задаче
Согласно сделанному выше замечанию, последнее уравнение системы (3.6) опущено. Кроме того, если будет получено не целочисленное решение, то можно ввести дополнительное ограничение на целочисленность. Результаты оптимизации представлены табл. 3.6.
Т а б л и ц а 3.6
| A | B | C | D | E | F | G | H |
1 | | Тарифы на перевозку груза | | | ||||
2 | | 3 | 2 | 4 | 6 | 7 | 1250 | |
3 | | 2 | 3 | 1 | 2 | 6 | | |
4 | | 5 | 4 | 7 | 6 | 8 | | |
5 | | Оптимальный план перевозок | | | ||||
6 | | B1 | B2 | B3 | B4 | B5 | | Запасы |
7 | A1 | 120 | 80 | 0 | 0 | 0 | 200 | 200 |
8 | A2 | 0 | 0 | 110 | 50 | 0 | 160 | 160 |
9 | A3 | 0 | 20 | 0 | 20 | 40 | 80 | 80 |
10 | | 120 | 100 | 110 | 70 | 40 | | |
11 | Потребности | 120 | 100 | 110 | 70 | 40 | | |
В ячейке G2 находятся минимальные суммарные затраты для оптимального плана перевозок, составляющие 1250 руб.
3.3.7. Граф перевозок
На основании оптимального плана изображен граф перевозок в виде рис. 3.2. На графе представлены направления перевозок груза и оптимальные объемы перевозок.
![](713906_html_10ad27bf67961acb.gif)
Рис. 3.2. Граф перевозок для оптимального плана
3.4. Содержание отчета по работе
Отчет должен содержать следующие пункты:
задание на работу с конкретными исходными данными студента,
математическая модель транспортной задачи для конкретных данных студента,
«равномерный» план перевозок, суммарные затраты на перевозки,
план перевозок, полученный методом «северо-западного» угла, суммарные затраты на перевозки,
план перевозок, полученный методом минимальной стоимости, суммарные затраты на перевозки,
оптимальный план перевозок, суммарные затраты на перевозки,
граф перевозок, построенный для оптимального плана,
выводы по работе.