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

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

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.

Tagged with: , , ,
Posted in Математичні моделі в розрахунках на еом

Перелік предметів:
  1. Інформаційні технологіі в галузі
  2. Інформаційні технологіі в системах якості стандартизаціісертифікаціі
  3. Історія української культури
  4. Бухоблік у ресторанному господарстві
  5. Діловодство
  6. Мікропроцесорні системи управління технологічними процесами
  7. Науково-практичні основи технологіі молока і молочних продуктів
  8. Науково-практичні основи технологіі м’яса і м’ясних продуктів
  9. Організація обслуговування у підприємствах ресторанного господарства
  10. Основи наукових досліджень та технічноі творчості
  11. Основи охорони праці
  12. Основи підприємницькоі діяльності та агробізнесу
  13. Політологія
  14. Технологічне обладнання для молочноі промисловості
  15. Технологічне обладнання для м’ясноі промисловості
  16. Технологічний семінар
  17. Технологія зберігання консервування та переробки молока
  18. Технологія зберігання консервування та переробки м’яса
  19. Технологія продукціі підприємств ресторанного господарства
  20. Технохімічний контроль
  21. Технохімічний контроль
  22. Управління якістю продукціі ресторанного господарства
  23. Вища математика 3к.1с
  24. Вступ до фаху 4к.2с.
  25. Загальні технології харчових виробництв
  26. Загальна технологія харчових виробництв 4к.2с.
  27. Мікробіологія молока і молочних продуктів 3к.1с
  28. Математичні моделі в розрахунках на еом
  29. Методи контролю харчових виробництв
  30. Основи фізіології та гігієни харчування 3к.1с
  31. Отримання доброякісного молока 3к.1с
  32. Прикладна механіка
  33. Прикладна механіка 4к.2с.
  34. Теоретичні основи технології харчових виробництв
  35. Технологія зберігання, консервування та переробки м’яса
  36. Фізика
  37. Харчові та дієтичні добавки
  38. Фізичне виховання 3к.1с

На русском

  1. Методы контроля пищевых производств
  2. Общая технология пищевых производств
  3. Теоретические основы технологий пищевых производств
  4. Технология хранения, консервирования и переработки мяса
LiveInternet

Интернет реклама УБС