Рішення транспортної задачі методом потенціалів

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Міністерство Російської Федерації з атомної енергії
Саровський Державний Фізико-Технічний Інститут
Політехнікум СарФТІ


Кусова РОБОТА
За фахом - «Програмне забезпечення»
Тема: Рішення транспортної задачі методом потенціалів


Студент:
Група:
Викладач:
Дата: 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
Матриця (c ij) m * n називається матрицею тарифів. Планом транспортної задачі називається матриця х = (x ij) m * n, де кожне число позначає кількість одиниць вантажу, яке треба доставити з i-го пункту відправлення в j-й пункт призначення.

1. Транспортна задача

Транспортна задача ставиться так: є m пунктів відправлення, в яких зосереджені запаси якихось однорідних вантажів. Є n пунктів призначення подали заявки відповідно на вантажу. Відомі вартості р ij перевезення одиниці вантажу від кожного пункту відправлення до кожного пункту призначення. Всі числа р ij, що утворюють прямокутну таблицю задані. Потрібно скласти такий план перевезень (звідки, куди і скільки одиниць поставити), щоб усі заявки були виконані, а загальна вартість всіх перевезень була мінімальна.
Далі, передбачається, що
(1)
де 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

...

.
.
.
.
.
.

...

Сума елементів рядка i повинна бути дорівнює b i, а сума елементів стовпця j повинна бути дорівнює a j, і все повинні бути невід'ємними.
Приклад 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
Будемо заповнювати таблицю перевезеннями поступово починаючи з лівої верхньої комірки ("північно-західного кута" таблиці). Будемо міркувати при цьому таким чином. Пункт а 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) .
5
6
4
7
3
1
8
На цьому розподіл запасів закінчено; кожен пункт призначення отримав вантаж, відповідно до своєї заявки. Це виражається в тому, що сума перевезень в кожному рядку дорівнює відповідному запасу, а в стовпці - заявці. Таким чином, нами відразу ж складений план перевезень, що задовольняє балансовим умов. Отримане рішення є опорним вирішенням транспортної задачі. Складений нами план перевезень, не є оптимальним за вартістю, так як при його побудові ми зовсім не врахували вартість перевезень З 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.
pll
plj
pln
ul
.
...
.
.
...
.
.
.
.
pil
pij
pin
ui
.
...
.
.
...
.
.
.
.
pml
pmj
pmn
um
vl
...
vj
...
vn
Для всіх базисних рішень ця система має трикутний вигляд, ранг її матриці дорівнює n + m - 1. Отже, систему завжди можна вирішити таким способом.
Вважають v n = 0. Якщо значення k невідомих визначено, то в системі завжди є рівняння, одне з невідомих в якому вже знайдено, а інше ще немає.
Змінні u i і v j симплекс - множниками. Іноді вони називаються також потенціалами, а цей метод розв'язання називають методом потенціалів.
Приклад 2.
5
u1
6
4
7
u2
3
1
8
u3
v1
v2
v3
v4
v5
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) визначає базисне змінне, яке повинно стати вільним, тобто базисне змінне, відповідне індексом роздільної рядка симплекс - методу.
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
До опт = 150
Перехід до нової транспортної таблиці (заміна базису) відбувається наступним чином:
а). У комірку (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
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова
104.5кб. | скачати


Схожі роботи:
Рішення транспортної задачі з правильним балансом
Розвязання задач графічним методом методом потенціалів методом множників Лангранжа та симплекс-методом
Рішення задачі лінійного програмування симплексним методом
Рішення задачі лінійного програмування симплекс методом
Рішення задачі лінійного програмування графічним методом
Рішення задачі комівояжера методом гілок і меж
Рішення задачі оптимального резервування системи методом динамічного програмування
Основні принципи розв`язання транспортної задачі
Рішення прикладної задачі
© Усі права захищені
написати до нас