Контрольная работа: Вирішення транспортної задачі з використанням електроних таблиц Micrsoft Excel

.

Аналогічно обмеження виду

зводиться до рівності, віднімаючи від лівої частини додаткову змінну :

,

Така заміна нерівностей рівняннями за допомогою введення додаткових змінних не змінить розв’язку початкової задачі.

Задачі лінійного програмування можна розв’язувати графічно і аналітично.

Симплексний метод розв'язування задач лінійного програмування

Графічний метод для визначення оптимального плану задач лінійного програмування доцільно застосовувати лише для задач із двома змінними. За більшої кількості змінних необхідно застосовувати інший метод. З властивостей розв'язків задачі лінійного програмування відомо: оптимальний розв'язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв'язків. Тому найпростіший спосіб відшукання оптимального плану потребує перебору всіх кутових точок (допустимих планів задачі, які ще називають опорними). Порівняння вершин багатогранника можна здійснювати тільки після відшукання якоїсь однієї з них, тобто знайшовши початковий опорний план. Кожний опорний план визначається системою m лінійно незалежних векторів, які містяться в системі обмежень задачі з n векторів  . Отже, загальна кількість опорних планів визначається кількістю комбінацій . Задачі, що описують реальні економічні процеси, мають велику розмірність, і простий перебір всіх опорних планів таких задач є дуже складним, навіть за умови застосування сучасних ЕОМ. Тому необхідне використання методу, який уможливлював би скорочення кількості обчислень. 1949 року такий метод був запропонований американським вченим Дж.Данцігом - так званий симплексний метод, або симплекс-метод.

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

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

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

Правило побудови двоїстої задачі

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

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

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

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

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

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

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

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

Пари задач лінійного програмування симетричні та несиметричні.

У симетричних задачах обмеження прямої та двоїстої задач є лише нерівностями, а змінні обох задач можуть набувати лише невід’ємних значень.

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

Транспортна задача лінійного програмування

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

Економічна і математична постановки транспортної задачі

Класична транспортна задача лінійного програмування формулюється так: деякий однорідний продукт, що знаходиться у m постачальників А в обсягах ,,…, одиниць відповідно необхідно перевезти n споживачам  в обсягах ,,…, одиниць. При цьому виконується умова, що загальний наявний обсяг продукції у постачальників дорівнює загальному попиту всіх споживачів. Відомі вартості  перевезень одиниці продукції від кожного -го постачальника до кожного -го споживача, що подані як елементи матриці виду: = .

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

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

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

Таблиця 7.1.

Мають виконуватися такі умови:

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

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

) сумарна вартість всіх перевезень повинна бути мінімальною:

Очевидно, що .

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

 (7.1)

за обмежень:

; (7.2)

; (7.3)

 ( ; ). (7.4)

У розглянутій задачі має виконуватися умова:

. (7.5)

Транспортну задачу називають збалансованою, або закритою, якщо виконується умова (7.5). Якщо ж така умова не виконується, то транспортну задачу називають незбалансованою, або відкритою.

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

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

Теорема (умова існування розв'язку транспортної задачі): необхідною і достатньою умовою існування розв'язку транспортної задачі(7.1)-(7.4) є її збалансованість: .

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

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

Як згадувалося вище, транспортна задача (7.1)-(7.4) є звичайною задачею лінійного програмування і може бути розв'язана симплексним методом, однак особливості побудови математичної моделі транспортної задачі дають змогу розв'язати її простіше. Легко помітити, що всі коефіцієнти при змінних у рівняннях (7.2), (7.3) дорівнюють одиниці, а сама система обмежень (7.2), (7..3) задана в канонічній формі. Крім того, система обмежень (7.2), (7.3) складається з mn невідомих та m+n рівнянь, які пов'язані між собою співвідношенням (7.8). Якщо додати відповідно праві та ліві частини систем рівнянь (7.2) та (7.3), то отримаємо два однакових рівняння:

;

.

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

Методи побудови опорного плану транспортної задачі

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

Існують такі методи:

·        північно-західного кута,

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