Повна версія

Головна arrow Логістика arrow Проектування логістичних систем

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


<<   ЗМІСТ   >>

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

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

(4.6)

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

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

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

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

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

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

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

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

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

(4.6а)

(4.6б)

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

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

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

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

(4.7)

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

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

(4.8)

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

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

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

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

Зауважимо, що в задачі призначення числа повинні задовольняти ще додатковій умові: кожне з них має

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

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

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

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

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

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

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

  • 1. Всі числа повинні бути невід'ємними:
    • (4.9)
  • 2. Якщо , то

(4.10)

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

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

(4.11)

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

(4.12)

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

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

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

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

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

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

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

 
<<   ЗМІСТ   >>