• 1. ЕКОНОМІЧНА ПОСТАНОВКА ЗАВДАННЯ.
  • 2. МАТЕМАТИЧНА ПОСТАНОВКА ЗАВДАННЯ. Побудова математичної моделі.
  • 3. Вибір методу РЕАЛІЗАЦІЇ МОДЕЛІ І ОБГРУНТУВАННЯ ВИБОРУ.
  • 4. символьна схема алгоритмів.
  • Процедура north_west_angle.
  • Процедура psevdostoimost.
  • Процедура sravn. Процедура sravn1.
  • 5. СУЧАСНИЙ СТАН ЕОМ ТА ЙОГО ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ.
  • 6. ОБГРУНТУВАННЯ ВИБОРУ МОВИ ПРОГРАМУВАННЯ.
  • 7. РІШЕННЯ ЗАВДАННЯ-ТЕСТУ ДЛЯ НАПИСАННЯ та налагодження програми.
  • 8. АНАЛІЗ ОТРИМАНИХ РЕЗУЛЬТАТІВ.


  • Дата конвертації16.04.2018
    Розмір21.14 Kb.
    Типреферат

    Скачати 21.14 Kb.

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

    , ВаҐе еа Е «ей е Ј®ао祣® Ґ|Ґ¤Ґў® еа пвбп 180, 350 Е 20 в. ЎҐ§Ё.
    ќв®в ЎҐ§Ё Ґ|Ґ¤Ґў® Ї® «гз ов Їпвм § Їа ў®зле бв Же © ў Є®« YoзҐc⢥ а ў®¬
    ᮮ⢥вб⢥® 110, 90, 120, 80, Е 150 в. ЎҐ§Ё.
    'В®Ё¬®бвм ЇҐаҐў®§®Є 1 ст. ЎҐ§Ё б еа Е «ей Є § Їа ў®зл¬ бв жЁп¬ § ¤ ов
    ¬ ваЁжҐ ©.

    (7 12 4 6 5)
    '= (1 8 6 5 3)
    (6 13 8 7 4)

    '®бв ўЁвм в Є® © Ї «ЇҐаҐў®§®Є ЎҐ§Ё ЇаЁ Є®в®а®¬ ®Ўй п бв®Ё¬®бвм ЇҐаҐў®§®Є
    пў «пҐвбп ¬ЁЁ¬« м® ©.

    28

    КП.2203 81-16

    ВСТУП.

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

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

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

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

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

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

    У трьох сховищах пального щодня зберігається 180, 350 і 20т бензину.

    Цей бензин щодня отримують п'ять станцій в кількостях рівних відповідно 110, 90, 120, і 150т бензину. Вартість перевезень 1т бензину з сховищ до заправних станціях задають матрицею:

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

    2. МАТЕМАТИЧНА ПОСТАНОВКА ЗАВДАННЯ. Побудова математичної моделі.

    m - сховища, в яких зберігаються бензин (i = 1,2 ... m);

    Ai - ресурси в сховищах;

    n - заправні станції j-ого виду (j = 1,2 ... n);

    Bj - заявки АЗС;

    Cij - вартість перевезень 1т бензину з i-го сховища на j-ую заправну станцію;

    xij - перевезення бензину, тобто кількість бензину перевезеного i-го сховища в j-ую заправну станцію;

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

    2. Планові обмеження:

    (J = 1,2 ... n)

    3. невід'ємності змінних:

    xij> = 0 (4)

    4. Цільова функція:

    3. Вибір методу РЕАЛІЗАЦІЇ МОДЕЛІ І ОБГРУНТУВАННЯ ВИБОРУ.

    Симплекс-метод є універсальним і застосуємо для вирішення будь-яких завдань. Однак існують деякі приватні типи завдань лінійного програмування, які в силу деяких особливостей своєї структури допускають рішення більш простими методами. Для вирішення моєї завдання доцільно використовувати транспортну задачу лінійного програмування (ТЗЛП) методом потенціалів.

    3.1. Алгоритм рішення ТЗЛП методом потенціалом.

    Будуємо закриту модель ТЗЛП, а саме: сума всіх замовлень повинна дорівнювати сумі всіх заявок:

    Якщо дотримуватися модель умовно, то така модель називається закритою.

    Якщо умова не дотримуватися, то така модель ТЗЛП з неправильним балансом.

    У цьому випадку може бути два варіанти:

    а) ТЗ з надлишком запасу

    вводимо фіктивного споживача (фіктивний стовпець), яким приписуємо заявку, рівну різниці запасів і заявок:

    Сiф = 0, (i = 1,2 ... m) - вартість фіктивних перевезень дорівнює нулю.

    Це означає, що якщо в якійсь комірці фіктивного стовпчика за планом буде стояти перевезення xij, то фактично ці перевезення залишаться відправленими. Вводять Bф з його заявкою Bф, ми зрівнює баланс ТЗ, і тепер це завдання можна вирішувати як звичайну ТЗ.

    б) ТЗ з надлишком заявок

    вводимо фіктивного постачальника (фіктивна рядок), яким описуємо замовника AФ:

    Сij = 0 (j = 1,2 ... n)

    В даному випадку ми зводимо ТЗ з надлишком заявок до ТЗ з правильним балансом, при цьому ми не вважали за потрібне, про справедливість задоволення заявок - нас цікавили лише витрати, які треба мінімізувати.

    Складаємо перший опорний план перевезень, в яких забезпечені

    m + n-1 базисних клітин, за методом північно-західного кута.

    Припустимо, план називається опорним, якщо в ньому відмінних від нуля не більше ніж

    r = m + n-1 базисних змінних (перевезень), а інші рівні нулю.

    План (xij) називається оптимальним, якщо він серед усіх допустимих планів призводить до найменшої вартості всіх перевезень.

    Таблиця 2.

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

    ПО / ПН

    B1

    B2

    ... Bn

    ЗАПАСИ ai

    A1

    A2

    ...

    Am

    C11

    C21

    ...

    Cm1

    C12

    C22

    ...

    Cm2

    ... C1n

    ... C2n

    ... ...

    ... Cmn

    a1

    a2

    ...

    am

    ЗАЯВКИ bJ

    b1

    b2

    ... bn

    ПН - пункт призначення;

    ПО - пункт відправлення.

    У правих верхніх кутах кожного осередку вказана стоімоть перевезень з кожного i-ого пункту в кожен j-ий пункт.

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

    Для цього порівнюємо а1 з b1. Менший з обсягів записуємо в клітку А1В1.

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

    Клітини таблиці, в яких не нульові перевезення є базисними, і їх число задовольняє умові r = m + n-1. Інші клієнти вільні в них стоять нульові перевезення, їх число дорівнює (n-1) * (m-1). Отримане рішення є не тільки допустимим, але і опорним рішенням ТЗ.

    Якщо число базисних клітин r m + n-1, то вводимо r нескінченно малих фіктивних перевезень, наприклад.

    Для першого плану будуємо систему платежів. Припустимо, що кожен з пунктів відправлення А: вносить за перевезення одиниці, якусь суму i, якомусь третій особі; в свою чергу кожен з пунктів значення Bj так само вносить за перевезення одиниці вантажу цього ж особі суму j. i і j називаються платежами. Позначимо суму цих платежів:

    Si, j = i + j, (12)

    (I = 1,2 ... m, j = 1,2 ... n)

    і назвемо псевдостоімость.

    Теорема платежів:

    якщо:

    а) для базисних клітин (xi, j> 0) i + j = Si, j = Ci, j (псевдостоімость дорівнює вартості);

    б) для вільних клітин (xi, j0) i + j = Si, j> 0 (псевдостоімость більше вартості), то план не є оптимальним.

    Якщо ж перша умова виконується, а друге Si, jCi, j, то план є оптимальним і ніяким чином покращено бути не може.

    За допомогою базисних клітин, в яких сума цих платежів дорівнює Si, j = Ci, j = i + j (i = 1,2 ... mj = 1,2 ... n), а число базисних клітин одно r, то перший платіж значенням довільно (наприклад, 1 = 0).

    Знаходимо псевдостоімость для всіх вільних осередків, і якщо в кожної вільної клітці Si, jCi, j, то план оптимальний і вважаємо цільову функцію.

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

    4. символьна схема алгоритмів.

    Процедура balans.







    Процедура north_west_angle.





    Процедура PEpsilon.




    Процедура psevdostoimost.








    Процедура Pmax.Процедура Px1.










    Процедура Pschet.











    Процедура sravn. Процедура sravn1.








    Процедура Px.








    Основна програма.













    5. СУЧАСНИЙ СТАН ЕОМ ТА ЙОГО ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ.

    У цій роботі використовувалася ЕОМ - IBM PC до складу якої входять:

    1.Сістемний блок з пороцессором Intel Pentium II з тактовою частотою 300 MHz, оперативною пам'яттю 64 Мb, з графічним адаптером ATI 3D RAGE PRO і вінчестером Western digital об'ємом 4 Gb.

    2.Клавіатура типу IBM PS / 2.

    3.Маніпулятор типу "Microsoft Inteli Mouse".

    4.Моніор SVGA SONY "Trinitron".

    5.Прінтер HP DeskJet 400 Color.

    6. ОБГРУНТУВАННЯ ВИБОРУ МОВИ ПРОГРАМУВАННЯ.

    Для реалізації даної програми була вибрана Турбо Паскаль - універсальна мова програмування високого рівня.

    Як відомо, в даний час найбільш поширеним алгоритмічною мовою є Паскаль. Саме ця мова використовується практично на всіх діючих обчислювальних системах - від супер ЕОМ до персональних комп'ютерів.

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

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

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

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

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

    Велику допомогу програмістам надає бібліотека стандартних програм Турбо Паскаля. Ця бібліотека модернізується і поповнюється вже понад 5 років. У неї входять засоби для роботи з оперативною та зовнішньою пам'яттю, клавіатурою, дисплеєм і іншими зовнішніми пристроями ПЕОМ.

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

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

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

    7. РІШЕННЯ ЗАВДАННЯ-ТЕСТУ ДЛЯ НАПИСАННЯ та налагодження програми.

    Складемо математичну модель задачі. Будемо вважати, що i-ий тип верстатів зайнятий виготовленням j-го виду тканин xi, j ст. / Год. Тоді змінні xi, j повинні відповідати таким умовою:

    x11 + x12 + x13 + x14 = 180

    x21 + x22 + x23 + x24 = 350 (1)

    x31 + x32 + x33 + x34 = 20

    x11 + x12 + x13 = 110

    x21 + x22 + x23 = 90 (2)

    x31 + x32 + x33 = 120

    x41 + x42 + x43 = 80

    x51 + x52 + x53 = 150

    Змінні повинні задовольняти умові незаперечності:

    xi, j0 (i = 1,2 ... m, j = 1,2 ... n) (3)

    Серед усіх можливих значень невідомих, які задовольняють умову (1), (2) і (3), потрібно знайти таке, при якому лінійна функція: Fmin = 7x11 + 12x12 + 4x13 + 6x14 + 5x15 + x21 + 8x22 + 6x23 + 5x24 + 3x25 + 6x31 + 13x32 + 8x33 +

    + 7x34 + 4x35, прийме найменше значення.

    Так як отримана завдання має відкриту модель, а саме:

    Тому, згідно з умовою (8), щоб знайти її рішення, вважаємо, що є фіктивна потреба в тканинах, на вироблення яких необхідно затратити:

    Отриману задачу вирішуємо методом потенціалів:

    1 ітерація

    ПО / ПН

    B1

    B2

    B3

    B4

    B5

    ai

    i

    А1

    7

    110

    12

    70

    4

    9 6

    5

    180

    0

    j

    7

    12

    10

    9

    7

    r = m + n-1 = 7

    2 ітерація

    ПО / ПН

    B1

    B2

    B3

    B4

    B5

    ai

    i

    А1

    7 7

    110

    6 12

    4 4

    70

    3 6

    1 5

    180

    0

    j

    7

    6

    4

    3

    1

    r = m + n-1 = 7

    3 ітерація

    ПО / ПН

    B1

    B2

    B3

    B4

    B5

    ai

    i

    А1

    7 7

    60

    14 12

    4 4

    120

    11 6

    1 5

    180

    0

    j

    7

    14

    4

    11

    9

    r = m + n-1 = 7

    4 ітерація

    ПО / ПН

    B1

    B2

    B3

    B4

    B5

    ai

    i

    А1

    2 7

    9 12

    4

    120

    6

    60

    4 5

    180

    0

    j

    2

    9

    4

    6

    4

    В останній ітерації план є оптимальним, тюкю в кожній порожній клітці Si, jCi, j.

    Використовуючи співвідношення (4), для визначення оптимального плану вихідної завдання, отримаємо матрицю:

    Отримано оптимальний план:

    Fmin = 4 * 120 + 6 * 60 + 1 * 110 + 8 * 90 + 5 * 20 + 3 * 130 + 4 * 20 = 2240 руб.

    8. АНАЛІЗ ОТРИМАНИХ РЕЗУЛЬТАТІВ.

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

    а) з першого сховища 120т бензину на третю заправну станцію і 60т бензину на четверту;

    б) з другого сховища 110т бензину на першу заправну станцію, 90т бензину на другу, 20т бензину на четверту і 130т бензину на п'яту заправну станцію;

    в) з третього сховища 20т бензину на п'яту заправну станцію.

    При отриманому плані перевезень бензину їх вартість є мінімальною і становить: Fmin = 2240 руб.

    Всі результати тесту-завдання повністю сходяться з отриманими результатами машинного рахунку (дивись додаток).

    ВИСНОВОК.

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

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

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

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

    ЛІТЕРАТУРА.

    Малик Г.С. "Основи економіки і матемотіческіе методи в плануванні", Москва "Вища школа", 1988р.

    Акуліч І.Л. "Матемотіческое програмування в прикладах і завданнях", Москва "Вища школа", 1986р.

    ДОДАТОК.