• 1.2 Економічна постановка задачі
  • 1.3 Економіко-математичне моделювання
  • 1.4 Математична постановка задачі
  • 1.5 Транспортна задача з обмеженими можливостями транспортних засобів
  • 1.6 Рішення транспортної задачі з обмеженими можливостями транспортних засобів угорським методом
  • 2. Практична частина


  • Дата конвертації12.05.2017
    Розмір24.32 Kb.
    Типконтрольна робота

    Скачати 24.32 Kb.

    Транспортна задача з обмеженнями можливих транспортних засобів

    1. Теоретична частина

    1.1 Характеристика підприємства

    Товариство з обмеженою відповідальністю ТОВ "Реверс" як юридична особа було зареєстровано 11 листопада 1999 року і є найбільшим постачальником комп'ютерної техніки в Екібастузі.

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

    виробництво і постачання комп'ютерів, серверів, комплектуючих і периферійних пристроїв;

    поставка копіювальної техніки;

    реалізація ліцензійного програмного забезпечення;

    реалізація і обслуговування копіювальної техніки;

    прокладка локальних мереж;

    впровадження і підтримка інформаційних систем на базі програмних продуктів "Фірми 1С";

    Розробка та підтримка веб-сайтів;

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

    Завдяки тісній співпраці з виробниками, в техцентр Revers завжди низькі ціни і широкий асортимент товару. Є власний авторизований сервісний центр ТОВ "Аверс-Сервіс" спеціалізується на ремонті і обслуговуванні побутової техніки, електроніки, кондиціонерів.

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

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

    1.2 Економічна постановка задачі

    Техцентр "Реверс" у 2009 році в жовтні місяці оголосив знижки на весь місяць за наступними відділам: Відділ копіювальної техніки і заправки картріджів (B1) Відділ продажу комп'ютерної техніки (B2) Відділ ремонту та обслуговування комп'ютерної техніки (B3)

    У жовтні місяці заявки в Техцентр "Реверс" зробили чотири організації: ЗОШ 24 (A1) ЗОШ 35 (A2) ЦТДЮ "Кайнар" (A3) Комп'ютерний клуб (A4).

    Для ЗОШ 24 від техцентра "Реверс" у зв'язку з акцією у всіх відділах були зроблені знижки. У відділі копіювальної техніки та заправки картриджів знижка в 5%, у відділі продажу комп'ютерної техніки 10%, у відділі ремонту та обслуговування комп'ютерної техніки 10%.

    Для ЗОШ 35 від техцентра "Реверс" у зв'язку з акцією у всіх відділах були зроблені знижки. У відділі копіювальної техніки та заправки картриджів знижка в 5%, у відділі продажу комп'ютерної техніки як постійному клієнтові знижка 15%, у відділі ремонту та обслуговування комп'ютерної техніки в 12%,

    Для ЦТДЮ "Кайнар" в зв'язку з акцією у всіх відділах були зроблені знижки. У відділі копіювальної техніки та заправки картриджів знижка в 3%, у відділі продажу комп'ютерної техніки знижка в 5%, у відділі ремонту та обслуговування комп'ютерної техніки 6%.

    Для Комп'ютерного клубу "Бест" у всіх відділах були зроблені знижки. У відділі копіювальної техніки та заправки картриджів знижка в 2%, у відділі продажу комп'ютерної техніки знижка в 5%, у відділі ремонту та обслуговування комп'ютерної техніки 6%.

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

    При обслуговуванні відділом продажу ЗОШ 24 повинен бути не більше 15 продажів, обслуговування відділу ремонту для ЗОШ 24 повинен бути не менше 15 викликів.

    Таблиця 2.1 - Вихідна таблиця

    ai / bj

    B1

    B2

    B3

    B4

    25

    25

    15

    25

    A1

    40

    10

    15

    5

    5

    A2

    30

    10

    12

    6

    6

    A3

    30

    5

    5

    3

    2

    Х11 <= 15 x12> = 15

    1.3 Економіко-математичне моделювання

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

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

    Система обмежень складається з окремих математичних рівнянь або нерівностей, званих балансовими рівняннями чи нерівностями.

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

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

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

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

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

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

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

    1.4 Математична постановка задачі

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

    (1.1)

    i = 1,2, ..., m, (1.2)

    j = 1,2, ..., n, (1.3)

    i = 1,2, ..., m; j = 1,2, ..., n. (1.4)

    Цільова функція задачі (1.1) виражає вимоги забезпечити мінімум сумарних витрат на перевезення всіх вантажів. Перша група з т рівнянь (1.2) описує той факт, що запаси всіх т постачальників вивозяться повністю. Друга група з n рівнянь (1.3) виражає вимоги повністю задовольнити запити всіх n споживачів. Нерівності (1.4) є умовами невід'ємності всіх змінних завдання.

    Таким чином, математична формулювання транспортної задачі полягає в наступному: знайти змінні завдання

    i = 1,2, ..., m; j = 1,2, ..., n, (1.5)

    задовольняє системі обмежень (1.2), (1.3), умовами невід'ємності (1.4) і забезпечує мінімум цільової функції (1.1).

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

    . (1.6)

    1.5 Транспортна задача з обмеженими можливостями транспортних засобів

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

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

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

    (1.7)

    i = 1,2, ..., m, (1.8)

    j = 1,2, ..., n, (1.9)

    (1.10)

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

    Якщо позначитися транспортні можливості між пунктами I і j через dij, то кількість вантажу , Яке може бути перевезено за цим напрямком за планований період часу, не повинно перевищувати транспортних можливостей, т.е.

    (1.11)

    Тоді обмеження 1.10, 1.11 об'єднуються, і модель завдання ускладнюється двосторонніми обмеженнями на змінні

    (1.12)

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

    i = 1,2, ..., m, (1.13)

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

    i = 1,2, ..., n, (1.14)

    Існують різні підходи до вирішення цього завдання. Розглянемо найбільш простий з них.

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

    Потужність умовного постачальника А 'i - приймається рівний встановленої можливості засобів, що з'єднують пункт і з споживачами j

    A 'i = d ij (1.15)

    а потужність умовного постачальника А 'j - що дорівнює різниці між заданими в умові завдання потужністю постачальника в пункті I і можливістю засобів між I-м і j-м пунктами, тобто

    a '' i = a i -d ij. (1.16)

    При цьому витрати на поставку вантажів з пунктів I 'в пункт jc ij приймаються рівними дійсним витратам c ij наведеним в умові завдання. В оптимальному рішення змінні х ij можуть мати будь-який позитивне значення від нуля до a 'i, тобто

    (1.17)

    На відміну від них змінні х ij в оптимальному рішенні неодмінно повинні бути рівні нулю, оскільки потужність А 'j характеризує кількість в пункті і понад встановлену засобів, що з'єднують пункти i і j, отже це частина вантажу повинна бути спрямована не j-му а будь-якого іншого споживачеві. Для того, щоб в оптимальному рішенні забезпечити значення змінних х ij дорівнює нулю, витрати на поставку вантажу з пункту i '' в пункт j приймаються рівними М, т. Е c ij = М.

    При мінімізації цільової функції (1.7) і коефіцієнтах c ij = М, в оптимальному вирішенні отримаємо

    Звідси слідує що

    X ij = X i 'j + X i' j = X ij (1.18)

    Тоді, виходячи з умов (1.15), (1.17), отримаємо

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

    Якщо для якоїсь пари пунктів виробництва i споживання s транспортні можливості не обмежені, обсяг поставки вантажу від постачальника Аi до споживача B s визначиться як сума значень пари відповідних змінних:

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

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

    Попередній етап. За вихідній матриці С виконується побудова матриці С ', а потім матриці Co, за відомими правилами.

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

    Розмітка. На етапі розмітки відзначають символом "+" стовпці з нульовими невязке і суттєві нулі матриці С. Точкою відзначають істотні неповні нулі, а двома точками - повні. Несуттєві нулі залишаються без розмітки. З точки зору комунікації вони є неповними.

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

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

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

    Розрахунок цільової функції.

    2. Практична частина

    2.1 Опис алгоритму реалізації моделі

    Визначившись з методами, які ми будемо використовувати в рішенні завдання, приступимо до безпосереднього отримання результату. Рішення транспортної задачі починається з знаходження опорного плану. Для цього існують різні способи. Наприклад, спосіб "Метод обмежень" / Умови транспортної задачі задані транспортної таблицею (2.1).

    Таблиця 2.1 - Умова транспортної задачі

    ai / bj

    B1

    B2

    B3

    B4

    25

    25

    15

    25

    A1

    40

    10

    15

    5

    5

    A2

    30

    10

    12

    6

    6

    A3

    30

    5

    5

    3

    2

    В даному випадку Σa i = 100 = Σb j = 100 маємо справу із закритою моделлю транспортної задачі.

    Вводимо кількість постачальників і споживачів, потім будуємо матрицю елементи якої відображають вартість перевезення. Якщо завдання за умовою не є збалансованою, то для цього додаємо фіктивний пункт виробництва і споживача. У нашому випадки завдання є збалансованою, для її вирішення будуємо матрицю Х ij - план перевезень. Елементи цього типу характеризують кількість товарів, яке буде переміщатися від i-го постачальника до j-му споживачеві. Виводимо цільову функцію (див малюнок 2.1)


    Малюнок 2.1 - блок-схема підпрограми перевірки на умову балансу.


    Відбувається початкове обчислення опорного плану.

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

    На етапі розмітки відзначають символом "+" стовпці з нульовими невязке і суттєві нулі матриці С. Точкою відзначають істотні неповні нулі, а двома точками - повні. Несуттєві нулі залишаються без розмітки. З точки зору комунікації вони є неповними.

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

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

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

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

    Додається h до виділених елементів і віднімається з невиділених. Якщо двічі виділений елемент стає рівним нулю, то його виділяють "*" Знак виділення на колонку знімається.



    Малюнок 2.2 - Загальний алгоритм обчислення опорного плану

    Обчислення нев'язки.

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

    Після заповнення елемента плану обсяги виробництва і споживання коригуються. Корекції передує побудова ланцюжка. Ланцюжок містить обов'язково непарне число нулів і в принципі може складатися з одного нуля. Побудова ланцюжка починається з останнього знайденого нуля зі штрихом. Потім по стовпу до нуля із зірочкою, а вже від нього по рядку до нуля зі штрихом. Для корекції плану вибирається коригувальний елемент . Він вибирається з невязки рядки спочатку, з невязки кінця ланцюжка і елементів кінця Х, відповідних нулях із зірочкою, які увійшли в ланцюжок. елемент додається до елементу Х ij, якщо йому в ланцюжок відповідав елемент З ij = 0 ', і віднімається від елемента Х ij, якщо в ланцюжку йому відповідав елемент З ij = 0 *. Для корекції плану розраховується нев'язка по рядках і стовпцях, а так само сумарна нев'язка.

    Розраховуються невязки по стовпцях і рядках.

    Невязка по рядку , I = 1, m, j = 1, n (2.19)

    Невязка по рядку , I = 1, m, j = 1, n (2.20)

    Потім розраховується сумарна нев'язка плану

    Δ (2.21)


    Якщо сумарна нев'язка плану  = 0, то це говорить про отримання оптимального рішення. Якщо  не дорівнює 0, то переходимо до етапу розмітки. Виводимо L - загальна вартість перевезень (див малюнок 2.3).

    Малюнок 2.3 - блок - схема підпрограми обчислення нев'язки.


    Опис програми.

    Опис роботи програми:

    користувач вводить кількість постачальників і споживачів;

    користувач вводить всі дані про постачальників і споживачів;

    користувач вводить обмеження;

    будує матрицю С ij, елементи якої відображають певну знижку;

    Всі використовувані в програмі змінні і підпрограми, коротко описані в таблицях 2.1

    Опис блок-схеми:

    блок-схема перевірка на умова балансу представлена ​​на малюнку 2.1;

    блок - схема загального алгоритму обчислення опорного плану представлена ​​на малюнку 2.2;

    блок схема обчислення нев'язки представлено на малюнку 2.3

    Таблиця 2.1 -Іспользуемие змінні

    ім'я

    Тип

    опис

    Cont

    TZLPTableContext

    У кожній конкретній бібліотеці буде свій тип контексту

    значення функції

    Integer

    Код повернення:

    ResultError = - 1 - помилка в алгоритмі;

    ResultFinish = 0 - успішне закінчення розрахунків;

    ResultNoSolution = 1 - немає рішення;

    SourceF

    TFunction

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

    Limitations

    TLimitations

    обмеження

    MinMax

    TFunctionType

    Функція на мінімум або максимум.

    ftMin - мінімум;

    ftMax - максимум.

    Len

    Integer

    Довжина масиву обмежень

    Factors

    TDynIntegerArray

    Масив обмежень: послідовність з Len цілих чисел (Integer)


    Головна сторінка


        Головна сторінка



    Транспортна задача з обмеженнями можливих транспортних засобів

    Скачати 24.32 Kb.