Розробка програми розв'язку транспортної задачі

 

 

Міністерство освіти, науки, молоді та спорту України

Кіровоградський національний технічний університет

Факультет автоматика та енергетики

Кафедра “Обчислювальної  техніки та прикладної математики”

 

 

 

 

 

Курсова  робота

з дисципліни «Алгоритмічні  мови і програмування»

 

Тема: «Розробка програми розв'язку транспортної задачі»

 

Виконав: студент групи  СІ-10-2

Чорногор С.О.

 

Перевірив: викладач

Рибакова Л.В.

Дата захисту: _____________

Оцінка:  __________________    

 

 

 

Кіровоград 2011

АНОТАЦІЯ

 

Дана програма є навчально-практичною програмою розв’язку транспортної задачі.

Функціонує  в операційній системі MS DOS (версія 4.0 і вища) при 64 Мбайт ОЗП та 100 Кбайт дискового простору ( при завантаженні *.exe – файлу), інакше необхідна наявність інтегрованого середовища програмування Borland Pascal версії 7.0 та вище)

 

 

Данная программа является обучаеще-практической прогаммой решения транспортной задачи..

Функционирует в операционной системе MS DOS (версия 4.0 и выше) при 64 Мбайт ОЗП и 100 Кбайт дискового пространства ( при загрузке *.exe – файла), иначе необходимое наличие интегрированной среды программирования Borland Pascal версии 7.0 и выше.

 

 

This  program is teaching and  practical program for an account  of transport task.

Functions in the operating system MS DOS (version 4.0 and higher) at 64 Mb of ОЗП and 100 Kb of disk space ( at loading *.exe - file), otherwise necessary presence of the integrated environment of programming of Borland Pascal versions 7.0 and higher.

 

 

 

 

Зміст

Стор.

Вступ…………………………………………………………………………………..4

Розділ  І. Аналіз задач, що зводяться до розв’язання транспортної моделі (задачі), формалізація змісту задачі та розгляд методів її розв’язку............6

1. Розгляд задач, що трапляються в житті, і які зводяться до розв’язання транспортних ………………………………………………….…………..6
2. Початкові розв’язки ТЗ, опис методів, які дають початкові наближені результати………………………………………………………………...10
3. Метод потенціалів, як найбільш доцільніший та практичний метод розв’язку ТЗ………………..………………………………………….….16

Роздііл ІІ. Побудова алгоритму роботи програми для вирішення ТЗ……...21

2.1 Стандартний  алгоритм розв’язку транспортної задачі…..……………..21

2.2 Загальний алгоритм роботи програми ………………….……………....23

2.3 Допоміжні  алгоритми ………….………………………...………….…...25

Розділ  ІІІ. Програмна реалізація алгоритму…………………….……………...26

3.1. Обгругтування вибіру мови………...………………………………….. 26

3.2. Опис роботи програми………………..…………….…………………..27

3.3. Допоміжні процедури та функції ………………...…………………….28

3.4. Інструкція користувача, аналіз роботи програми…………….………..29

3.5. Ідеї та методи вдосконалення програми……………………….……….30

Висновки……………………………………………………………………………..30

Використана література…………………………………………………….…….....32

 

 

 

Вступ

У наш час(час бурхливого розвитку новітніх технологій) дедалі більше значення набуває моделювання тих чи інших процесів. Найпростішими та найдешевшими моделями являються віртуальні моделі, тобто моделі створені засобами програмування. В основі такого моделювання лежить прикладна математика, а саме числові методи. Цей новий підхід дав можливість заощаджувати  кошти, які раніше йшли на дорогі випробування та дослідження науки, промислового виробництва, економіки.

Зараз обчислення чи аналіз будь-якого процесу, задач,на розв’язок яких вручну потрібно декілька років, машини моделюють за декілька годин, при чому безпосередній обрахунок займає декілька хвилин. З кожним роком удосконалюється техніка, а разом з нею і засоби програмування та моделювання. Саме тому чисельний аналіз на сьогодні є найбільш актуальним і найбільш ефективним апаратом конструктивного дослідження прикладних проблем.

Однією з  задач чисельних методів є  розв’язання транспортної задачі. Вона полягає в визначенні найкращого шляху переміщення(перевезення) якогось  товару з пункту відправлення в пункт  призначення. Транспортні задачі допомагають визначити об’єм перевезень з пунктів відправлення до пунктів призначення з мінімальною сумарною вартістю перевезень.

Програму з  таким змістом доречно використовувати  підприємствам, які мають декілька пунктів виробництва та збуту  товару. Вона допоможе доречно використати час, товар та отримати максимальний прибуток.

Метою даної роботи є створення універсальної програми, яка знаходить оптимальний результат розв’язку задач що зводяться до транспортної.

Сама програма буде створена за допомогою засобів програмування мови Turbo Paskal.

Для  даної  роботи поставлено три задачі:

Перша: Аналізувати  задачі, що зводяться до розв’язання  транспортної моделі (задачі), формалізувати зміст задач та обґрунтувати вибір методу їх розв’язку.

Друга: Побудовати алгоритм розв’язку ТЗ та проаналізувати його роботу.

Третя: Програмно  реалізувати алгоритм та описати функціонування програми.

Курсова робота поділена на три розділи: опис методів  розв’язання даної задачі, опису  самого алгоритму розв’язку задачі та реалізація алгоритму на мові Pascal.

Перший розділ містить аналіз задач, які зводяться  до ТЗ, а також опис методів розв’язку  транспортної задачі, їх дослідження  та вибір найкращого, або декількох  методів. Розгляд прикладів на можливих задачах транспортної моделі.

У розділі другому  на алгоритмічному рівні досягається  поставлена мета, у вигляді блок схем та словесного опису.

Третій розділ – найважливіший, у ньому викладено  реалізацію алгоритму викладеного  в попередньому розділові. Тут описано  роботу головної програми та процедур і функцій користувача. Та коротка інструкція по використанню програми. А також викладені можливі допрацювання до програми та ідеї її покращення.

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

Курсова робота була розроблена мною спираючись на такі наукові роботи:  Вєнтцель Є.С. «Дослідження операцій», Булуцький В.В. «Чисельні  методи» та ще деякі праці зв’язані з програмуванням на мові TP.

 

 

 

Розділ І

1.   Аналіз задач, що зводяться до розв’язання транспортної моделі (задачі), обґрунтування вибору методу їх розв’язку

1. Формулювання змісту та аналіз задач, які зводяться до задач транспортного типу.

Транспортні задачі[3, 5, 8] (моделі) – спеціальний клас задач лінійного програмування. Ці моделі найчастіше описують переміщення (перевезення) якогось товару з пункту відправлення до пункту призначення.

Транспортні задачі допомагають визначити об’єм  перевезень з пунктів відправлення до пунктів призначення з мінімальною  сумарною вартістю вантажу, який знаходиться в пунктах відправлення (пропозиції), та обмеження перевезень. При цьому повинні враховуватися обмеження, які накладаються на об’єми, які враховують потреби вантажу в пунктах призначення (попит).

В загальних  випадках транспортну модель використовують в ситуаціях пов’язаних з управлінням запасами, управління руху капіталів, складання розкладу і т.п.

Стандартна  транспортна модель.

У прикладній математиці стандартну транспортну задачу[1] показують у вигляді сітки з m пунктами відправлення та n пунктами призначення, які будуть слугувати вузлами сітки. Дуги , які поєднують вузли сітки, відповідають маршрутам, які пов’язують пункти відправлення та пункти призначення. З дугою (i,j), яка пов’язує пункт відправлення i з пунктом призначення j, пов’язують такі дані: вартість C _ij перевезень одиниці вантажу з пункту i до пункту j; кількість вантажу X_ij. Об’єм вантажу в пункті відправлення і дорівнює а_і, а об’єм вантажу в пункті призначення j – b_j. В задачі необхідно визначити невідомі X_ij, які мінімізують сумарні транспортні витрати і задовольняють обмеження, які накладаються на об’єми вантажу в пунктах відправлення і пунктах призначення. (Схему стандартної транспортної задачі показано на рисунку 1.1.)

 

                 пункти відправлення                            пункти призначення

a₁                                                                                                        b₁

a₂                                                                                                       b₂

a_m                                                                                                       b_n

 

Рисунок.1. – Схема транспортної задачі

                                Транспортна таблиця.

Методи розв’язання  транспортної задачі безпосередньо пов’язані з простими операціями з таблицею, де у відповідному порядку розташовані усі умови транспортної задачі. Така таблиця називається транспортною табли- цею(Рис. 2.). В ній записуються:

• Пункти відправлення та призначення;
• Запаси, що знаходяться в пунктах відправлення;
• Заявки, які поступили з пунктів призначення;
• Вартість перевозок з кожного пункту відправлення в кожний пункт призначення.

ПП ПВ	В1	В2	…	Вn	Запаси aj
А1	C11	C21		C1n	a1
А2	C12	C22		C2n	a2
…
Аm	Cm1	Cm2		Cmn	am
Заявки b1	b1	b2		bn

Рисунок 2. –Транспортна таблиця

Де ПП – пункти призначення, ПВ – пункти відправлення, в правому верхньому куті –  вартість перевезки одиниці товару з ПВ до ПП. В правому стовбці  містяться запаси товару в кожному  ПВ, в нижній строці – заявки, що подані кожним ПП. Сума запасів дорівнює сумі заявок.

Приклад 1. Компанія займається переробкою деревинних ресурсів. Вона має три пункти накопичення (вироблення) деревини, та чотири пункти переробки. Також відомо про витрати на доставку одиниці ресурсу між пунктами накопичення та пунктами переробки ресурсів. Необхідно встановити, як розподілити ресурси між цими пунктами, щоб витрати на їх перевезення були мінімальними. Дану задачу можна зобразити так:

Місця та кількість накопиченого ресурсу		Місця та обсяги використання ресурсу
		В1	В2	В3	В4
		30	25	18	20
А1	70	1	4	3	2
А2	50	5	2	3	7
А3	20	2	4	5	1

Рисунок 3. – Тр. Таб.1

Приклад. 2. Автомобільна компанія Ford має три заводи в Лос-Анжелесі, Детройті та Новому Орлеані і два розподільчі центри в Денвері та Маямі. Об’єми виробництва заводів в наступному кварталі складають 1000, 1500, 1200 автомобілів відповідно. Кожного кварталу розподільчі центри потребують 2300 та 1400 автомобілів. Відстані (в милях) між заводами та розподільчими центрами подані в таблиці (Рис 4):

	Денвер	Майамі
Лос-Анжелес	1000	2690
Детройд	1250	1350
Новий Орлеан	1275	850

Рисунок 4. – Відстані між заводами

Транспортна компанія оцінює свої послуги у 8 центів за перевезення  одного автомобіля на відстань 1 миля. Тому вартість перевезень покожному маршруту (Рис 5):

 

	Денвер	Майамі
Лос-Анжелес	80$	215$
Детройд	100$	108$
Новий Орлеан	102$	68$