bannerka.ua

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

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

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 Математические модели в расчетах на эвм
No Comments » for Транспортная задача
3 Pings/Trackbacks for "Транспортная задача"

Добавить комментарий

Ваш e-mail не будет опубликован.

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

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