mi band

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

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

1. Огляд теми

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

2. Методи побудови опорного плану ТЗ.

3. Знаходження оптимального плану ТЗ методом потенціалів

2. Типові завдання.

В пунктах відправлення А1, А2, А3, …. знаходиться однорідний вантаж в кількості a1, а2, а3, …. відповідно, який необхідно перевезти в пункти призначення В1, В2, В3, …. , потреба кожного з яких становить b1, b2, b3, …. . Відома відстань між пунктами перевезень (оцінки).

Маємо три постачальника з такими запасами вантажу:

А1 = 26 т, А2 = 33 т, А3 = 45 т;

і чотири споживача з потребою на цей вантаж:

В1 = 14 т, В2 = 19 т, В3 = 20 т, В4 = 5 т.

Відома відстань між пунктами перевезень.

Відстань між пунктами перевезень, км (Сij).

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

Споживачі

B1

B2

B3

B4

A1

6

4

15

19

A2

13

17

28

3

A3

5

20

6

10

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

Рішення.

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

метод північно-західного кута; метод найменшої вартості; метод подвійної переваги.

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

— загальні запаси = 26+33+45 = 104 т;

— загальні потреби = 14+19+20+5 = 58 т.

Отже задача відкрита, тому необхідно ввести фіктивного споживача, якому слід перевезти Вфікт = 104–58 = 46 т.

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

Першу транспортну таблицю заповнимо методом північно-західного кута: першою заповнюється верхня ліва клітина Х11, в яку заноситься або всі запаси А1, або вся потреба В1 в залежності від того, що менше. На кожному наступному кроці розглядається перший з тих, що залишилися, пункт призначення або пункт відправлення:

—  якщо це пункт призначення, то потреба його визначається за правилом: Хij = ai — вивезений вантаж з Ai;

—  якщо це пункт відправлення, то запаси його визначається за правилом: Хij = bj — завезений вантаж в Bj.

Так заповнюються всі клітини таблиці з Х11 по ХMh (це заповнення має вигляд східців по діагоналі таблиці).

В клітину Х11 записуємо 14 і відповідно покривається вся потреба першого споживача за рахунок першого постачальника, в якого залишається вантаж в кількості: 26–14=12тон, який можна відвезти в другий пункт призначення. Тимчасово не розглядається стовпець В1. Потреба другого пункту споживання В2 становить 19тон, а за рахунок першого постачальника А1 можна завезти лише 12тон, 7тон завозиться з другого пункту відправлення. Тимчасово не розглядається рядок А1. В постачальника А2 було 33тони, з яких 7тон перевозиться в пункт споживання В2, 20тон в пункт споживання В3 та 1тонна в фіктивний пункт споживання ВФікт. Потреба фіктивного пункту споживання покривається за рахунок другого та третього постачальника.

При такому плані перевезень загальна кількість тонно-кілометрів буде становити:

Fmin=14*6+12*4+7*17+20*28+5*3+1*0+45*0=826 т-км.

За допомогою методу потенціалів можна визначити оптимальний план транспортної задачі. Задача має оптимальне значення, коли сума потенціалів в усіх клітинах таблиці не перевищує оцінок, тобто при рішенні задачі на мінімум план вважається оптимальним в тому випадку, якщо для всіх вільних клітинок дотримується вимога: Ui +Vj £Cij, а для зайнятих Ui +Vj =Cij.

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

Ui +Vj =Cij

Де: Cij — оцінка клітинки;

I — рядки (I = 1, 2, … , M),

J – стовпчики ( J=1, 2, … , H)

Ui — оцінка I–го рядка (I = 1, 2, … M)

Vj – оцінка J–го стовпця (J = 1, 2, … H)

Тобто, якщо відомий потенціал Ui, То Vj=Cij–Ui, а якщо відомий Vj, то Ui=CijVj . При цьому один з рядків або один з стовпчиків отримує довільну оцінку, а оцінки останніх рядків і стовпчиків треба розрахувати за вказаними формулами.

Нехай U1 =0, тоді потенціали першого та другого стовпчиків будуть становити:

V1=C11 –U1 = 6-0 = 6 для В1

V2=C12 –U1 = 4-0 = 4 для В2

Тепер можна визначити потенціал другого рядка:

U2 = C22 – V2 = 17 – 4 = 13

Визначимо потенціали для В3 , В4 І Вфікт:

V3=C23 –U2 = 28 — 13 = 15 для В3

V2=C24 –U2 = 3 — 13 = -10 для В4

V2=C25 –U2 = 0 — 13 = -13 для Вфікт

Тепер можна визначити потенціал А3:

U3 = C35 – V5 = 0 — (-13) = 13

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

Для Х13 сума потенціалів U1 + V3 = 0 + 15 = 15, що £ 15

Для Х14 сума потенціалів U1 + V4 = 0 + (-10) = -10, що £ 19

Для Х15 сума потенціалів U1 + V5 = 0 + (-13) = -13, що£ 0

Для Х21 сума потенціалів U2 + V1 = 13 + 6 = 19, що > 13

Для Х31 сума потенціалів U3 + V1 = 13 + 6 = 19, що > 5

Для Х32 сума потенціалів U3 + V2 = 13 + 4 = 17, що £ 20

Для Х33 сума потенціалів U3 + V3 = 13 + 15 = 28, що > 6

Для Х34 сума потенціалів U3 + V4 = 13 + (-10) = 3, що £ 10

Отже, даний план перевезень не є оптимальним, тому що в клітинках Х21, Х31, Х33 не виконується вимога Ui + Vj £ Cij. Необхідно перейти до наступного плану.

Для цього вибирається клітина, в якій сума потенціалів найбільш перевищує оцінку, це клітина Х33 і вона називається клітиною перерахунку.

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

Клітини, які ввійшли до фігури перерахунку позначаються по черзі знаками “+”, “-”,”+”, “-”, … , починаючи з клітини перерахунку.

Заповнюється нова транспортна таблиця:

—  кількість вантажу в клітинах, які не ввійшли до фігури перерахунку переноситься в нову таблицю без змін;

—  для клітин фігури перерахунку: кількість вантажу в клітинках зі знаком “+” збільшується, а в клітинках зі знаком “-“ зменшується на одну і ту ж величину, а саме, на найменшу кількість вантажу у клітинках, позначених знаком “-“.

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

При такому плані перевезень загальна кількість тонно-кілометрів буде становити:

FMin=14*6+12*4+7*17+5*3+21*0+20*6+25*0=386 т-км.

Обчислимо потенціали за правилом, описаним вище, і перевіримо складений план на оптимальність.

Для вільних клітин зробимо розрахунки:

Для Х13 сума потенціалів U1 + V3 = 0 + (-7) = -7, що £ 15

Для Х14 сума потенціалів U1 + V4 = 0 + (-10) = -10, що £ 19

Для Х15 сума потенціалів U1 + V5 = 0 + (-13) = -13, що £ 0

Для Х21 сума потенціалів U2 + V1 = 13 + 6 = 19, що > 13

Для Х23 сума потенціалів U2 + V3 = 13 +(-7) = 6, що£ 28

Для Х31 сума потенціалів U3 + V1 = 13 + 6 = 19, що > 5

Для Х32 сума потенціалів U3 + V2 = 13 + 4 = 17, що £ 20

для Х34 сума потенціалів U3 + V4 = 13 + (-10) = 3, що £ 10

Даний план перевезень не є оптимальним, тому що в клітинках Х21, Х31, не виконується умова оптимальності Ui + Vj £ Cij.

Вибирається клітина Х31, починаючи з неї будується фігура перерахунку.

Наступна транспортна таблиця має вигляд:

При такому плані перевезень загальна кількість тонно-кілометрів буде становити:

FMin=7*6+19*4+5*3+28*0+7*5+20*6+18*0=288 т-км.

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

Для Х13 сума потенціалів U1 + V3 = 0 + 7 = 7, що £ 15

Для Х14 сума потенціалів U1 + V4 = 0 + 4 =4, що £ 19

Для Х15 сума потенціалів U1 + V5 = 0 + 1 = -1, що > 0

Для Х21 сума потенціалів U2 + V1 = -1 + 6 = 5, що £ 13

Для Х22 сума потенціалів U2 + V2 = -1 + 4 = 3, що £ 17

Для Х23 сума потенціалів U2 + V3 = -1 + 7 = 6, що £ 28

Для Х32 сума потенціалів U3 + V2 = -1 + 4 = 3, що £ 20

для Х34 сума потенціалів U3 + V4 = -1 + 4 = 3, що £ 10

Даний план перевезень не є оптимальним, тому що в клітинці Х15 не дотримується вимога оптимальності Ui + Vj £ Cij. Побудуємо фігуру перерахунку та розрахуємо нову таблицю.

Малюємо фігуру перерахунку та розрахуємо нову таблицю.

Поста-чальники

Споживачі

Запаси

Потенціали, Ui

В1

В2

В3

В4

Вфіктивний

A1

6

4

15

19

0

26

0

19

7

A2

13

17

28

3

0

33

0

5

28

A3

5

20

6

10

0

45

0

14

20

11

Потреба

14

19

20

5

46

104

Потенціали, VJ

5

4

6

3

0

При такому плані перевезень загальна кількість тонно-кілометрів буде становити:

FMin=7*6+19*4+5*3+28*0+7*5+20*6+18*0=281 т.-км.

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

Для Х11 сума потенціалів U1 + V1 = 0 + 5 = 5, що £ 6

Для Х13 сума потенціалів U1 + V3 = 0 + 6 = 6, що £ 15

Для Х14 сума потенціалів U1 + V4 = 0 + 3 = 3, що £ 19

Для Х21 сума потенціалів U2 + V1 = 0 + 5 = 5, що £ 13

Для Х22 сума потенціалів U2 + V2 = 0 + 4 = 4, що £ 17

Для Х23 сума потенціалів U2 + V3 = 0 + 6 = 6, що £ 28

Для Х32 сума потенціалів U3 + V2 = 0 + 4 = 4, що £ 20

для Х34 сума потенціалів U3 + V4 = 0 + 3 = 3, що £ 10

Даний план перевезень є оптимальним, тому що в усіх клітинах таблиці виконується умова оптимальності.

При оптимальному плані перевезень загальна кількість тонно-кілометрів буде становити 281 т.-км.

Так, перевезення вантажу слід організувати таким чином:

—  з пункту А1 необхідно перевезти 19тон в пункт В2 та 7тон в пункт Вфікт;

—  з пункту А2 необхідно перевезти 5тон в пункт В4 та 28тон в пункт Вфікт;

—  з пункту А3 необхідно перевезти 14тон в пункт В1, 20тон в пункт В3 та 11тон в пункт Вфікт.

3. Рекомендована література

Курносов А. П., Сысоев И. А. Вычислительная техника т экономико-математические методы в сельском хозяйстве. — М., 1989. Кузнецов Ю. Н., Кузобов В. И., Ермольев Ю. М. Математическое программирование. — М.: Высш. шк., 1976. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986. Исследование операций в экономике: Учебн. пособие для вузов/ Н. Ш.Кремер, Б. А.Путко, И. М.Тришин. М. Н.Фридман; Под ред. проф. Н. Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997. Акулич И. Л. Математическое программирование в примерах и задачах. — М.: Высш. Шк.», 1986, — 319 с . Ляшенко И. Н. Линейное и нелинейное программирование. — і К.: Вищашк., 1975,-371 с.

7.  Математическое моделирование экономических процессов в сельском хозяйстве/ Гатаулин А. М. и др.; Под ред. А. М.Гатаулина. – М.: Агропромиздат, 1990. – 432с.:ил.

8.  Эддоус М., Стэнфилд Р. Методы принятия решений/ Пер. с англ. под ред. член-корр. РАН И. И.Елисеевой. – М.: Аудит, ЮНИТИ, 1997. – 590с.

Крушевский А. В., Шевцов К. И. Математическое программирование и моделирование в экономике.: Учеб. пособие для вузов. – Киев: Высшая школа. Головное изд-во, 1979. – 456с. Курицкий Б. Я. Поиск оптимальных решений средствами Excel 7.0. – СПб.: ВНV – Санкт-Петербург, 1997. – 384с., ил. Ляшенко И. Н. Лінійне та нелінійне програмування. — К.: Вища шк., 1975. Степанюк В. В. Методи математичного програмування. — К.: Вища шк., 1984. Кузнецов Ю. Н., Кудрявцев В. И. Математическое программирование. — М., 1980. Франс Дж. и др. Математические модели в сельском хозяйстве. М.: Агропромиздат, 1987 Кравченко Р. Г. Математическое моделирование в сельском хозяйстве. М.:Колос, 1978. Кузнецов Ю. Н. Математические модели в с/х. М.: Высшая школа, 1981 Карпенко А. ф. Практикум по математическому моделированию экономических агропромышленных процессов в сельском хозяйстве. М.: Финансы и статистика, 1985.

mi band