Міністерство Російської Федерації з атомної енергії
Саровський Державний Фізико-Технічний Інститут
В
Політехнікум СарФТІ
Кусов РОБОТА
В
За фахом - В«Програмне забезпеченняВ»
Тема: Рішення транспортної задачі методом потенціалів
<В
Студент :
Група:
Викладач:
Дата: 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 . p> Якщо то потреба не може бути покрита. У цьому випадку початкові умови повинні бути змінені таким чином, щоб потреба у продукції могла бути забезпечена.
Позначимо через x ij ...
