Повна версія

Головна arrow Логістика arrow ЛОГІСТИКА: ТЕОРІЯ І ПРАКТИКА ПРОЕКТУВАННЯ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

МОДЕЛІ ОПТИМІЗАЦІЇ ПОТОКІВ

Канонічна постановка моделі оптимізації потоків.

Завдання відшукання найбільш раціонального способу транспортування деякого продукту досить часто може бути описана наступним чином. Є т пунктів відправлення, в кожному на яких зосереджено певну кількість одиниць однорідного продукту, призначеного до відправки: в першому пункті відправлення є а х одиниць цього продукту, у другому - а 2 одиниць, в i-м - a i одиниць і, нарешті, в т-му пункті - а т одиниць продукту. Цей продукт слід доставити в п пунктів призначення (споживання), причому в перший пункт призначення слід доставити Ь, одиниць продукту, у другій - Ь2 одиниць, в j -й - Ь одиниць і, нарешті, в п-й пункт - Ь п одиниць продукту.

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

Далі передбачається, що кожен пункт відправлення з'єднаний з кожним пунктом призначення деяким маршрутом (число цих маршрутів одно т? П), причому відома вартість перевезення однієї одиниці продукту по цьому маршруту. Загальна вартість перевезення будь-яким маршрутом пропорційна кількості перевезеного продукту. Вартість перевезення одиниці продукту з i-ro пункту відправлення в j-й пункт призначення позначимо числом з ^.

Перераховані дані зручно звести в табл. 4.1, звану таблицею вартостей.

Таблиця 4.1. Таблиця вартостей

ь,

ь,

ь ,

до

° 1

з п

З 12

з «

З 1п

З 21

З 22

З 2)

З 2 "

а.

«і

C i2

з а

З , "

З т

З т2

__

з тп

У цій таблиці рядкам відповідають пункти відправлення, а стовпцями - пункти призначення. У клітці? J, розташованої на перетині? -го рядка і; -го стовпчика, вказана вартість перевезення одиниці продукту за маршрутом, що веде з? -го пункту відправлення в j-й пункт призначення.

Кількість продукту (а ,, а 2 , ..., а ш ), наявне в пунктах відправлення, і кількість продукту 1 , видання 2 , Ь п ), потрібне в пунктах призначення, розміщені відповідно в лівому стовпчику та верхньому рядку таблиці вартостей.

Позначимо кількість одиниць продукту, плановане до перевезення з i-ro пункту відправлення в j-й пункт призначення, через х ^.

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

Будь-який план перевезень визначається завданням сукупності чисел Ху (i = 1, 2, mj = 1, 2, п), тобто перерахуванням величин перевезень, що здійснюються по кожному з маршрутів. Ці числа повинні відповідати таким вимогам.

1. З кожного пункту відправлення повинен вивозитися весь наявний там продукт:

2. У кожному пункті призначення повинна бути задоволена вся потреба в даному продукті:

3. Числа x ^. повинні бути невід'ємними:

Неважко бачити, що, навпаки, будь-яка сукупність чисел Ху, які відповідають умовам (4.1) - (4.3), може розглядатися як певний план перевезень.

Кожен план перевезень може бути наочно зображений у вигляді табл. 4.2.

Таблиця 4.2. план перевезень

ь,

ь 2

b i

Ь "

а 1

* 11

* 12

* 1 /

* ln

* 21

* 22

X 2j

* 2л

а.

* п

* 12

**

*, "

а т

* ml

* т2

_

* Ш Л

Підрахуємо загальну вартість перевезень за планом за даними табл. 4.2. По маршруту, що з'єднує t-й пункт відправлення та j-й пункт призначення, перевозітсях одиниць продукту, а вартість перевезення однієї одиниці продукту дорівнює c (j. Оскільки загальна вартість перевезення по даному маршруту пропорційна кількості одиниць перевезеного продукту, ця вартість дорівнює суху. Грошових одиниць.

Звідси сумарна вартість перевезень по всіх маршрутах

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

Математично транспортна задача лінійного програмування формулюється так: знайти значення невідомих ^ (i = 1, 2, ..., m; j = 1, 2, п), задовольня

ющие умов (4.1) - (4.3) і звертають в мінімум лінійну функцію (4.4).

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

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

У більш загальній постановці цю ж задачу можна сформулювати наступним чином. Нехай стовпці таблиці вартостей означають різні види каналів обслуговування, а рядки - різні класи заявок. Кожне число b j при цьому показує, скільки каналів містить даний вид, а числа a j - скільки є заявок класу i. Числа с., Можуть характеризувати час обслуговування заявки i-ro класу каналом обслуговування j -го виду або будь-які інші витрати, пов'язані з цим обслу-

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

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

Слід зазначити, що історично деякі методи рішення транспортної задачі були розроблені не на базі загальних методів лінійного програмування, а безпосередньо з розгляду властивостей транспортної задачі; зв'язок ж цих методів з загальними була з'ясована пізніше. Саме так виник один з найбільш ефективних методів вирішення транспортної задачі - угорський метод, який є з точки зору класифікації, даної у введенні, типовим представником методів послідовного скорочення нев'язок. Ідея методу була висловлена ще в 1931 р угорським математиком Егерварі. На початку 1950-х рр. американський математик Кун, розвинувши цю ідею, розробив метод вирішення задачі вибору, що є окремим випадком транспортної задачі [14, 15]. Пізніше угорський метод був удосконалений і узагальнено на випадок довільної транспортної задачі Манкресом.

Приклад рішення канонічної транспортної задачі.

Є три постачальники і чотири споживача. Потужності постачальників, попити споживачів, а також витрати на перевезення вантажів зведені в таблицю поставок.

постачальники

споживачі

потужність

постачальників

1

2

3

4

1

4

6

1

2

80

2

7

3

8

5

150

3

2

5

4

7

30

Попит споживачів Ь (

40

60

30

130

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

Рішення

За умовою завдання =? Ь ,. Отже, транспортна

i )

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

Для вирішення завдання необхідно побудувати початкове базисне рішення будь-яким способом, потім спробувати поліпшити отримане рішення. Побудуємо початкове базисне рішення методом найменших витрат, для поліпшення рішення використовуємо метод потенціалів. Число базисних змінних закритою транспортної задачі має дорівнювати (т + п - 1), де п - число постачальників; т - число споживачів. Можливо, що число базисних змінних буде менше, ніж (т + п - 1). Ми отримаємо вироджене рішення. У цьому випадку необхідно використовувати штучний прийом введення в базисне рішення клітин з нульовими постачальниками. У нашій задачі ранг матриці дорівнює 3 + 4 - 1 = 6.

постачальники

споживачі

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

1

2

3

4

1

4

6

1

2

80

30

50

2

7

3

8

5

150

10

60

80

3

2

5

4

7

30

30

Попит споживачів видання (

40

60

30

130

Визначимо потенціали кожного стовпця і кожного рядка, починаючи з нульового значення потенціалу, заданого для першого стовпця, при цьому будемо виходити з умови, що потенціали клітин з базисним рішенням дорівнюють нулю, тобто необхідно дотримуватися умова ц. + V = с ^. Потім обчислимо потенціал кожної клітини, що не увійшла в базисне рішення, за формулою і ( + г - - з = р у , де Ру - потенціал вільної клітини (розташований в правому кутку клітки).

юз

постачальники

споживачі

Потенціали рядків ( «,)

1

2

3

4

1

4

6

1

2

4

0

-6

30

50

2

7

3

8

5

7

10

60

-4

80

3

2

5

4

7

2

30

-7

-5

-7

Потенціали стовпців (V,)

0

-4

-3

-2

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

У нашій задачі потенціали клітин не мають позитивних значень, отже отримано оптимальне рішення. Мінімальні витрати: 10 • 7 + 30 • 2 + 60 • 3 + 30 • 1 + + 50 • 2 + 80 • 5 = 840. Необхідно зауважити, що отримане оптимальне рішення в даній задачі не є єдиним.

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

Насправді ця умова може не виконуватися. Так, наприклад, наявну кількість продукту може перевищувати потреби в ньому, тобто

В цьому випадку система рівнянь (4.1) - (4.2) виявляється несумісною, так як при забезпеченні наявних потреб в продукті частина продукту обов'язково повинна залишитися в деяких з пунктів відправлення. Тому в розглянутій задачі слід рівності (4.1) замінити нерівностями

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

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

Розглянемо як приклад таку задачу. Нехай є п будівельних майданчиків, в кожній з яких заданий обсяг потреб цегли ( b v видання 2 , ..., видання п штук). Для забезпечення цих потреб слід заздалегідь завезти залізницею необхідний цегла на наявні т залізничних станцій, звідки він буде доставлятися на будівельні майданчики автотранспортом, причому питомі вартості перевезення цегли цим транспортом відомі і задані табл. 4.1. На кожній із згаданих залізничних станцій може бути зосереджено обмежена кількість цегли - а ; штук (в силу, скажімо, обмеженості складських примі-

П

ний). Загальна кількість необхідного цегли? менше,

ji

ніж його кількість, яку можна одночасно запасти

т

на всіх станціях, тобто менше, ніж? а, • штук. Виникає питання:

i = i

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

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

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

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

На закінчення покажемо, що відкриту модель транспортної задачі можна звести до звичайної транспортної задачі (замкнутої моделі). З цією метою можна застосувати наступний штучний прийом. Введемо ще один (п + 1) -й пункт споживання (фіктивний), для якого покладемо

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

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

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

Завдання з додатковими обмеженнями з вивезення продукту. Нехай у розглянутій задачі все склади розбиті на групи так, що кожна забезпечується цеглою з певного заводу, і тому загальна кількість цегли, яке може бути приховано на складах цієї групи, обмежена продуктивністюзаводу. Тоді поряд з умовами (4.2), (4.3), (4.5) з'являються додаткові умови:

де до - номер цегельного заводу; г - число заводів; 1 до - безліч номерів складів, постачає fc-м цегляним заводом; S k максимальне кількість цегли, яке може призвести до-й цегельний завод.

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

ielk

не виконується, то для них умови (4.6) виписувати не потрібно, бо вони будуть автоматично виконані, якщо забезпечити виконання умов (4.5).

Назвемо розглянуту задачу мінімізації витрат на перевезення (функції (4.4) при обмеженнях (4.5), (4.6), (4.2), (4.3) транспортної завданням з додатковими обмеженнями з вивезення продукту. Це завдання було проаналізовано в роботі [25].

Завдання з обмеженнями пропускних спроможностей.

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

Тому поряд з викладеної завданням становить інтерес завдання мінімізації лінійної функції (4.4) за умов (4.1) - (4.3) і додаткових умовах:

де d (j - задані невід'ємні числа.

Слід зазначити, що звичайна транспортна задача може розглядатися як окремий випадок транспортної задачі з обмеженими пропускними здатностями, якщо покласти все d { . = Оо.

Ясно, що для того щоб транспортна задача з обмеженими пропускними здатностями мала розв'язок, необхідно, щоб числа d t j були надто малими, а саме, щоб виконувалися наступні нерівності:

Задача про призначення (вибору). Розглянемо один окремий випадок транспортної задачі лінійного програмування, що має велике число додатків.

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

Визначимо матрицю чисел х .. за таким правилом: покладемо х ~ = 1, якщо число c t - вибрано, і х у . = 0, якщо число не вибрано. Тепер будь-який план завдання призначення однозначно визначає деяку матрицю || х у ||.

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

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

Сумарну ефективність даного плану розподілу можна записати в наступному вигляді:

Тепер завдання можна математично сформулювати так: знайти матрицю чисел х ( ., Які відповідають умовам (4.7) і звертають в максимум лінійну функцію (1.8).

Якщо замість функції (1.8) розглянути протилежну функцію

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

Особливість такого завдання в тому, що а. = B. = 1. Це дозволяє спростити деякі алгоритми її вирішення для розглянутого окремого випадку.

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

На закінчення слід зазначити, що так само, як і загальна транспортна задача, задача призначення може розглядатися при відсутності рівності між кількістю розподіляються коштів і кількістю об'єктів, на які ці кошти слід направити (між числом робочих і числом робіт). У цьому окремому випадку відкритої моделі транспортної задачі одна з двох груп рівності (4.7) повинна бути замінена відповідними нерівностями. Так, якщо т> п, то обмеження, що накладаються на невідомі, повинні мати вигляд

Завдання про максимальний потік (в матричної постановці). Дуже близька до транспортної наступна більш просте завдання. Нехай, як і раніше, задані кількість продукту а р а 2 , ..., а т , призначені до відправки з пунктів відправлення, і потреби Ь р Ь 2 , ..., видання п в цьому продукті в пунктах призначення. Однак кожен пункт відправлення пов'язаний лише з деякими пунктами призначення, тобто з будь-якого пункту відправлення в деякі пункти призначення можна здійснювати перевезення, а в деякі - не можна.

Математично ці умови можна задати числами а заповнюють матрицю | | сг. 11. Ці числа формуються за таким правилом: число а "= 1, якщо не можна здійснювати перевезення з i-ro пункту відправлення bj'-й пункт призначення, і число а .. = 0, якщо таке перевезення можлива. Природніше було б позначати відсутність маршруту нулем, а наявність - одиницею, проте запроваджене протилежне правило виявляється більш зручним в подальшому, при побудові алгоритму рішення транспортної задачі.

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

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

т

збігається із загальною кількістю? а, продукту, наявного

i = 1

mn

в пунктах відправлення (для випадку X а ; - X Ь /) або з сумарною

п i = i; = i

потребою в продукті X в пунктах призначення (для слу-

т п; = 1

чаю X a i - XV- Така ж кількість продукту можна пере-

1 = 1 .1 = 1

везти, якщо нулів в матриці 11 а ^. 11 досить багато. При подальшому зменшенні кількості нулів в матриці 11 | максі

мально досяжне кількість перевезень зменшується.

Той чи інший план перевезень може бути визначений завданням чисел х ~ (i = 1, ..., т; j = 1, ..., п), що вказують, скільки слід перевозити продукту з i-ro пункту відправлення в j -й пункт призначення. Числа х ; повинні задовольняти ряду вимог, які можуть бути сформульовані наступним чином.

1. Всі числа х у . повинні бути невід'ємними:

2. Якщо а ^ 0, то

Ця умова означає, що перевезення з i-ro в j-й пункт не проводиться, якщо ці пункти не пов'язані між собою.

3. З кожного (i-ro) пункту відправлення не можна вивезти продукту більше, ніж його є:

4. У кожен (j-й) пункт призначення не можна ввезти кількість продукту, що перевищує потребу в ньому:

Всякі m • п чисел x i} , що задовольняють умовам (4.9) - (4.12), визначають деякий план перевезень. При цьому загальна кількість перевезеного продукту Ф визначається наступною формулою:

У відповідності зі сказаним потрібно знайти такі т? п чисел x ijt які відповідають умовам (4.9) - (4.12), які звертають функцію Ф в максимум.

Зауважимо, що фактичне число невідомих в задачі не т? п, а менше, так як умова (4.10) визначає ряд невідомих, тобто число невідомих дорівнює т • п мінус кількість чисел а не дорівнює нулю.

Так само як і в транспортній задачі, тут можна ввести обмеження пропускної здатності кожного маршруту, наклавши додаткові обмеження на невідомі х ~: < d j} ,

де - максимальна кількість продукту, яке можна везти з пункту i в пункт ;.

У цьому випадку матрицю Ца ^ .Ц можна не ставити, а прийняти всі пропускні спроможності cL, відповідні забороненим маршрутами (тобто маршрутами, для яких а .. = 1), рівними нулю.

Це завдання, так само як і транспортна, може бути сформульована в термінах заявок і каналів обслуговування. Нехай, як і в транспортній задачі, індекс i відповідає різним класам заявок, а індекс) - різним видам наявних каналів обслуговування. Рівність = 1 означає неможливість обслуговування заявки (-го класу каналом обслуговування j- го виду. Потрібно так розподілити заявки між каналами обслуговування, щоб потік заявок, обслужених без затримки, був максимальний, тобто щоб створилася чергу необслужен- них заявок була мінімальна .

У задачі про максимальний потік іноді, так само як і в транспортній задачі, слід враховувати додаткові обмеження з вивезення продукту, про які говорилося вище. У цьому випадку поряд з умовами (4.9) - (4.12) невідомі повинні задовольняти умовам (4.6).

Розподільна завдання. Багато задач лінійного програмування, що зустрічаються при вирішенні питань планування, можуть бути зведені до задачі, одна з численних економічних інтерпретацій якої така. Є т видів сировини в кількостях а р а 2 , а т одиниць. Існують п пунктів виробництва, у яких будь-який вид цієї сировини може перероблятися в готовий продукт, причому на виготовлення одиниці готового продукту в j -му пункті виробництва йде ау одиниць сировини i-ro виду. Задані кількості Ь р Ь 2 , ..., Ь п одиниць продукту, які повинні бути виготовлені на кожному з пунктів виробництва. Нехай - кількість продукту, що виготовляється в j-му пункті виробництва із сировини г-го виду, а с- - вартість виготовлення одиниці продукту цим способом.

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

Вимоги відсутності перевитрати кожного виду сировини можуть бути записані у вигляді нерівностей

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

а все невідомі повинні бути невід'ємними:

Вартість виробництва, яка визначається планом | х ^ , виражається формулою

Таким чином, приходимо до наступної математичної формулюванні завдання: знайти мінімум лінійної функції (4.16) при обмеженнях (4.13) - (4.15), що накладаються на невідомі.

з

Це завдання має назву розподільної. Часто її називають також ^ -завдання (лямбда-завданням) або узагальненої транспортної завданням. Остання назва відображає те, що в окремому випадку, коли всі а у = 1, розподільна завдання зводиться до транспортної. У термінах перевезень розподільну завдання можна сформулювати інакше. Числа a v а 2 , а т означають запаси палива, сконцентровані в т пунктах відправлення, причому в різних пунктах різне паливо. Все це паливо або частина його потрібно доставити до споживачів, причому для кожного споживача вказано кількість тепла b j (число калорій), який повинен бути одержаний в результаті спалювання завезеного палива.

Числа <т. означають теплотворну здатність палива з i-ro пункту відправлення, яка передбачається залежить не тільки від джерела постачання, а й від того, який споживач це паливо спалює. Витрати на транспортування однієї вагової одиниці палива з i-ro пункту відправлення до) -го споживача позначимо через і будемо вважати також відомими. Будь-яка сукупність чисел х, що означають величини перевезень, що здійснюються з пунктів відправлення до споживачів, є планом задачі, якщо вона задовольняє вимогам по забезпеченню калоріями кожного споживача, тобто

і якщо вона не передбачає перевищення запасів палива, наявних в пунктах відправлення:

При цьому слід вважати перевезення невід'ємними:

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

Отже, потрібно знайти мінімум лінійної функції (4.20) при умовах (4.17) - (4.19). Ця постановка дещо відмінна від раніше наведеної. Однак якщо ввести заміну змінних = а у х у й позначити 1 / а у = а ', з у / а у = з', то задача зведеться до відшукання мінімуму лінійної функції

за умов

що з точністю до позначень збігається з раніше сформульованої розподільної завданням.

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

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

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

У відповідності зі сказаним введемо поняття транспортної мережі. Під транспортною мережею будемо розуміти сукупність пунктів (Р р Р 2 , ..., P N ), деякі з яких з'єднані направленими відрізками (комунікаціями) До Якщо існує комунікація До ( ., Що йде від пункту Р ( до пункту Я, то це означає , що з пункту Р { в пункт Я можуть здійснюватися перевезення продукту. Підкреслимо, що наявність комунікації означає можливість тільки одностороннього руху.

У тих випадках, коли в дійсності допустимі перевезення в обох напрямках між пунктами Р. і Р ; , Ці два пункти повинні бути з'єднані парою комунікацій протилежного напрямку (С. = Р у ).

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

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

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

Пункти Р, Р 3 - пункти виробництва з обсягами виробництва відповідно 30, 70, 50 одиниць; пункти Р 57 - пункти споживання з обсягами споживання, що дорівнюють відповідно 60, 40, 50 одиниць; пункти Р 4 , P g10 - перевалочні пункти (відсутність у відповідних колах, обсягів виробництва означає, що вони дорівнюють нулю).

Спрямовані відрізки, що з'єднують деякі пункти, зображують комунікації. Так, з пункту Р j в пункт Р 8 продукт може перевозитися по комунікації До г 8. У той же час з пункту Р 8 до пункту Р ] або в пункт Р 5 безпосередньо, минаючи проміжні пункти, продукт перевозитися не може, бо комунікації До 8 , ІК 8 відсутні. У той же час між пунктами Р 4 і Р д перевезення можуть здійснюватися безпосередньо в обидві сторони, бо ці пункти з'єднані парою комунікацій До 4 9 і К 9 4. Пропускні здатності комунікацій представлені знаменниками дробів, які перебувають при кожній комунікації, а вартості перевезень - числителями цих дробів.

р 6

Приклад транспортної мережі

Мал. 4.7. Приклад транспортної мережі

Якщо задана транспортна мережа, то виникає задача організації перевезень з комунікацій цієї мережі. Число одиниць продукту, що перевозиться по комунікації До { . з пункту Р в пункт Pj, позначимо через х ^, оскільки ми домовилися розглядати лише комунікації з одностороннім рухом, Ху > 0. Облік пропускної здатності призводить до додаткової вимоги х. <D ... Сукупність чисел {х ^.}, Що задовольняють умовам

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

Кількість одиниць продукту, що вивозиться з довільного пункту відповідно до системи перевезень {х ^}, так само X x ij> де E'i - безліч номерів тих пунктів, в які

з пункту Р ; йдуть комунікації. Точно так же кількість одиниць продукту, що ввозиться в пункт Р., визначається виразом X x ij> де Е " - безліч номерів пунктів, з яких

j'eE / '

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

Для того щоб система перевезень {х ^} узгоджувалася з обсягами виробництва і споживання, необхідно, щоб ця різниця для кожного пункту дорівнювала обсягом виробництва в цьому пункті.

Звідси приходимо до наступного визначення плану транспортної задачі на мережі: планом називається будь-яка сукупність чисел {х ~}, що задовольняє умовам

0 <х. <^;

вивезення> ввезення, то пункт виробництва; вивезення <ввезення, то пункт споживання; вивезення = ввезення, то транзит.

Легко підрахувати загальну вартість перевезень, визначених планом {Ху}:

де підсумовування ведеться по всіх комунікацій транспортної мережі.

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

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

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

Розглянемо транспортну мережу, що має один пункт виробництва Р р один пункт споживання P N і N- 2 перевалочних пунктів. Назвемо потоком з пункту Р у в пункт P N систему перевезень, що задовольняє наступним умовам:

Величину р назвемо величиною потоку. Ця величина показує, скільки продукту вивозиться з пункту P v званого джерелом. Оскільки для всіх перевалочних пунктів існує баланс між кількістю ввезеного і кількістю вивозиться продукту (4.25), то ясно, що весь продукт, що вивозиться з пункту Р р повинен прибути в пункт P N , що легко показати і аналітично. Для цього позначимо кількість продукту, що вивозиться з пункту P N , через p N . Воно визначається співвідношенням

Складемо останню рівність з усіма равенствами (4.25) і (4.26). Неважко бачити, що ліва частина отриманого рівності звертається в нуль, так як для будь-якого числа стоїть зі знаком «плюс», знайдеться це ж число, яке стоїть зі знаком «мінус». Дійсно, будь-яка комунікація fC. виходить рівно з одного пункту Р ( і входить рівно в один пункт Ру Тому одне з рівності (4.25) або (4.26), відповідне пункту Ру містить в лівій частині доданок а інше, відповідне пункту Ру - від'ємник х у . Таким чином, приходимо до співвідношенню

Отже, з пункту P N вивозиться негативне кількість одиниць продукту (-р), а це і означає, що в нього ввозиться р одиниць, що і стверджувалося.

Пункт P N носить назву «стік».

Завданням про максимальний потік називається задача відшукання потоку найбільшої величини з пункту Р г в пункт P N або, що те ж саме, завдання знаходження максимуму лінійної функції (4.26) при лінійних обмеженнях (4.25) і (4.24).

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

Завдання про максимальний потік має сенс розглядати тільки в тому випадку, якщо існує хоча б один спрямований маршрут з пункту Р г в пункт P N , бо в іншому випадку не може існувати потоку, відмінного від нуля.

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

Завдання про максимальний потік легко узагальнюється на випадок, коли на транспортній мережі задається кілька пунктів P v Р 2 , ..., Р до , з яких треба перевезти якомога більше продукту в декілька інших пунктів Q p Q 2 , ..., Q ( .

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

Тут I - безліч номерів всіх пунктів транспортної мережі, за винятком пунктів P v Р 2 , Р до , Q v Q 2 , ..., Q ; . Величиною потоку р, яка максимізує, називається сумарна кількість продукту, що вивозиться з пунктів Р р Р 2 , Р до .

Метод рішення задачі про максимальний потік розроблений американськими математиками Фордом і Фулкерсоном [11, 36, 38, 39].

 
<<   ЗМІСТ   >>