Зміст
1. Постановка завдання
. Опис алгоритму розв'язання задачі
. Рішення завдання вручну
. Рішення у програмі TORA
. Рішення у програмі MS Excel
. Розробка програми для вирішення задачі в загальному вигляді (Delphi)
Висновки
Список використаної літератури
1. Постановка завдання
1. Вибрати й обгрунтувати найбільш ефективний метод розв'язання задачі.
. Розробити алгоритм і програму для розв'язання задачі в загальному вигляді.
. Перевірити правильність алгоритму на пропонованій задачі.
. Задача:
Є два елеватори, в яких зосереджено відповідно 4200 і 1200 т зерна. Зерно необхідно перевезти трьом хлібозаводам в кількості 1000,2000,1600 т кожному. Відстань від елеватора до хлібозаводів вказано в наступній таблиці:
ЕлеваториХлебозаводи1231 220 6030 2050 40
Витрати на перевезення 1 т продукту на 1 км складають 25 ВО
Сплануйте перевезення зерна з умови мінімізації транспортних витрат.
2. Опис алгоритму розв'язання задачі
Оскільки розглянута задача є транспортної, то алгоритм рішення буде виглядати наступним чином:
. Перевірити на збалансованість.
Транспортна задача є збалансованою, якщо сумарні запаси постачальників рівні сумарним запитам споживачів, тобто . p> Якщо сумарні запаси постачальників перевершують сумарні запити споживачів, тобто то необхідно ввести фіктивного (n +1)-го споживача з запитами рівними різниці сумарних запасів постачальників і запитів споживачів, і нульовими вартостями перевезень одиниць вантажу;
1. Визначити початкове рішення. p align="justify"> Знайдемо початкове рішення методом найменшого елемента, який дозволяє побудувати опорне рішення, досить близько до оптимального.
Опорним рішенням транспортної задачі називається будь допустиме рішення, для якого вектори умов, відповідні позитивним координатами, лінійно незалежні.
Даний метод дозволяє побудувати опорне рішення, яке досить близько до оптимального, оскільки використовує матрицю вартостей транспортної задачі, i = 1,2, ..., m; j = 1,2 ..., n. Даний метод складається з ряду однотипних кроків, на кожному з яких заповнюється тільки одна клітина таблиці, відповідна мінімальної вартості, і виключається з розгляду тільки один рядок (постачальник) або один стовпець (споживач). Чергову клітку, відпо...
