На головну    

 Мінімізація вартостей перевезень - Економіко-математичне моделювання

Московський Державний Коледж

Інформаційних Технологій

Курсовий проект

по предмету

«Мови програмування та розробка

програмного забезпечення »

на тему:

«Мінімізація вартостей перевезень»

Роботу виконав Роботу перевірили

студент групи П-407 Викладачі

Чубаков А.С. Капустіна Р.Н.

Токарев С.Б.

1998

КР. 2203 81 - 21

ВСТУП

Розвиток сучасного суспільства характеризується підвищенням технічного

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

Рішення екстремальних економічних задач можна розбити на три етапи:

Побудова економіко - математичної задачі.

Знаходження оптимального рішення одним з математичних методів.

Промислове впровадження в народне господарство.

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

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

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

Динамічне програмування як самостійна дисципліна сформулювалася в п'ятдесятих роках нашого століття. Великий внесок у її розвиток вніс американський математик Р. Бельман. Подальші розвиток динамічне програмування отримало

в працях зарубіжних вчених Робертса, Ланга та ін.

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

КР. 2203 81 - 21

2. ЕКОНОМІЧНА ПОСТАНОВКА ЗАВДАННЯ

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

відповідно в кількостях, рівних 50, 30 і 10 одиниць. Цю продукцію отримують чотири споживача, розташованих у різних

місцях. Їхні потреби відповідно рівні 30, 30, 10 і 20 одиниць. Тарифи перевезень одиниці продукції від кожного філій відповідним споживачам задаються матрицею:

1 лютому 4 січня

Сij = 2 березня 1 травня

2 Березня 4 квітня

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

КП. 2203 81 - 21

2.МАТЕМАТІЧЕСКАЯ ПОСТАНОВКА ЗАВДАННЯ

2. Математична модель задачі

Мається:

m (i = 1,2, ..., m) - філії.

Ai - кількість одиниць продукції «i» філії.

n (j = 1,2, ..., n) - споживачі

Bj - потреби «j» споживача

Cij - вартість перевезення 1 умовної одиниці продукції

від «i» філії до «j» споживачеві

Обмеження:

Балансове обмеження.

Передбачається, що сума всіх запасів (ai) дорівнює сумі всіх заявок (bj):

2. Ресурсне обмеження.

Сумарна кількість вантажу, направленого з кожного пункту відправлення в усі пункти призначення має дорівнювати запасу вантажу в даному пункті. Це дасть m - умов рівності:

або

3. Планове обмеження.

Сумарна кількість вантажу, що доставляється в кожний пункт призначення з усіх пунктів відправлення має дорівнювати заявці (bj) поданої даним пунктом. Це дасть нам n - умов рівності:

КП. 2203 81 - 21

або

4. Реальність плану перевезень.

Перевезення не можуть бути негативними числами:

5. Потрібно скласти такий план перевезень, при якому всі заявки були б виконані і при цьому загальна вартість всіх перевезень була б мінімальна, тому цільова функція або критерій ефективності:

КП. 2203 81 - 21

3.Вибор МЕТОДУ РЕАЛІЗАЦІЇ ПРОДУКЦІЇ.

ОБГРУНТУВАННЯ ВИБОРУ МЕТОДУ.

Симплекс - метод є універсальним і застосовується для вирішення будь-яких завдань.

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

які в силу деяких особливостей своєї структури допускають рішення більш

простими методами. До них відноситься транспортна задача.

Розподільний метод вирішення транспортної задачі володіє одним

недоліком:

потрібно відшукувати цикли для всіх вільних клітин і знаходити їх ціни. Від цієї

трудомісткої роботи нас позбавляє спеціальний метод вирішення транспортної

задачі, який називається методом потенціалів. Він дозволяє автоматично

виділяти цикли з негативною ціною і визначати їх ціни.

На відміну від загального випадку ОЗЛП з довільними обмеженнями та

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

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

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

Визначення значень xi, jначінается з лівої верхньої клітини таблиці. Знаходимо значення x1,1із співвідношення x11 = min {a1, b1}.

Якщо ai1то x11 = a1, рядок i = 1 виключається з подальшого розгляду, а потреба першого споживача b1уменьшается на величину a1.

Якщо a1> b1, то x11 = b1, стовпець j = 1 виключається з подальшого розгляду, а наявність вантажу у першого постачальника a1уменьшается на величину b1.

Якщо a1 = b1, то x11 = a1 = b1, рядок i = 1 і стовпець j = 1 виключаються з подальшого розгляду.

Даний варіант призводить до виродження вихідного плану.

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

Якщо кількість заповнених клітин одно m + n -1, то план є невиродженим. Якщо план вироджений, тобто кількість заповнених клітин стало менше m + n -1, то незаповнені клітини з мінімальними вартостями перевезень заповнюються нулями, щоб загальні кількість заповнених клітин стало рівним

m + n -1.

Транспортна задача з неправильним балансом називається відкритою моделлю.

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

Коли еai> еbjето транспортна задача з надлишком запасів.

еxijеai, то таке завдання називається - транспортна задача з надлишком запасу. Це завдання можна звести до звичайної задачі з правильним балансом, якщо ввести фіктивний пункт відправлення AФ, приписавши йому фіктивний запас AФ = еbj- еai. Додаємо фіктивну рядок, де Cфi = 0 (j = 1, n).

Вартості будуть рівні нулю. це означає, що частина заявок cфjостанутся незадоволеними. Серед них можуть виявитися ті потреби, які необхідно обов'язково задовольнити. Для цього вводимо коефіцієнт:

R = еai: еbjі кожен запас bjумножаем на цей коефіцієнт. Таким чином задача зведена до транспортної задачі з правильним балансом.

Побудований вище вихідний план можна довести до оптимального за допомогою методу потенціалів.

Кожному постачальнику Aiпоставім відповідно деякі числа ai, звані потенціалом, а кожному споживачу Bj- число bj.

Для кожної незалежної клітини, т.е для кожної незалежної змінної розраховуються так звані непрямі тарифи (Cўij) за формулою

Cўij = ai + bj. А для заповнених клітин, т.е базисних змінних Cўij = Cij.

Перевіряємо отриманий план на оптимальність. Якщо для кожної незалежної клітини виконується умова Cўij- CijCij, то слід приступити до поліпшення плану.

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

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

У кожної клітини циклу, починаючи з вільною, проставляються по черзі знаки

І + І і І - ІV. У клітинах зі знаком І - І вибирається мінімальна величина. Новий базисний план починається шляхом складань обраної величини з величинами, що стоять в клітинах циклу зі знаком І + І і відніманням цієї величини з величини, що стоїть у клітці зі знаком І - ІV. Обрана мінімальна величина буде відповідати перемененной виведеної з базису.

КП. 2203 81 - 21

Значення змінних включених в цикл, після описаної коригування, переносяться в нову таблицю.

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

F = її Cij · cijmin.

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

КР. 2203 81 - 21

5.КРАТКАЯ ХАРАКТЕРИСТИКА ЕОМ та його програмного забезпечення.

Слово «комп'ютер» означає «обчислювач», тобто пристрій для обчислень.

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

Комп'ютер - це універсальний прилад для переробки інформації. Але сам по собі комп'ютер є просто ящиком з набором електронних схем. Він не володіє знаннями в жодній області свого застосування. Всі ці знання зосереджені у виконуваних на комп'ютері програми. Для того, щоб комп'ютер міг здійснити певні дії, необхідно скласти для комп'ютера програму, т.е точну і підлогу = дробову послідовність інструкцій на зрозумілій комп'ютері мовою, як треба правильно обробляти інформацію. Змінюючи програми для комп'ютера, можна привести його в робочі місце бухгалтера мул конструктора, статистика або агронома, редагувати документ або грати в ігри. Тому для ефективного використання комп'ютера необхідно знати призначення і властивості необхідні при роботі з ним програм.

Програми. працюють на комп'ютери можна розділити на три категорії:

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

картинок, обробку інформаційних масивів і т.д.

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

Інструментальні системи (системи програмування), забезпечують створення нових програм для комп'ютера.

КР. 2203 81 - 21 6.ОБОСНОВАНІЕ ВИБОРУ МОВИ

У 1992 році фірма Borland International випустила два пакети програмування, засновані на використанні мови Паскаль - Borland Pascal 7.0 і Turbo Pascal 7.0. Система програмування Turbo Pascal, розроблена американською корпорацією Borland

залишається однією з найпопулярніших систем програмування у світі. Цьому сприяє, з одного боку, простота лежить в основі цього мови програмування Паскаль, а з іншого - праця і талант співробітників Borland на чолі з ідеологом і творцем Turbo Pascal Андерс Гейлсберг, які доклали чимало зусиль до її вдосконалення. Придуманий швейцарським ученим Никласом Віртом як засіб для навчання студентів програмуванню, мова Паскаль стараннями А. Хейлсберг перетворилася на потужну сучасну професійну систему програмування, якій до снаги будь-які завдання - від створення простих програм, призначених для вирішення нескладних обчислювальних завдань, до розробки найскладніших реляційних систем управління базами даних. Поява Windows та інструментальних засобів Borland Pascal with Object і Delphi для розробки програм в середовищі Windows зайвий раз показало, які воістину не є вичерпними можливості таїть він в собі: і Borland Pascal, і використовуваний в Delphi мову Object Pascal грунтуються на Турбо Паскалі і розвивають його ідеї .

Пакет Turbo Pascal включає в себе як мова програмування - одне з розширень мови Паскаль для ЕОМ типу IBM, так і середу, призначену для написання, налагодження і запуску програм.

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

середовище програмування дозволяє створювати тексти програм. компілювати їх, знаходити і справляти помилки, компонувати програми з окремих частин. включаючи стандартні модулі, налагоджувати і виконувати налагоджену програму. Пакет представляє користувачеві великий обсяг довідкової інформації, дозволяє застосовувати об'єктне - орієнтоване програмування, володіє вбудованим асемблером, має інструментальний засіб для створення інтерактивних програм - Turbo Vision і т.д.

КР. 2203 81 - 21

7.РЕШЕНІЕ ЗАВДАННЯ ТЕСТУ ДЛЯ написання і налагодження ПРОГРРАММИ.

 B1

 B2

 B3

 B4

 a i

 a i

 A1

 1 січня

 30

 2 лютого

 20

 0 4

 1 квітня

 50

0

 A2

 2 лютого

 3 березня

 10

 1 січня

 10

 5 травня

 10

 30

1

 A3

 3 січня

 2 лютого

 0 4

 4 квітня

 10

 10

0

 заявки

 b j

 30

 30

 10

 20

 90

 B j

1

2

0

4

1,2 1,4

10

2,2 2,4

 B1

 B2

 B3

 B4

 a i

 a i

 A1

 1 січня

 30

 2 лютого

 10

 0 4

 1 січня

 10

 50

0

 A2

 2 лютого

 3 березня

 20

 1 січня

 10

 5 лютого

 30

1

 A3

 4 березня

 5 лютого

 4 березня

 4 квітня

 10

 10

3

 b j

 30

 30

 10

 20

 90

 B j

1

2

0

1

1,1 1,4

10

3,1 3,4

КР. 2203 81 - 21

 B1

 B2

 B3

 B4

 a i

 a i

 A1

 1 січня

 20

 2 лютого

 10

 0 4

 1 січня

 20

 50

0

 A2

 2 лютого

 3 березня

 20

 1 січня

 10

 5 лютого

 30

1

 A3

 3 березня

 10

 2 квітня

 2 квітня

 4 березня

 10

2

 b j

 30

 30

 10

 20

 90

 Bj

1

2

0

1

1,1 1,2

10

3,1 3,2

 B1

 B2

 B3

 B4

 a i

 a i

 A1

 1 січня

 30

 -1 2

 -3 4

 1 січня

 20

 50

0

 A2

 5 лютого

 3 березня

 20

 1 січня

 10

 5 травня

 30

4

 A3

 4 березня

 2 лютого

 10

 0 4

 4 квітня

E

 10 + E

3

 b j

 30

 30

 10

 20 + E

 90 + E

 B j

1

 -1

 -3

1

1,1 1,2

10

2,1 2,2

КР. 2203 81 - 21

 B1

 B2

 B3

 B4

 a i

 a i

 A1

 1 січня

 10

 2 лютого

 20

 0 4

 1 січня

 20

 50

0

 A2

 2 лютого

 20

 3 березня

 1 січня

 10

 5 лютого

 30

1

 A3

 3 січня

 2 лютого

 10

 0 4

 1 квітня

 10

0

 b j

 30

 30

 10

 20

 90

 B j

1

2

0

1

Fmin = 1 · 10 + 2 · 20 + 2 · 10 + 1 · 10 + 2 · 20 + 20 * 1 = 140

Знайдений оптимальний план перевезень, рівний 140.

КР. 2203 81 - 21

8.Аналіз ОТРИМАНИХ РЕЗУЛЬТАТІВ

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

Cўij-Cij

© 8ref.com - українські реферати