Міністерство Російської Федерації з атомної енергії
Саровський Державний Фізико-Технічний Інститут
Політехнікум СарФТІ
Кусова РОБОТА
За фахом - «Програмне забезпечення»
Тема: Рішення транспортної задачі методом потенціалів
Студент:
Група:
Викладач:
Дата: 5 травня
Оцінка: ...
м. Саров
2005
Зміст
Введення .. 3
1. Транспортна задача .. 4
1.1 Складання опорного плану. 7
1.2 Метод потенціалів. 9
2. Практична частина .. 16
2.1 Обгрунтування вибору мови програмування. 16
2.2 Розробка. 16
2.3 Керівництво користувачів. 16
Висновок .. 18
Література .. 19
Введення
Даний курсовий проект являє собою програму для розв'язання транспортної задачі методом потенціалів. Програма надає користувачеві можливість покрокового знаходження оптимального рішення. Всі проміжні результати виводяться на екран, користувач може стежити за ходом вирішення.
Транспортна задача полягає в знаходженні такого плану поставок, при якому його ціна мінімальна.
Умови завдання задаються у вигляді таблиці:
Матриця (c ij) m * n називається матрицею тарифів. Планом транспортної задачі називається матриця х = (x ij) m * n, де кожне число позначає кількість одиниць вантажу, яке треба доставити з i-го пункту відправлення в j-й пункт призначення.
Далі, передбачається, що
(1)
де b i є кількість продукції, що знаходиться на складі i, і a j - потреба споживача j.
Зауваження. Якщо ту кількість продукції, рівне залишається на складах. У цьому випадку ми введемо "фіктивного" споживача n +1 з потребою і покладемо транспортні витрати p i, n +1 рівними 0 всіх i.
Якщо то потреба не може бути покрита. У цьому випадку початкові умови мають бути змінені таким чином, щоб потреба в продукції могла бути забезпечена.
Позначимо через x ij кількість продукції, що поставляється зі складу i споживачеві j. У пропозиції (1) нам потрібно вирішити таку задачу (математична модель транспортної задачі):
(2)
Транспортну задачу ми можемо характеризувати транспортної таблицею та таблицею витрат:
Допустимий план перевезень будемо представляти у вигляді транспортної таблиці:
Сума елементів рядка i повинна бути дорівнює b i, а сума елементів стовпця j повинна бути дорівнює a j, і все повинні бути невід'ємними.
Приклад 1.
Ми отримуємо таку задачу:
х 11 + х 12 + х 13 + х 14 + х 15 = 15,
х 21 + х 22 + х 23 + х 24 + х 55 = 15,
х 31 + х 32 + х 33 + х 34 + х 35 = 20,
х 11 + х 21 + х 31 = 20,
х 12 + х 22 + х 32 = 5,
х 13 + х 23 + х 33 = 10,
х 14 + х 24 + х 34 = 10,
х 15 + х 25 + х 35 = 5;
х ij 0 для i = 1,2,3; j = 1,2,3,4,5;
До min = 5х 11 +6 х 12 +3 х 13 +5 х 14 +9 х 15 +6 х 21 +4 х 22 +7 х 23 +3 х 24 +5 х 25 +2 х 31 +5 х 32 +3 х 33 + х 34 +8 х 35;
Такі завдання доцільно вирішувати за допомогою особливого варіанта симплекс-методу - так званого методу потенціалів.
Всі транспортні завдання мають оптимальне рішення. Якщо все значення a j і b i в умовах транспортної задачі цілими, то змінні x ij у всіх базисних рішеннях (а так само і в будь-якому оптимальному базисному рішенні) мають цілочисельні значення.
Умови транспортної задачі задані транспортної таблицею.
Будемо заповнювати таблицю перевезеннями поступово починаючи з лівої верхньої комірки ("північно-західного кута" таблиці). Будемо міркувати при цьому таким чином. Пункт а 1 подав заявку на 20 одиниць вантажу. Задовольнимо цю заявку за рахунок запасу 15, наявного в пункті b 1, і запишемо перевезення 15 в клітці (1,1). Після цього доповнимо заявку за рахунок заявка пункту b 2, і запишемо 5 в клітці (1,2), тепер заявка задоволена, але в пункті b 2 залишилося ще 10 одиниць вантажу. Задовольнимо за рахунок них заявку пунктів а 2 (5 одиниць клітина 2,2) і а 3 (5 одиниць клітина 2,3). На складі b 3 є запас у 20 одиниць, за рахунок його ми задовольнимо заявки залишилися а 3 (решта 5 одиниць клітина 3,3), а 3 (10 одиниць клітина 3,4) і а 5 (5 одиниць клітина 3,5) .
На цьому розподіл запасів закінчено; кожен пункт призначення отримав вантаж, відповідно до своєї заявки. Це виражається в тому, що сума перевезень в кожному рядку дорівнює відповідному запасу, а в стовпці - заявці. Таким чином, нами відразу ж складений план перевезень, що задовольняє балансовим умов. Отримане рішення є опорним вирішенням транспортної задачі. Складений нами план перевезень, не є оптимальним за вартістю, так як при його побудові ми зовсім не врахували вартість перевезень З ij.
1.2 Метод потенціалів
Нехай є транспортна таблиця, відповідна початкового рішенням, х il = для базисного рішення змінних, х il = 0 для вільних змінних (Комірки, відповідні вільним змінним, залишаються порожніми). Далі, нам потрібно таблиця витрат із заданими p ij.
Відшукування симплекс множників. Заповнимо таблицю витрат, залишивши осередки, відповідні вільним змінним, порожніми. У крайній правий стовпець внесемо значення невідомих u 1, ..., u m, в нижній рядок - значення невідомих v 1, ..., v n,. Ці m + n невідомих для всіх (i, j), відповідних базисним змінним, повинні задовольняти лінійної системи рівнянь u i + v j = P ij.
Для всіх базисних рішень ця система має трикутний вигляд, ранг її матриці дорівнює n + m - 1. Отже, систему завжди можна вирішити таким способом.
Вважають v n = 0. Якщо значення k невідомих визначено, то в системі завжди є рівняння, одне з невідомих в якому вже знайдено, а інше ще немає.
Змінні u i і v j симплекс - множниками. Іноді вони називаються також потенціалами, а цей метод розв'язання називають методом потенціалів.
Приклад 2.
v 5 = 0 ® u 3 = 8, так як u 3 + u 5 = P 35 = 8, ® v 4 = -7, так як u 3 + V 4 = P 34 = 1, ® v 3 = -5, так як u 3 + V 3 = 3, ® u 2 = 12 ® v 2 = -8, ® v 1 = -6 ® u 1 = 11.
Симплекс - множники потрібні для того, щоб знайти вільну комірку (i, j), яка при заміні базису переходить в базисну (це відповідає відшукання дозволяє стовпця в симплекс - метод).
Для визначення симплекс - множників ми вносимо на вільні місця в таблиці значення
p ¢ ij = P ij - u i - v j
(Коефіцієнти цільової функції, перелічені для вільних змінних). Якщо все p ¢ ij 0, то базисне рішення оптимально. В іншому випадку ми вибираємо довільне p ¢ a b <0, найчастіше найменше. Індексом a b позначено вільне змінне х a b , Яке має увійти в базис. Відповідну клітинку транспортної таблиці ми відзначимо знаком +.
Крім осередку (a, b) транспортної таблиці, ми помітимо значками - і + інші зайняті числами осередку таким чином, щоб в кожному рядку і в кожному стовпці транспортної таблиці число знаків + було дорівнює числу знаків -. Це завжди можна зробити єдиним чином, причому в кожному рядку і в кожному стовпці буде міститися максимум по одному знаку = і по одному знаку -.
Потім ми визначаємо мінімум М з усіх елементів із літерами -, і вибираємо клітинку (g, d), де цей мінімум досягається.
У нашому прикладі з М = 5 можна вибрати (g, d) = (2, 3); при цьому (g, d) визначає базисне змінне, яке повинно стати вільним, тобто базисне змінне, відповідне індексом роздільної рядка симплекс - методу.
¯
¯
¯
¯
До опт = 150
Перехід до нової транспортної таблиці (заміна базису) відбувається наступним чином:
а). У комірку (a, b) нової таблиці записується число М.
б). Вічко (g, d) залишається порожньою.
в). В інших осередках помічених знаками - або +, число М віднімається з стоїть в осередку числа (-) або складається з ним (+). Результат вноситься у відповідний осередок нової таблиці.
г). Непозначених числа переносяться в нову таблицю без змін. Решта осередку нової таблиці залишаються порожніми.
· Вивчення цієї мови в школі
· Наявність літератури з мови програмування
Потрібно скласти такий план перевезень (звідки, куди і скільки одиниць поставити), щоб усі заявки були виконані, а загальна вартість всіх перевезень була мінімальна.
Скласти програму, яка б вираховувала оптимальний план перевезення (потенційний план).
А. В. Кузнєцов, Г. І. Новикова, І. І. Холод - "Збірник задач з математичного програмування". Мінськ, Вища школа, 1985р
Боборикін В.А. Математичні методи вирішення транспортних завдань. Л.: СЗПІ, 1986
Кузнєцов Ю.М., Кузубов В.І., Волощснко А. Б. Математичне програмування. М.: Вища школа, 1980
Саровський Державний Фізико-Технічний Інститут
Політехнікум СарФТІ
Кусова РОБОТА
За фахом - «Програмне забезпечення»
Тема: Рішення транспортної задачі методом потенціалів
Студент:
Група:
Викладач:
Дата: 5 травня
Оцінка: ...
м. Саров
2005
Зміст
Введення .. 3
1. Транспортна задача .. 4
1.1 Складання опорного плану. 7
1.2 Метод потенціалів. 9
2. Практична частина .. 16
2.1 Обгрунтування вибору мови програмування. 16
2.2 Розробка. 16
2.3 Керівництво користувачів. 16
Висновок .. 18
Література .. 19
Введення
Даний курсовий проект являє собою програму для розв'язання транспортної задачі методом потенціалів. Програма надає користувачеві можливість покрокового знаходження оптимального рішення. Всі проміжні результати виводяться на екран, користувач може стежити за ходом вирішення.
Транспортна задача полягає в знаходженні такого плану поставок, при якому його ціна мінімальна.
Умови завдання задаються у вигляді таблиці:
постачальник | споживач | Запас вантажу | |||
В1 | В2 | ... | Вn | ||
А1 | C11 X11 | C12 X12 | ... | C1n X1n | a1 |
А2 | C21 X21 | C22 X22 | ... | C2n X2n | a2 |
... | ... | ... | ... | ... | ... |
Аm | Cm1 Xm1 | Cm2 Xm2 | ... | Cmn Xmn | am |
Потреба у вантажі | b1 | b2 | ... | bn |
1. Транспортна задача
Транспортна задача ставиться так: є m пунктів відправлення, в яких зосереджені запаси якихось однорідних вантажів. Є n пунктів призначення подали заявки відповідно на вантажу. Відомі вартості р ij перевезення одиниці вантажу від кожного пункту відправлення до кожного пункту призначення. Всі числа р ij, що утворюють прямокутну таблицю задані. Потрібно скласти такий план перевезень (звідки, куди і скільки одиниць поставити), щоб усі заявки були виконані, а загальна вартість всіх перевезень була мінімальна.Далі, передбачається, що
де b i є кількість продукції, що знаходиться на складі i, і a j - потреба споживача j.
Зауваження. Якщо ту кількість продукції, рівне залишається на складах. У цьому випадку ми введемо "фіктивного" споживача n +1 з потребою і покладемо транспортні витрати p i, n +1 рівними 0 всіх i.
Якщо то потреба не може бути покрита. У цьому випадку початкові умови мають бути змінені таким чином, щоб потреба в продукції могла бути забезпечена.
Позначимо через x ij кількість продукції, що поставляється зі складу i споживачеві j. У пропозиції (1) нам потрібно вирішити таку задачу (математична модель транспортної задачі):
(2)
Транспортну задачу ми можемо характеризувати транспортної таблицею та таблицею витрат:
а1 | ... | аn | ||||
b1 . . . bm | . | |||||
. | ||||||
. | ||||||
. | ||||||
. | ||||||
. |
p11 | ... | p1n |
. | . | |
. | . | |
. | . | |
pm1 | ... | pmn |
а1 | ... | аn | |
b . . . bm | ... | ||
. | . | ||
. | . | ||
. | . | ||
... |
Приклад 1.
20 | 5 | 10 | 10 | 5 | |
15 | |||||
15 | |||||
20 |
5 | 6 | 3 | 5 | 9 |
6 | 4 | 7 | 3 | 5 |
2 | 5 | 3 | 1 | 8 |
х 11 + х 12 + х 13 + х 14 + х 15 = 15,
х 21 + х 22 + х 23 + х 24 + х 55 = 15,
х 31 + х 32 + х 33 + х 34 + х 35 = 20,
х 11 + х 21 + х 31 = 20,
х 12 + х 22 + х 32 = 5,
х 13 + х 23 + х 33 = 10,
х 14 + х 24 + х 34 = 10,
х 15 + х 25 + х 35 = 5;
х ij 0 для i = 1,2,3; j = 1,2,3,4,5;
До min = 5х 11 +6 х 12 +3 х 13 +5 х 14 +9 х 15 +6 х 21 +4 х 22 +7 х 23 +3 х 24 +5 х 25 +2 х 31 +5 х 32 +3 х 33 + х 34 +8 х 35;
Такі завдання доцільно вирішувати за допомогою особливого варіанта симплекс-методу - так званого методу потенціалів.
Всі транспортні завдання мають оптимальне рішення. Якщо все значення a j і b i в умовах транспортної задачі цілими, то змінні x ij у всіх базисних рішеннях (а так само і в будь-якому оптимальному базисному рішенні) мають цілочисельні значення.
1.1 Складання опорного плану
Рішення транспортної задачі починається із знаходження опорного плану. Для цього існують різні способи, розглянемо найпростіший, так званий спосіб північно-західного кута. Пояснити його найпростіше буде на конкретному прикладі:Умови транспортної задачі задані транспортної таблицею.
а b | 20 | 5 | 10 | 10 | 5 |
15 | 5 | 6 | 3 | 5 | 9 |
15 | 6 | 4 | 7 | 3 | 5 |
20 | 2 | 5 | 3 | 1 | 8 |
5 | ||||
6 | 4 | 7 | ||
3 | 1 | 8 |
1.2 Метод потенціалів
Нехай є транспортна таблиця, відповідна початкового рішенням, х il = для базисного рішення змінних, х il = 0 для вільних змінних (Комірки, відповідні вільним змінним, залишаються порожніми). Далі, нам потрібно таблиця витрат із заданими p ij.
Відшукування симплекс множників. Заповнимо таблицю витрат, залишивши осередки, відповідні вільним змінним, порожніми. У крайній правий стовпець внесемо значення невідомих u 1, ..., u m, в нижній рядок - значення невідомих v 1, ..., v n,. Ці m + n невідомих для всіх (i, j), відповідних базисним змінним, повинні задовольняти лінійної системи рівнянь u i + v j = P ij.
pll | plj | pln | ul | ||
. ... . | . ... . | . . . | |||
pil | pij | pin | ui | ||
. ... . | . ... . | . . . | |||
pml | pmj | pmn | um | ||
vl | ... | vj | ... | vn |
Вважають v n = 0. Якщо значення k невідомих визначено, то в системі завжди є рівняння, одне з невідомих в якому вже знайдено, а інше ще немає.
Змінні u i і v j симплекс - множниками. Іноді вони називаються також потенціалами, а цей метод розв'язання називають методом потенціалів.
Приклад 2.
5 | u1 | ||||
6 | 4 | 7 | u2 | ||
3 | 1 | 8 | u3 | ||
v1 | v2 | v3 | v4 | v5 |
Симплекс - множники потрібні для того, щоб знайти вільну комірку (i, j), яка при заміні базису переходить в базисну (це відповідає відшукання дозволяє стовпця в симплекс - метод).
Для визначення симплекс - множників ми вносимо на вільні місця в таблиці значення
p ¢ ij = P ij - u i - v j
(Коефіцієнти цільової функції, перелічені для вільних змінних). Якщо все p ¢ ij 0, то базисне рішення оптимально. В іншому випадку ми вибираємо довільне p ¢ a b <0, найчастіше найменше. Індексом a b позначено вільне змінне х a b , Яке має увійти в базис. Відповідну клітинку транспортної таблиці ми відзначимо знаком +.
Крім осередку (a, b) транспортної таблиці, ми помітимо значками - і + інші зайняті числами осередку таким чином, щоб в кожному рядку і в кожному стовпці транспортної таблиці число знаків + було дорівнює числу знаків -. Це завжди можна зробити єдиним чином, причому в кожному рядку і в кожному стовпці буде міститися максимум по одному знаку = і по одному знаку -.
Потім ми визначаємо мінімум М з усіх елементів із літерами -, і вибираємо клітинку (g, d), де цей мінімум досягається.
У нашому прикладі з М = 5 можна вибрати (g, d) = (2, 3); при цьому (g, d) визначає базисне змінне, яке повинно стати вільним, тобто базисне змінне, відповідне індексом роздільної рядка симплекс - методу.
20 | 5 | 10 | 10 | 5 | |
15 | 15 | ||||
15 | 5 | 5 | 5 - | + | |
20 | 5 + | 10 | 5 - |
15 | ||||
5 - | 5 | 5 + | ||
+ | 10 | 10 | 0 - |
15 - | + | |||
5 | 5 | 5 | ||
0 + | 10 - | 10 |
5 | 10 | |||
5 - | 5 | + | 5 | |
10 + | 10 - |
5 | 10 | |||
5 | 5 | 5 | ||
15 | 5 |
Перехід до нової транспортної таблиці (заміна базису) відбувається наступним чином:
а). У комірку (a, b) нової таблиці записується число М.
б). Вічко (g, d) залишається порожньою.
в). В інших осередках помічених знаками - або +, число М віднімається з стоїть в осередку числа (-) або складається з ним (+). Результат вноситься у відповідний осередок нової таблиці.
г). Непозначених числа переносяться в нову таблицю без змін. Решта осередку нової таблиці залишаються порожніми.
2. Практична частина
2.1 Обгрунтування вибору мови програмування
Мною була вибрана мова програмування Turbo Pascal з таких міркувань:· Вивчення цієї мови в школі
· Наявність літератури з мови програмування
2.2 Розробка
Є m пунктів відправлення А1, А2, ..., Аm, в яких зосереджені запаси якихось однорідних вантажів у кількості відповідно а1, а2, ... , Аm одиниць. Є n пунктів призначення В1, В2, ... , Вn подали заявки відповідно на b1, b2, ... , Bn одиниць вантажу. Відомі вартості Сi, j перевезення одиниці вантажу від кожного пункту відправлення Аі до кожного пункту призначення Вj. Всі числа Сi, j, що утворюють прямокутну таблицю задані.Потрібно скласти такий план перевезень (звідки, куди і скільки одиниць поставити), щоб усі заявки були виконані, а загальна вартість всіх перевезень була мінімальна.
Скласти програму, яка б вираховувала оптимальний план перевезення (потенційний план).
2.3 Керівництво користувачів
При запуску програма пропонує ввести кількість постачальників (не менше 2, але не більше 5), потім кількість споживачів (умова теж). Якщо вводяться числа не задовольняють цій умові, то програма пропонує ввести їх заново. Далі програма виводить на екран таблицю, число рядків якої дорівнює введеному кількості постачальників, а число стовпців - кількості споживачів. Пропонується ввести кількість продукції у першого постачальника, у другого і т.д. Після користувачеві пропонується ввести кількість продукції необхідне перший споживачеві, другому і т.д. Потім вводяться вартості перевезень, після чого виробляються обчислення та видається результатЛітература
Карманов В.Г. Математичне програмування. - М.; Наука, 1986А. В. Кузнєцов, Г. І. Новикова, І. І. Холод - "Збірник задач з математичного програмування". Мінськ, Вища школа, 1985р
Боборикін В.А. Математичні методи вирішення транспортних завдань. Л.: СЗПІ, 1986
Кузнєцов Ю.М., Кузубов В.І., Волощснко А. Б. Математичне програмування. М.: Вища школа, 1980