Теоретичне завдання на тему: «Схема перевірки оптимального розв’язку транспортної задачі»

 

 

 

ЗМІСТ

 

 

ВСТУП

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

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

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

Завдання курсової роботи:

- ознайомитись і набути  практичних навичок використання  математичних моделей;

- оволодіти теоретичними знаннями та практичним застосуванням транспортних задач;

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

- ознайомитись та оволодіти  матеріалом на тему «Схема перевірки оптимального розв’язку транспортної задачі»

 

 

 

Розділ 1.  Побудова та опис математичної оптимізаційної моделі

Постановка задачі: Для пошиття одного виробу потрібно викроїти з тканини 6 деталей. На швейній фабриці були розроблено два варіанти розкрою тканини. В табл. 1 наведені характеристики варіантів розкрою 10 м2 тканини та комплектність, тобто кількість деталей визначеного виду, які необхідні для пошиву одного виробу. Щомісячний запас тканини для пошиву виробів даного типу складає 405 м2. У найближчий місяць планується пошити 90 виробів. Побудувати математичну модель, що дозволяє в найближчий місяць виконати план по пошиву з мінімальною кількістю відходів.

Таблиця 1. – Характеристика варіантів розкрою відрізів тканини по 10 м2

Варіант розкрою	Кількість деталей, шт../відріз						Відходи, кв.м/відріз
	1	2	3	4	5	6
1	60	0	90	40	70	90	0,5
2	80	35	20	78	15	0	0,35
Комплектність, шт../виріб	1	2	2	2	2	2

 

Розв’язання

змінні завдання

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

x1 - кількість відрізів тканини по 10 м2, розкроєних першим способом протягом місяця , [ відріз . / міс. ];

x2 - кількість відрізів тканини по 10 м2, розкроєних другим способомпротягом місяця, [ відріз . / міс. ].

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

Метою рішення задачі є виконання плану при мінімальній кількості відходів. Оскільки кількість виробів строго заплановано ( 90шт. / міс.), то цей параметр не описує ЦФ, а відноситься до обмеження, невиконання якого означає, що завдання не розв`язана. А критерієм ефективності виконання плану служить параметр "кількість відходів", який необхідно звести до мінімуму. Оскільки при розкрої одного відрізу( 10 м2) тканини по 1-му варіанту виходить 0,5 м2 відходів, а по 2-муваріанту - 0,35 м2 (див. табл. 1), то загальна кількість відходів при крої (ЦФ )має вигляд:

L(X )= 0,5x1 + 0,35x2 → min ,

Обмеження

Кількість розкроїв тканини різними способами обмежується наступними умовами:

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

 • витрати тканини  не повинні перевищувати її місячного запасу  на складі;

• кількість відрізів розкроєної тканини не може бути негативною.

Математично обмеження за планом пошиття пальто записуються у вигляді:

60x1+80x2 ≥90;

          35x2 ≥80;

90x1+20x2 ≥180;

40x1+78x2 ≥180;

70x1+15x2 ≥180;

90x1              ≥180;

 ≥ 

Обмеження по витраті тканини має таку математичну форму запису:

x1 + x2 ≤

,

 ≤ 

Таким чином, математична модель задачі має вигляд:

L(X )= 0,5x1 + 0,35x2 → min [

відх./міс.],

 

Розділ 2. Транспортна задача

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

 

	В1	В2	В3	В4	Запаси
А1	1	5	7	1	30
А2	1	4	2	5	60
А3	2	3	5	2	60
Потреби	30	20	60	40

 

Розв’язання

Виконуємо перевірку умову .

Отже, задача є закритою.

В Microsoft Excel створюємо таблицю, у яку заносимо початкові дані (рис. 2.1).

Рисунок 2.1 – Початкові дані

Методом північно-західного кута розраховується початковий план перевезень (рис. 2.2). Для швидкості та зручності розрахунків у клітинки потреб (C21, ) та запасів (O12,) записуємо формули

=$D$5-D13-D16-D19;

=$H$2-D13-G13-J13-M13.

Дані формули копіюються в усі аналогічні клітинки. Це дозволить за даним методом у таблиці заповнити базисні клітинки відповідними величинами . Таких клітинок 6. Згідно отриманого початкового плану мінімальна вартість перевезень становитиме 370 у.о. Для розрахунку цієї величини у клітинку O21 записуємо формулу:

=D13*E12+G13*H12+J13*K12+M13*N12+D16*E15+G16*H15+J16*K15+M16*N15+D19*E18+G19*H18+J19*K18+M19*N18.

’

Рисунок 2.2 – Перший опорний план

Перевіряємо отриманий план на оптимальність. Розраховуємо значення потенціалів, записавши 0 у клітинку D8 (рис. 2.3).

Рисунок 2.3 – Перша ітерація методу

Інші потенціали розраховуємо на основі базисних клітинок. Маємо наступні результати:

Не базисні (вільні клітинки) для зручності роботи можна зафарбувати у той чи інший колір.

Для усіх клітинок  отриманої таблиці розраховуємо непрямий тариф перевезення за формулою . Формула в Excel має наступний вигляд: =$D8-А12.

Оцінки розраховуємо за формулою:  .

У клітинку Е14 записуємо формулу =$D8-А12 (для зручності роботи аналогічні розрахунки проводимо в усіх інших порожніх та непорожніх клітинках).

Із небазисних клітинок вибираємо ту, у якій додатня  оцінка є максимальною. Це клітинка, яка знаходиться на перетині рядка A3 та стовпчика B2, у якій

Будуємо цикл для цієї клітинки (рис. 2.3), Для клітинок з «+» додали знайдену величину до , а для клітинок з «–»  – відняли. Отримуємо новий план перевезень (рис. 2.4). При цьому вартість мінімальних перевезень становитиме 290 у.о.

Рисунок 2.4 – Друга ітерація методу

Перевіряємо отриманий план на оптимальність. Розрахунки показали, що отриманий опорний план третьої ітерації не оптимальний.

Рисунок 2.5 – Третя ітерація методу

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

Рисунок 2.6 – Четверта ітерація методу

 

Отже, отриманий план є оптимальним. Мінімальна вартість перевезень при цьому становить 290 у.о. Маємо такий оптимальний розв’язок:

,

 

 

 

Розділ 3. Теорія ігор

Постановка задачі: Знайти стратегію гравців А і В та ціну гри, що задана матрицею (за допомогою формул та графічно).

Матриця стратегій гравців А і В

3	5	2	0
6	-1	3	5

Розв’язання

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

На площині xОy введемо систему координат і на осі Ох відкладемо відрізок одиничної довжини А1, А2, кожній точці якого поставимо у відповідність деяку змішану стратегію 1-го гравця ( ). Зокрема, точці А1 (0; 0) відповідає стратегія А1, точці А2 (1, 0) - стратегія А2.

Через точку А1 і А2 проведемо перпендикуляр і на отриманих прямих будемо відкладати виграш гравців. На першому перпендикулярі (в даному випадку він збігається з віссю Оу) відкладемо виграш 1-го гравця при стратегії А1, а на другому - при стратегії А2. Якщо гравець 1 застосує стратегію А1, то виграш при стратегії В1 гравця 2 – 2 , при стратегії В2 – 5, при стратегії В3 – 3, а при стратегії В4 - 0. Числам 2, 5, 3, 0 на осі 0х відповідають точки В1, В2, В3 і В4.

Якщо ж гравець 1 застосує стратегію А2, то його виграш при стратегії В1 дорівнює 6, при В2 – (-1), при В3 – 3 і при В4 – 5. Ці числа визначають точки В1', В2', В3', В4' на перпендикулярі , проведеному через точку А2. З’єднавши між собою точки В1 і В1', В2 і В2', В3 і В3', В4 і В4' отримаємо чотири прямі, відстань до яких від осі 0х визначає середній виграш при будь-якому поєднанні відповідних стратегій.

Таким чином, ординати точок, що належать ламаній В4KВ2' визначають мінімальний виграш 1-го гравця при застосуванні ним будь-яких змішаних стратегій. Ця мінімальна величина є максимальною в точці K, отже, цій точці відповідає оптимальна стратегія p* = ( ), а її ордината дорівнює ціні гри ν. Координати точки K знаходимо як точку перетину прямих В4 В4' і В2В2'.

Звідси, виключаючи стратегії В3 і В4, отримуємо матричну гру 2x2 з платіжною матрицею виду

Матриця гри

5	0
-1	5

 

 

 

 

 

 

 

 

Рисунок 3.1 - Геометрична інтерпретація матрічної гри

Розв’яжемо дану гру аналітичним методом.

Середній виграш першого гравця, якщо він використовує оптимальну мішану стратегію, p* = ( ), а другий гравець – чисту стратегію, що відповідає першому стовпцю платіжної матриці, дорівнює ціні гри ν:

.

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

.

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

Розв’язуємо дану систему рівнянь:

Тоді

Отже,

 

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

Розв’язуємо дану систему рівнянь:

 

Тоді

Отже,

Гра розв’язана. Оптимальні мішані стратегії ціна гри .

 

 

 

 

 

 

 

 

 

Розділ 4. Теоретичне завдання на тему: «Схема перевірки оптимального розв’язку транспортної задачі»

4.1. Постановка транспортної задачі

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

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

       (4.1)

за обмежень

  ;                                 (4.2) 
;                                    (4.3) 
,                           (4.4)

де хij — кількість продукції, що перевозиться від і-го постачальника до j-го споживача; сij — вартість перевезення одиниці продукції від і-го постачальника до j-го споживача; аi — запаси продукції і-го постачальника; bj — попит на продукцію j-го спо¬живача.

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

,                                          (4.5)

то таку транспорту задачу називають збалансованою, або закритою. Якщо ж така умова не виконується, то транспортну задачу називають незбалансованою, або відкритою. Планом транспортної задачі називають будь-який невід’єм¬ний розв’язок системи обмежень (4.2)—(4.4) транспортної задачі, який позначають матрицею     .

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

 Теорема (умова існування розв’язку транспортної задачі). Необхідною і достатньою умовою існування розв’язку транспортної задачі є її збалансованість, тобто  .

 

4.2. Метод потенціалів

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

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

1. Визначення типу транспортної задачі (відкрита чи закрита).
2. Побудова першого опорного плану транспортної задачі.
3. Перевірка плану транспортної задачі на оптимальність.
4. Якщо умова оптимальності виконується, то маємо оптимальний розв’язок транспортної задачі. Якщо ж умова оптимальності не виконується, необхідно перейти до наступного опорного плану.
5. Новий план знову перевіряють на оптимальність, тобто повторюють дії

п. 3, і т. д.

Розглянемо докладно кожний етап цього алгоритму.

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

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

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

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

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

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

Після побудови першого опорного плану одним із розглянутих методів у таблиці має бути заповнено (m + n – 1) клітинок, де m — кількість постачальників; n — кількість споживачів у задачі, у тому числі фіктивних. Такий план називають невиродженим. Якщо кількість заповнених клітинок перевищує (n + m – 1), то початковий план побудовано неправильно і він є неопорним. Ознакою опорності плану транспортної задачі є його ациклічність, тобто неможливість побудови циклу. Циклом у транспортній задачі називають замкнену ламану лінію, вершини якої розміщуються в заповнених клітинках таблиці, а сторони проходять уздовж рядків і стовпчиків таблиці.

Якщо заповнених клітинок у таблиці менш як (m + n – 1), то опорний план називають виродженим. У такому разі необхідно заповнити відповідну кількість порожніх клітинок, записуючи в них «нульове перевезення», але так, щоб при цьому не порушилася ациклічність плану.

3. Опорний план перевіряють на оптимальність за допомогою потенціалів ui та vj відповідно постачальників та споживачів.

 Теорема (умова оптимальності опорного плану транспортної задачі). Якщо для деякого опорного плану Х* = (xij*) існують числа ui та vj, для яких виконується умова:

ui + vj = cij,    xij > 0,

ui + vj = cij,    xij = 0

для всіх   та  , то він є оптимальним планом транспортної задачі.

Потенціали опорного плану визначаються із системи рівнянь ui + vj = cij, які записують для всіх заповнених клітинок транспортної таблиці.

4. За допомогою розрахованих потенціалів перевіряють умову оптимальності ui + vj = cij для порожніх клітинок таблиці. Якщо хоча б для однієї клітинки ця умова не виконується, тобто ui + vj> cij, то поточний план є неоптимальним і від нього необхідно перейти до нового опорного плану.

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

1. кожній вершині циклу приписують певний знак, причому вільній клітинці — знак «+», а всім іншим по черзі — знаки «–» та «+»;
2. у порожню клітинку переносять менше з чисел xij, що стоять у клітинках зі знаком «–». Одночасно це число додають до відповідних чисел, які розміщуються в клітинках зі знаком «+».

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

3. Новий опорний план перевіряють на оптимальність згідно з п. 3 розглянутого алгоритму.

Розглянемо застосування методу потенціалів для розв’язування транспортної задачі, наведеної далі.

4.3. Приклад розв’язання транспортної задачі методом потенціалів

Компанія контролює три фабрики А1, А2, А3, здатні виготовляти відповідно 150, 60 та 80 тис. од. продукції щотижня. Вона уклала договір із чотирма замовниками В1, В2, В3, В4, яким потрібно щотижня доставляти відповідно 110, 40, 60 та 80 тис. од. продукції. Вартість транспортування 1000 од. продукції замовникам з кожної фабрики наведена в табл. 4.10.

Фабрика	Вартість транспортування 1000 од. продукції замовнику
	В1	В2	В3	В4
А1	4	4	2	5
А2	5	3	1	2
А3	2	1	4	2

Таблиця 4.10 «Вартість транспортування продукції»

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

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

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

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

Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування 1000од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:

min Z = 4x11 + 4x12 + 2x13 + 5x14 + 5x21 + 3x22 + x23 +  2x24 +  2x31 + + x32 +4x33 +2x34.

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

min Z = 4x11 + 4x12 + 2x13 + 5x14 + 5x21 + 3x22 + x23 + 2x24 + 2x31 + x32 + + 4x33 +2x34

за умов:

Розв’язання. Запишемо умови задачі у вигляді транспортної таблиці (табл. 4.11) та складемо її перший опорний план у цій таблиці методом мінімальної вартості.

Таблиця 4.11

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

Z1 = 4*110 + 5*40 + 1*60 + 1*40 + 2*40 = 820 (ум. од.).

Перший опорний план транспортної задачі вироджений, оскільки кількість заповнених клітинок у таблиці дорівнює п’яти, а = (m + n – 1) = 3 + 4 – 1 = 6.

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

На основі першої умови оптимальності ui + vj = cij складемо систему рівнянь (для заповнених клітин таблиці) для визначення потенціалів першого опорного плану:

Записана система рівнянь є невизначеною, і один з її розв’язків дістанемо, узявши, наприклад, v4 = 0. Тоді всі інші потенціали однозначно визначаються з цієї системи рівнянь: u1 = 5, u2 = 2, u3 = 2, v1 = – 1,v2 = – 1, v3 = – 1. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.

Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij (для порожніх клітинок таблиці):

А1B2 : u1 + v2 = 5 + (–1) = 4 = 4;

А1B3 : u1 + v3 = 5 + (–1) = 4 > 2;

А2B1 : u2 + v1 = 2 + (–1) = 1 < 5;

А2B2 : u2 + v2 = 2 + (–1) = 1 < 3;

А3B1 : u3 + v1 = 2 + (–1) = 1 < 2;

А3B3 : u3 + v3 = 2 + (–1) = 1 < 4.

Умова оптимальності не виконується для клітинки А1B3. Порушення D13 = (u1 + v3) – c13 = 4 – 2 = 2 записуємо в лівому нижньому кутку відповідної клітинки.

Отже, перший опорний план транспортної задачі неоптимальний. Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Потрібно заповнити клітинку А1B3, в якій є єдине порушення умови оптимальності. Ставимо в ній знак «+». Для визначення клітинки, що звільняється, будуємо цикл, починаючи з клітинки А1B3, та позначаємо вершини циклу почергово знаками «–» і «+». Тепер необхідно перемістити продукцію в межах побудованого циклу. Для цього у порожню клітинку А1B3 переносимо менше з чисел хij, які розміщені в клітинках зі знаком «–». Одночасно це саме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».

У даному разі  , тобто  . Виконавши перерозподіл перевезень продукції згідно із записаними правилами, дістанемо такі нові значення: для клітинки А1B3 — 40 од. продукції, а для А2B3 – (60 – 40) = 20 од., а для А2B4 – (0 + 40) = 40 од. Клітинка А1B4 звільняється і в новій таблиці буде порожньою. Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).