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

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

скачати

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 - блок-схема підпрограми перевірки на умову балансу.
початок
Введення кількості постачальників і споживачів a i b i
Будуємо матрицю З ij (i = 1, m; j = 1, n), елементи якого відображають знижку
Побудувати матрицю Х ij
Завдання відкритого типу
Додавання фіктивного споживача

Завдання закритого типу

Додавання фіктивного споживача

кінець


Відбувається початкове обчислення опорного плану.
Побудова плану виконується зверху-вниз по стовпцях матриці Co починаючи з лівого, для O матриці Co, при цьому враховується пропускна можливість комунікацій.
На етапі розмітки відзначають символом "+" стовпчики з нульовими нев'язками і суттєві нулі матриці С. Точкою відзначають істотні неповні нулі, а двома крапками - повні. Несуттєві нулі залишаються без розмітки. З точки зору комунікації вони є неповними.
Метою пошуку є відшукати неповний нуль (без різниці істотний або несуттєвий), розташований у рядку з повною нев'язкої. Алгоритм пошуку по колонках відомий.
Елемент який стоїть на перетині виділеної рядки і виділеного стовпця називається двічі виділеним.
Вибирається коригувальний елемент h. Коригувальний елемент отримуємо як мінімальний позитивний елемент серед невиділений частині матриці, або як мінімальний модуль двох виділених негативних елементів
Якщо пошуковий етап закінчився невдачею в невиділений частині матриці елементи непозитивно, а всі двічі виділені елементи ненегативні, то завдання нерозв'язна при даних обмеженнях на пропускну здатність.
Додається h до виділених елементів і віднімається з невиділених. Якщо двічі виділений елемент стає рівним нулю, то його виділяють "*" Знак виділення над стовпцем знімається.

кінець
Обчислення опорного плану
Якщо сумарна нев'язка = 0
a [i, j] <min then
min: = a [I, j]
Мінімальний елемент вичитується з усіх елементів
стовпця
Сij-m
Відшукується мінімальний елемент у кожному рядку
m '
C'-нова матриця
C o
Мінімальний елемент вичитується з усіх елементів рядка
З ij - m
Будується початковий план
X o з С про
Чи зараховується нев'язки по рядках і стовпцях і сумарна нев'язка
оптимум
Так
Ні
min: = a [1,1]

Рисунок 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)
кінець
D = 0
Х про
початковий план
Висновок
L
Х ij = min {a i, b j}
a i = a i - x ij
bj = b j - x ij
Невязка по рядку
, I = 1, m, j = 1, n
Невязка за стовпцем
, I = 1, m, j = 1, n
Сумарна нев'язка
D
Оптимальне рішення
Перехід до етапу розмітки

Якщо сумарна нев'язка плану  = 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)
Значення функції
TIntegerMatrix
матриця з цілих чисел
Додати в блог або на сайт

Цей текст може містити помилки.

Економіко-математичне моделювання | Контрольна робота
76.8кб. | скачати


Схожі роботи:
Транспортна задача
Транспортна задача лінійного програмування
Транспортна логістика та організація транспортних процесів на підприємствах
Ремонт транспортних засобів
Оцінка транспортних засобів
Оподаткування транспортних засобів
Основи експлуатації транспортних засобів
Технічне обслуговування транспортних засобів
Страхування транспортних засобів та вантажів
© Усі права захищені
написати до нас