Знаходження опорного плану транспортної задачі

1. Лінійний метод ОПТИМІЗАЦІЇ, Задача лінійного програмування, ЇЇ

ПОСТАНОВКА І ВЛАСТИВОСТІ

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

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

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

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

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

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

Нелінійне програмування - нелінійних цільова функція й обмеження.
Нелінійне програмування прийнято поділяти наступним чином:

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

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

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

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

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

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

1. Завдання вирішується відносно змінних.

Надалі вони будуть записуватися у вигляді або вектора-стовпця

(X1)

X = (..)

(Xn)

або вектора-рядка х = (х1, ..., хn).

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

a11x1 + .... + a1nxn = 0 (16)

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

(матрична запис) записується у вигляді:

(p, x) (max x (17)

за умов: ax> = bx> = 0 (18) або в запису у вигляді нерівностей:

EpjXj (min x1 .. xn

при обмеженнях:

E aij xj> = bi

... ... ... ... ..

E aij xj> = bm

X1 .... xn> = 0

Таким чином, не важливо, в якій формі виходять лінійні обмеження: у формі рівностей або у формі нерівностей. еквівалентними перетвореннями можливо пустити нерівності до рівності і навпаки.
Необхідність перетворень звичайно пов'язана з тим, який застосовується метод рішення.

1.3 Транспортна задача

Нехай деякий, однорідний товар (продукт) зберігається на складах M і споживається в N пунктах (наприклад, магазинах). Відомі наступні параметри:ai - запас продукту на-му складі, ai> 0, i = 1, ...., m bj-потреба в продукті у-му пункті, bj> 0, j = 1, ...., n
Cij - вартість перевезення одиничного кількості товару з-го складу в
-й пункт,. Планується повністю перевезти товар зі складів і повністю задовольнити потреби в пунктах призначення. При цьому передбачається, що сумарні запаси дорівнюють сумарним потребам:

mn
E ai = E bj (19) i = 1 j = 1

Транспортна задача ставиться як канонічна задача ЛП наступного спеціального виду:mn

EE CijXij (min (20) i = 1 j = 1

за умов:

E xij = ai, i = 1, ..., m (21)

J = 1

E xij = bj, j = 1, ...., n (22)

I = 1

Xij> = 0, i = 1, ... .. mj = 1, .... n (23) де - кількість товару, що перевозиться з I-го складу в J-ий пункт.
Іншими словами, потрібно так організувати перевезення продукту зі складів до пунктів споживання, щоб при повному задоволенні потреб мінімізувати сумарні транспортні витрати. Зауважимо, що умова () є необхідним і достатнім для існування вирішення транспортної задачі.

4. Аналіз завдання або моделі.
4.1 Визначення опорного плану транспортної задачі

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

Метод мінімального елемента

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

Проглядається вся матриця тарифів перевезень, і з неї вибирається позиція з найменшим значенням тарифу C, потім проглядаються значення наявності запасів на складі A і потреби у споживача B, потім в дану клітину записується величина D = MIN (A, B). З запасів відповідного складу і потреб магазину віднімається величина D. Якщо запас товару на складі вичерпано, то цей рядок виключається з подальшого розгляду.
Якщо потреба магазину в товарі задоволена повністю, то цей стовпець виключається з подальшого розгляду. Може бути випадок, коли одночасно виключаються й рядок і стовпець, цей випадок називається виродженим. Надалі весь процес повторюється до тих пір, поки не буде вичерпано весь запас товарів на складах і не буде задоволена потреба всіх магазинів. За отриманою матриці перевезень обчислюється цільова функція задачі Z.

Метод Фогеля

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

Метод подвійного переваги

В початковій своїй стадії цей метод схожий на метод мінімального елементу, але для стовпців. Проглядається перший стовпець матриці тарифів, у ньому знаходиться найменший елемент. Потім перевіряється, мінімальний чи цей елемент у своїй рядку. Якщо елемент мінімальний у своїй рядку, то за методом мінімального елемента в цю клітку заноситься значення D = MIN (A, B),відповідні запас і потреба зменшуються на цю величину.
Обнулитися рядок або стовпець виключаються з розгляду і процесповторюється, починаючи з першого неісключенного стовпця. Якщо знайдениймінімальний елемент не є мінімальним у своєму рядку, то відбувається перехід донаступного колонку і так до тих пір, поки не буде знайдено такий елемент. Заотриманої матриці перевезень обчислюється цільова функція Z. Цей методвимагає інтенсивних операції обміну з пам'яттю, тому громіздкіший попорівнянні з іншими і вимагає великих обчислювальних ресурсів.

Як і будь-яка задача лінійного програмування, необхідно побудувати початковий опорний план для розв'язання задачі. Одним з методів побудови вихідного опорного плану є так званий метод «північно-західного» кута.

Метод північно-західного кута

Метод полягає в наступному. Проглядається матриця тарифів перевезень C,починаючи з лівого верхнього кута (клітини). У цю клітку записується величина
D = MIN (A, B). Вона вираховується із запасів і потреб відповідногоскладу та магазину. Обнулитися рядок або стовпець виключаються зрозгляду, потім процес знову повторюється для лівої верхньої клітиниматриці, що залишилася, і так до тих пір, поки весь запас товарів не будевичерпано. Отриманий опорний план не оптимальний, тому його подальшерішення продовжують одним з вишерассмотренних методів.

2. Предмодельний аналіз.
2.1 Аналіз існуючих аналогів і підсистем

Програмне забезпечення для розв'язання задач лінійного програмування і вЗокрема, транспортної задачі розроблено вже в кінці 60-х - початку 70-хроків і було реалізовано як пакет програм - бібліотек. Даний пакет завданьбув реалізований на таких алгоритмічних мовах як Алгол, Фортран. Узахідних розробках в основному застосовувався алгоритмічну мову Кобол. Зпоявою персональних комп'ютерів даний пакет був переміщений на ПК, зурахуванням особливостей реалізації трансляторів перерахованих вище мов на ПК.
Також додатково були реалізовані пакети програм, в основному зусиллямивузів на мовах Паскаль, Сі. Перенесення програмного забезпечення на ПК відкривнові можливості у вирішенні задач лінійного програмування та наочноговідображення результатів обчисленні, що було відсутнє на великихобчислювальних системах - мейнфреймах.
Хід обчисленні і його результати, особливо для багатовимірних задач з великимчислом змінних можна було наочно відобразити на моніторі. Крім тогопоява інтерактивних програм, програм, в хід яких людина -оператор міг активно втрутитися, коригувати проміжні результати,змінити методику розрахунків, значно полегшує і прискорює розробкунового програмного забезпечення.
З розвитком апаратного забезпечення удосконалювався і програмнезабезпечення. Алгоритмічні мови теж удосконалювалися згіднопотребам економіки, науки і т.д.
Особливо бурхливий розвиток програмного забезпечення почалося з появоюопераційної системи Windows. Майже все існуюче програмнезабезпечення та алгоритмічні мови були перенесені на цю операційнуплатформу. Можливості Windows посилили інтерактивну сторону цихалгоритмічних мов, перейшовши на об'єктно-орієнтований принциппобудови алгоритмів, що дозволяло використовувати вже напрацьованепрограмне забезпечення без великих змін.
Одним з бурхливо розвиваються алгоритмічних мов є Pascal і йогодіалекти. Спочатку ця мова була створений для навчання студентів основампрограмування, зважаючи на свою простоту і наочності конструкції. Він бувстворений Ніклаус Віртом, і послужив основою для цілого сімейства Паскаль -подібних мов - Modula, Classcal, Object Pascal.
Найбільш розвинену систему програмування мовою Pascal побудувала фірма
Borland - Turbo Pascal. Спочатку вона була реалізована для DOS, зпоявою Windows, вона була перенесена до неї. І нарешті, була випущенанова версія для Windows - Delphi.

5.2 середу розробки Delphi

Без баз даних сьогодні неможливо уявити роботу більшостіфінансових, промислових, торговельних та інших організацій. Потоки інформації,циркулюють у світі, який нас оточує, величезні. У часі вони маютьтенденцію до збільшення. Не будь баз даних, ми давно захлинулися б уінформаційної лавини. Бази даних дозволяють структурувати інформацію,зберігати та видавати оптимальним для користувача чином.
Оскільки використання баз даних є одним з наріжних каменів,на яких побудоване існування різних організацій, пильнаувагу розробників додатків баз даних викликають інструменти, задопомоги яких такі програми можна було б створювати. Висунуті до нихвимоги у загальному вигляді можна сформулювати як:
"швидкість, простота, ефективність, надійність".
Серед великої різноманітності продуктів для розробки додатків Delphiзаймає одне з провідних місць. Delphi і віддають перевагу розробники зрізним стажем, звичками, професійними інтересами. За допомогою Delphiнаписано колосальна кількість додатків, десятки фірм і тисячіпрограмістів-одинаків розробляють для Delphi додаткові компоненти.
В основі такої загальновизнаної популярності лежить той факт, що Delphi, якніяка інша система програмування, задовольняє викладеним вищевимогам. Дійсно, додатки за допомогою Delphi розробляютьсяшвидко, причому взаємодія розробника з інтерактивною середовищем Delphi невикликає внутрішнього відторгнення, а навпаки, залишає відчуття комфорту.
Delphi-додатки ефективні, якщо розробник дотримується певніправила (і часто - якщо не дотримується). Ці додатки надійні і приексплуатації мають передбачуваним поведінкою.
Та ось проста чи Delphi? І так, і ні. Вона лише здається простим, якщобагато "підводні камені" приховані від розробника. Однак чим більше вивчаєшїї, тим більше стає зрозумілою її глибина, яка одночасно і викликаєповага, і лякає. Лише з часом приходить розуміння того, що длянаписання дійсно потужних і функціональних додатків потрібнопостійне вивчення Delphi.
-----------------------

лист
Кп-км-п-44-2203-99

Лист
Кп-км-п-44-2203-99