Реферати українською » Экономико-математическое моделирование » Рішення транспортної задачі розподілу методом потенціалів


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

Зміст

 

Запровадження

1. Формулювання проблеми, у практичної області

2. Побудова моделей транспортної завдання

3. Реалізація алгоритму програми

 Керівництво користувача

 Укладання

Список використовуваної літератури


Запровадження

>Линейное програмування (ЛЗ) - наука про методи дослідження та перебуванняекстремумов лінійної функції, на невідомі якої накладено лінійні обмеження. Тобто, завдання лінійного програмування, це перебування мінімального чи максимального значення лінійної функції з урахуванням системи з лінійнихуравнений-ограничений. Все разом це дає математичну модель, будь-якого економічного процесу.

>Экономико-математическая модель - це математичне опис економічного процесу чи об'єкта. Такі моделі йдуть на досліджень, і аналізу економічних процесів.

Усі завдання лінійного програмування можна розділити ми такі групи:

· завдання про використання ресурсів, сировини, планування виробництва;

· завдання складання раціону

· Завдання про використання потужностей, завантаженні устаткування

· Завдання прораскрое матеріалів

· Транспортні завдання

Їх розгляд не наведено, бо є необхідною для цього проекту.

Але треба представляти спільне завдання лінійного програмування (>ОЗЛП), оскільки упорядкування алгоритму треба розуміти математичний сенс виконання завдання. Нижче, наведено математичне опис загального виду завдання лінійного програмування.

>Геометрически область допустимих рішень такого завдання можна видати за багатогранник в n мірному просторі


Приклад геометричного уявлення області допустимих рішень завдання, де F - лінія цільової функції,F=0 початкове положення функції,F=F>max оптимальне становище функції, A, B, З, D, E - вершини багатокутника.

До того ж, зазвичай, оптимальне рішення це одне з його вершин. А пошук оптимуму виявляється у переході від однієї вершини до іншої і виборі оптимальної.

>Рассмотрена основна теореми лінійного програмування, з яка повинна, що й завдання лінійного програмування має оптимальне рішення, воно відповідає хоча б однієї кутової точці багатогранника прийняття рішень та збігається, по крайнього заходу, одним із допустимих базисних рішень системи обмежень. Саме там було вказано шлях розв'язання будь-який завдання лінійного програмування: перебрати кінцеве число допустимих базисних рішень системи обмежень і вибрати у тому числі то, на якому функція мети приймає оптимальне рішення.Геометрически це відповідає перебору всіх кутових точок багатогранника рішень. Такий перебір зрештою призведе оптимального рішенню (коли вона існує), але його практичне здійснення пов'язані з величезними труднощами, оскільки для реальних завдань число допустимих базисних рішень хоч і звісно, але, можливо надзвичайно великий.

Кількість які перебираються допустимих базисних рішень можна скоротити, якщо виробляти перебір не безладно, і з урахуванням змін лінійної функції, тобто. домагаючись здобуття права кожна наступна рішення вже було "краще" (чи, по крайнього заходу, "буде не гірший"), ніж попередня, по значенням лінійної функції (збільшення його при знаходженні максимуму F-> >max, зменшення — при знаходженні мінімуму F->min).


1. Формулювання проблеми, у практичної області

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

Мета роботи – визначення методу розрахунку плану перевезення продукції з

складу попредприятиям-потребителям, у якому забезпечується мінімальні транспортні Витрати перевезення всієї продукції.

Формальна (математична постановка завдань)

Завдання про розміщення (транспортна завдання) Це, у якій праці та ресурси вимірюються тільки в і тієї ж одиницях. У цих завданнях ресурси можна розділити між роботами, й окремі роботи може бути виконано з допомогою різних комбінацій ресурсів. Прикладом типовою транспортної завдання (>ТЗ) є розподіл (транспортування) продукції, яка перебуває на яких складах, попредприятиям-потребителям. Дана система зm лінійних рівнянь і нерівностей з n перемінними:

a11x1+a12x2+…+a>1nxn b1

a21x1+a22x2+…+a2Nxn b2

a>k1x1+a>k2x2+…+a>knxn b>k

a>m1x1+a>m2x2+…+a>mnxn b>m1

 

і лінійна функція

>F=c1x12x2+…+зnxn (2)

Необхідно відшукати таке рішення (план) системи


>X=(x1,x2….,xj….,xn) (3)

де

xj <>0(j=1,2,…,l, l n) (4)

у якому лінійна функція F (2) приймає оптимальне), є максимальне чи мінімальне залежно від завдання) значення. У цьому система (1) - система обмежень, а функція F (2) - цільова функція (функція мети).

Аналіз постановки завдань і обгрунтування методу рішення

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

2. Побудова моделей транспортної завдання

завдання програма модель

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

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

Особливостіекономико-математической моделі транспортної завдання:

- система обмежень є система рівнянь (тобто. транспортна завдання задана в канонічної формі);- коефіцієнти при змінних системи обмежень рівні одиниці чи нулю;- кожна змінна входить до системи обмежень двічі.

Критерій оптимальності формулюється так: базисне розподіл поставок оптимально тоді й тільки тоді, коли всіх вільних клітиннеотрицательни. >Циклом в матриці називається ламана з вершинами у клітинах і ланками, лежать вздовж рядків і шпальт матриці, що б умовам:

· ламана мусить бути зв'язковою, тобто. з її вершини потрапиш до будь-якої іншої вершину по ланкам ламаної;

· у кожному вершині ламаної зустрічаються дві ланки, одна з яких розташовується по рядку, інше - по стовпцю.

>Циклом перерахунку називається такий цикл в таблиці з базисним розподілом поставок, у якому одне з його вершин лежать у вільнішою клітині, інші - в заповнених. Цикл перерахунку називається зазначеним, тоді як його вершинах розставлено знаки "+" і "-" отож у вільної клітині стоїть знак "+", а сусідні вершини мають протилежні знаки.

Вихідні параметри моделі транспортної завдання

1) n– кількість пунктів відправлення,m – кількість пунктів призначення.

2) aі– запас продукції пункті відправлення Aі (>i=1, n) [од.прод.].

3) bj– попит продукції у пункті призначення Bj (>j=1,m) [од.прод.].

4) з>ij– тариф (вартість) перевезення одиниці виробленої продукції із відправлення aі до пункту призначення bj [>руб./ед.прод.].

>Искомие параметри моделі транспортної завдання

1) x>ij– кількість продукції, перевезеної із відправлення aі до пункту призначення bj [од.прод.].

2)L(x)– транспортні Витрати перевезення всієї продукції [крб.].

Етапи побудови моделі

I. Визначення змінних.

II. Перевірка збалансованості завдання.

III. Побудова збалансованої транспортної матриці.

IV Завдання цільової функції.

V Завдання обмежень.

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

Таблиця4.1Общий вид транспортної матриці

Пункти

відправлення, A1

Пункти споживання, Bj

Запаси,

од.прод.

B1

B2

>Bm

A1

з11, [>руб./ед.прод.]

з12

з>1m

a1

A2

з21

з22

З>2m

a2

An

З>n1

З>n2

З>nm

an

Потреба

од.прод.

b1

b2

b>m


З моделі (4.1) слід, сума запасів продукції переважають у всіх пунктах відправлення має дорівнювати сумарною потреби переважають у всіх пунктах споживання, тобто.

.

(

Якщо (4.2) виконується, тоТЗ називається збалансованої (закритою), інакше – незбалансованої (відкритої). Що стосується, коли сумарні запаси перевищують сумарні потреби, необхідний додатковий фіктивний (реально який існує) пункт споживання, який формально споживати існуючий надлишок запасів, тобто.

.

Якщо сумарні потреби перевищують сумарні запаси, то необхідний додатковий фіктивний пункт відправлення, формально який заповнює існуючий недолік продукції пунктах відправлення:

.

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

 Завдання про призначення – окреме питанняТЗ. У задачі про призначення кількість пунктів відправлення дорівнювала кількості пунктів призначення. Обсяги потреби і товарної пропозиції у кожному з пунктів призначення і відправлення рівні 1. Прикладом типовою завдання про призначення є розподіл працівників із різних видів робіт, яке мінімізує сумарне час виконання.

 Змінні завдання про призначення визначаються так

3. Реалізація алгоритму програми

Програма написана в програмної середовищі З++Builder 6.0. Задля реалізації всіх методів програми використовуються такі бібліотеки:

<>vcl.h> - бібліотека візуальнихкомпонентов(внешнее оформлення програми)

У конкурсній програмі визначено йинициализировани такі перемінні і масиви:

>massiv1[5][5] – масив потужностей постачальників і споживачів

>massiv2[5][5] - масив поставок

>massiv3[5][5] – масив значень матриці оцінок

>massiv4[5][5], >massiv5[5][5] - додаткові масиви

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


Керівництво користувача

 

Про торішню програму. Програма дозволяє перевірити правильність розв'язку транспортних завдань або ж за вас всю рутинну роботу під час вирішення з завдань. Програма дозволяє завантажувати таблиці з файла (*.>dat) чи створювати нову таблицю, шляхом створення осередків таблиці. Програма дбає про будь-який IBM сумісною машині при 32 МБОЗУ і одну МБ вільного місця на диску, будь-якою процесорі старше 486 і ОС Windows9800XP.

Опис програми. Програма має зручний і зрозумілий інтерфейс, завдяки якому вона швидко освоюється користувачем. Після запуску програми відкрито вікно введення значень.

Програма дозволяєзагружать/сохранять файли описи таблиць в форматі *.>dat. Вони уявляють собою текстові файли з параметрами вихідної завдання. Якщо файл описи завантажений, він відобразиться з вікна сторінка. Якщо це, можна жати кнопку запуску розрахунків.

Після перегляду результатів необхідно очищати елементи інтерфейсу натисканням на кнопку меню «>Сбросить». Після кожного рішення потрібно очищати запроваджені дані, інакше програма неправильно вважатиме це завдання.

Опис роботи програми. Спочатку кращої роботи необхідно завантажити файл з допомогою командиФайл>Открить.

Узятий файл відобразиться з вікна. У цьому вікні можна змінити дані відповідно до необхідної завданням. Між значеннями і наприкінці кожного рядка має бути знак прогалини.

Збереження значеньоуществляется командоюФайл->Сохранить.

Після необхідних значень потрібно натиснути кнопку “Запустити”. Після цього можна буде подивитися рішення.

Коли розподіл поставок буде оптимальним алгоритм програми закінчує своє рішення. Функція мети () і кількість кроків підраховується автоматично.

Після цього потрібні натиснути кнопку “скидання” на відновлення вихідних параметрів програми.

Для виходу з програми потрібно скористатися командоюФайл->Виход.


Укладання

 

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


Список використовуваної літератури

1.Экономико-математические методи лікування й прикладні моделі.Финстатинформ М., 1997

2.Абчук В.А.,Экономико-математические методи. Санкт-ПетербургСоюз,1999

3. РадБ.Я, Яковлєв С.А., Моделювання систем.Практикум. М. Вищашкола,1999

4. ЗамківО.О., Толстоп'ятенко А.В.,ЧеремнихЮ.Н., Математичні методи економіки.М.ДИС, 1997.


Схожі реферати:

Навігація