§ 15. Транспартная задача
| Сайт: | Профильное обучение |
| Курс: | Інфармацыйныя тэхналогіі. 11 клас (Базавы ўзровень) |
| Книга: | § 15. Транспартная задача |
| Напечатано:: | Гость |
| Дата: | Пятница, 26 Апрель 2024, 19:44 |
15.1. Асноўныя паняцці
|
Транспортная задача — задача пошуку такога плана перавозак аднаго віду тавару ад некалькіх пастаўшчыкоў да некалькіх спажыўцоў, які мае мінімальны кошт. Транспартная задача з'яўляецца эканамічнай задачай. Зыходнымі данымі ў транспартнай задачы з'яўляюцца:
Відавочна, што агульны аб'ём заявак роўны агульнаму аб'ёму паставак. Затраты на перавозку адзінкі грузу па кожным маршруце звычайна ўяўляюць у выглядзе табліцы, якая называецца табліцай удзельных затрат на перавозкi (прыклад 15.1). План перавозак у транспартнай задачы — гэта спіс запланаваных для перавозкі аб'ёмаў тавару ад кожнага пастаўшчыка кожнаму спажыўцу (прыклад 15.2). Ва ўмовах транспартнай задачы можна скласці шмат розных планаў перавозак. Але любой транспартнай кампаніі эканамічна больш выгадна скласці такі план перавозак, які забяспечыць ёй мінімальныя затраты на перавозку. |
Прыклад 15.1. Тры цукровыя заводы (пастаўшчыкі) павінны па дагаворы паставіць цукар у пяць магазiнаў (спажыўцы). Аб'ёмы паставак разлічваюцца ў мяшках. Вядомыя аб'ёмы заявак магазiнаў і аб'ёмы паставак заводамі. З транспартнай кампаніяй заключаны дагавор на перавозку цукру. Затраты на перавозку мяшка цукру з любога завода ў любы магазін разлічваюцца і прадстаўляюцца ў выглядзе табліцы ўдзельных затрат на перавозкі.
Напрыклад, затраты на перавозку мяшка цукру са склада 1 у краму 4 складаюць 3 грашовыя адзінкі. Прыклад 15.2. Для плана перавозак зручна выкарыстоўваць форму табліцы ўдзельных затрат на перавозку.
|
15.2. Пастаноўка задачы (этап 1)
|
Задача. Тры склады павінны забяспечыць пастаўку камп'ютарных манітораў у чатыры крамы. Аб'ёмы заявак магазiнаў і аб'ёмы паставак складамі зададзены (прыклад 15.3). Транспартная кампанія, якая павінна перавезці маніторы, разлічыла затраты на перавозку аднаго манітора па кожным маршруце і склала табліцу ўдзельных затрат на перавозкі (прыклад 15.4). Знайсці план перавозак з мінімальным коштам. |
Прыклад 15.3. Аб'ёмы заявак (у шт.):
Аб'ёмы паставак (у шт.):
Прыклад 15.4. Табліца ўдзельных затрат на перавозкі (у грашовых адзінках на адзінку тавару):
|
15.3. Выбар плана стварэння мадэлі (этап 2)
|
Асаблівасць транспартнай задачы заключаецца ў тым, што зыходныя даныя задачы зададзены трыма табліцамі (гл. прыклады 14.3, 15.4). І вынікам рашэння таксама павінна стаць табліца (гл. прыклад 15.2). Таму адразу будзем будаваць камп'ютарную разліковую мадэль у электронных табліцах (прыклад 15.5) без пабудовы дакументальнай матэматычнай мадэлi. План стварэння мадэлі для вырашэння транспартнай задачы ўключае толькі этап 3 — стварэнне камп'ютарнай разліковай мадэлі ў электронных табліцах. |
Матэматычную мадэль транспартнай задачы ўпершыню пабудаваў французскі матэматык Гаспар Монж у 1781 годзе. Першы метад рашэння транспартнай задачы ў 1939 годзе прапанаваў савецкі матэматык і эканаміст Л. В. Кантаровіч. З тых часоў распрацаваны яшчэ некалькі метадаў рашэння гэтай задачы. Прыклад 15.5. Транспартная задача з'яўляецца экстрэмальнай задачай, і яе рашэнне ў электронных табліцах Excel забяспечвае надбудова Поиск решения.
|
15.4. Стварэнне камп'ютарнай разліковай мадэлі (этап 3)
|
Зыходныя даныя камп'ютарнай мадэлі размесцім па схеме, прыведзенай у прыкладзе 15.6. Разліковую табліцу будзем будаваць па аналагічнай схеме (прыклад 15.7). Пасля ўводу загалоўкаў у ячэйкі A11 і A12 можна табліцу з раздзелу «Зыходныя даныя» скапіраваць у раздзел «Разліковая табліца» (прыклад 15.8). У ячэйку A18 уводзіцца надпіс «Сума». У ячэйку B18 уводзіцца формула сумы значэнняў ячэек гэтага слупка разліковай табліцы. Затым гэтай формулай трэба запоўніць дыяпазон C18:E18. У ячэйку F14 уводзіцца надпіс «Сума». У ячэйку F15 уводзіцца формула сумы значэнняў ячэек гэтага радка разліковай табліцы. Затым гэтай формулай запаўняецца дыяпазон F16:17. У задачы неабходна знайсці такі план перавозак, для якога іх сумарны кошт мінімальны ў параўнанні з іншымі планамі. Пабудуем функцыю V, якая вылічае сумарны кошт перавозак па зададзеным у мадэлі плане. Затраты на перавозку тавару па адным маршруце «склад i — магазін j» будуць роўныя здабытку кошту перавозкі на яе аб'ём. Кошт перавозкі зададзены ў ячэйцы табліцы ўдзельных затрат, а аб'ём — у такой жа яцэйцы табліцы плана перавозак. Для пабудовы функцыі V трэба перамнажаць значэнні адпаведных ячэек двух табліц(дыяпазонаў), а затым здабыткі скласці. Увядзем формулу для вылічэння функцыі V у ячэйку А20 (прыклад 15.9). Зараз варта выклікаць акно Параметры поиска решения і ўвесці зыходныя даныя для пошуку рашэння. Мэтавая функцыя V размешчана ў ячэйцы A20, крытэрый — Минимум, змяняючы ячэйкі пераменных дыяпазону B15:E17 (ячэйкі плана перавозак), пераходзім да ўводу абмежаванняў (прыклад 15.10). Варта таксама ячэйкі дыяпазону B15:E17 плана перавозак зрабіць цэлалікавымі (гл. прыклад 15.11). Пад полем для абмежаванняў павінна стаяць галачка выбару пункта Сделать переменные без ограничений неотрицательными. Пасля налад у акне Параметры поиска решения пстрыкаем па кнопцы Найти решение. |
Прыклад 15.6. Схема размяшчэння зыходных даных камп'ютарнай мадэлі. Слупок А трэба пашырыць.
Прыклад 15.7. Схема размяшчэння разліковай табліцы камп'ютарнай мадэлі транспартнай задачы.
План перавозак справа і знізу апраўлены ячэйкамі для сум. Прыклад 15.8. Для капіравання табліцы з раздзелу «Зыходныя даныя» варта вылучыць дыяпазон A4:E8 і скапіраваць яго на дыяпазон A13:E17. Пачатковыя значэнні ячэек плана перавозак могуць быць любымі лікамі, таму скапіраваныя значэнні ячэек плана перавозак можна пакінуць. Прыклад 15.9. Для ўводу значэння функцыі V выкарыстоўваем матэматычную функцыю СУММПРОИЗВ(), якая вяртае суму здабыткаў ячэек двух дыяпазонаў (масіваў). Таблічны курсор устанаўліваем на ячэйцы A20, пстрычкай па кнопцы Вставить функцию ў радку формул, адкрываем акно Вставка функции. Праводзім пошук функцыі па яе імені, затым два разы пстрыкаем па яе імені ў спісе. Адкрываецца акно для ўводу аргументаў. У табліцы вылучаем дыяпазон B6:E8. Ён запісваецца ў поле аргументу Массив1. Затым у акне пстрыкаем па полі другога аргументу Массив2 і ў табліцы вылучаем масіў B15:E17. Пстрычкай па кнопцы OK завяршаем увод. Прыклад 15.10. Няцяжка ўбачыць, што сумы ў ячэйках правей плана перавозак павінны даваць аб'ёмы паставак, якія зададзены ў пачатковых даных. А сумы ў ячэйках ніжэй плана перавозак — аб'ёмы заявак, якія таксама зададзеныя ў пачатковых даных. Такія абмежаванні Excel дазваляе задаваць як роўнасці дыяпазонаў. Пстрыкаем па кнопцы Добавить. У новым акне для ўводу абмежаванняў у левае поле вылучаем дыяпазон B18:E18. У другім поле выбіраем знак роўнасці. У трэцяе поле ўводзім дыяпазон B9:E9. Пстрыкаем па кнопцы OK. Аналагічна ўводзім умову роўнасці дыяпазонаў F15:F17 і F6:F8. |
15.5. Даследаванне мадэлі і атрыманне рашэння задачы (этапы 4 і 5)
|
Даследаванне мадэлі прадугледжвае вывучэнне яе адэкватнасці. Адэкватнасць правяраецца параўнаннем атрыманых вынікаў з пацверджанымі (прыклад 15.11). Рашэнне транспартнай задачы атрымана. |
Прыклад 15.11. Пацверджаныя вынікі рашэння задачы.
|
Практыкаванні
1. Паўтарыце на камп'ютары разгледжаную ў параграфе пабудову камп'ютарнай разліковай мадэлі для транспартнай задачы, зададзенай у п.15.2, і знайдзіце рашэнне гэтай задачы.
2. Вырашыце транспартную задачу, паменшыўшы ў два разы аб'ёмы заявак і аб'ёмы адгрузкі ва ўмовах задачы п. 15.2.
3. Вырашыце наступную транспартную задачу. Кампанія валодае трыма заводамі, якія вырабляюць непадзельную прадукцыю аднаго віду і маюць прадукцыйнасць 600, 300, 330 адзінак прадукцыі ў год. Кампанія абавязалася за год паставіць у чатыры гарады адпаведна 350, 350, 230 і 300 адзінак прадукцыі. Табліца ўдзельных коштаў перавозкі мае выгляд:
4. Знайсці план перавозак з мінімальным коштам.
5. Вырашыце транспартную задачу з наступнымі зыходнымі данымі для непадзельнага тавару.
