• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Розв’язування транспортної задачі

Розв’язування транспортної задачі відбувається за допомогою так званої транспортної таблиці, загальний вигляд якої подано у табл. 8.1. У клітинках з індексами i, j таблиці записано величини (у верхньому правому куті); у процесі розв’язування в деяких клітинах з’являться ненульові , а також додаткова інформація.

Таблиця 1.1

Пункти відправлень	Пункти призначення	Запаси
		...		…
			...		…
			…		…
…	…	…	…	...	…	...	...
			…	,	…
…	...	…	…	…	…	...	…
			…		…
Заявки			…		…

Рядки таблиці відповідають умовам (1.3), стовпчики – умовам (8.2).

Розв’язування ТЗ пояснимо на прикладі конкретної задачі, наведеної в табл. 1.2. Тут , .

Приклад 1.1.Розв’язати ТЗ, умова якої задана в таблиці 1.2.

Таблиця 1.2

Пункти відправлень	Пункти призначення	Запаси
Заявки

Розв’язування ТЗ містить два етапи:

- побудова опорного плану;

- побудова оптимального плану.

1.3. Побудова опорного (базисного) плану.

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

Розглянемо заявку з індексом , що становить 10 одиниць, і запас з індексом , що становить 25 од. Візьмемо меншу з цих величин і покладемо . Заявка задоволена, залишається запас у 15 од., що піде на задоволення заявки . Покладемо . Заявка і запас вичерпані. Звернемося до клітинки (2; 3): заявка 45 од., запас 35 од. Покладемо , далі і . Усі заявки забезпечені, запаси вичерпані. Підрахуємо кількість ненульових перевезень, яких намічується п’ять, а повинно бути . Щоб забезпечити потрібну кількість базисних клітин, треба у випадку, коли одночасно вичерпуються заявка і запас (так званий випадок виродженості), включити в базис ще одну (сусідню справа або знизу) клітину, записавши в неї величину або 0. Таким чином маємо табл. 1.3, де збалансовані заявки і запаси і є необхідна кількість базисних змінних, тобто 6.

Таблиця 1.3

Сформулюємо алгоритм методу північно-західного кута.

1. Беремо верхню ліву клітинку таблиці.

2. Порівнюємо заявку і запас. Менше з цих значень записуємо у клітинку. Від заявки і запасу віднімаємо цю величину. Переходимо до п. 3.

3. Якщо заявка була більша від запасу, беремо наступну знизу клітинку і переходимо до п. 2, інакше до п. 4.

4. Якщо запас був більше, ніж заявка, беремо наступну справа клітинку і переходимо до п. 2, інакше – до п. 5.

5. Запас і заявка рівні. Записуємо значення в клітинку, віднімаємо від заявки і запасу. Визначаємо, чи була клітина останньою (правою нижньою). Якщо так – переходимо до п. 7, якщо інакше – на п. 6.

6. У сусідню клітинку справа записуємо 0 і вважаємо її базисною. Беремо сусідню клітинку знизу і переходимо до п. 2.

7. Кінець.

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

.

Лекція 2. Знаходження оптимальногоплану перевезень методом потенціалів

2.1. Цикли як засоби поліпшення плану перевезень

Базисний план, наведений у табл. 8.3, очевидно, не оптимальний (зайняті клітини з великою вартістю і вільні з малою). Спробуємо зайняти клітину (2; 2), перенісши туди перевезення об’ємом з клітини (1; 2). Щоб зберігся баланс, треба від клітини (2; 3) відняти величину , а до клітини (1; 3) додати величину та отримати табл. 2.1.

Таблиця 2.1

Підрахуємо нове значення цільової функції:

,

тобто цільова функція зменшилася на 120 од.

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

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

- у кожній вершині зустрічаються дві ланки, одна розміщена по рядку, друга – по стовпчику;

- у кожній вершині здійснюється поворот на 90^о.

З означення циклу випливають його властивості:

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

- циклом може служити ламана, що самоперетинається, але точки перетину не можуть служити вершинами циклу.

Було здійснено простий цикл, що охоплював чотири клітини (табл. 2.2).

Таблиця 2.2

-	+
+	-

Цикли можуть бути набагато складнішими (табл. 2.3), де вершини циклу позначені хрестиками.

Таблиця 2.3

х		х		х			х
					х		х
		х			х
х						х
				х		х

Означення. Нехай є цикл, в якому деяка вершина вибрана як початкова. Надамо їй знак „+”, наступній „-” і т.д. Такий цикл називаємо означеним; клітини зі знаком „+” – додатними, із знаком „-” – від’ємними. Очевидно, у кожному рядку і стовпчику кількість додатних і від’ємних клітин буде рівною.

Цикл у табл. 2.2. зробили означеним.

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

Таким чином, перейшовши від табл. 1.3 до табл. 1.4, здійснили перенесення по циклу, наведеному у табл. 2.2.

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

У результаті циклу перерахунку ця вільна клітина стає базисною, а одна з базисних вільною.

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

Проаналізуємо доцільність операції перенесення по циклу.

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

У прикладі , , тому

.

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

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

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

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

Переглядів: 542