bannerka.ua

Нахождение оптимального плана тз методом потенциалов

Нахождение оптимального плана ТС методом потенциалов.

1. Нахождение оптимального плана ТС методом потенциалов

1. В пунктах отправления А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 т.

Клетки с фиктивным потребителем (поставщиком) заполняются в последнюю очередь, нарушения условия оптимальности в этих клетках рассматривается лишь после того, как в основных клетках нарушения условия оптимальности не наблюдается.

Первую транспортную таблицу заполним методом северо-западного угла

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

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 т-км.

Выбирается клетка Х31, начиная с нее строится фигура пересчета.

Следующая транспортная таблица имеет вид:

Нахождение оптимального плана тз методом потенциалов При таком плане перевозок общее количество тонно-километров будет составлять:

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

Данный план перевозок не является оптимальным, так как в ячейке Х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 т.-км.

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

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

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

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

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

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

2. Терминологический словарь

Задача, в которой общие запасы равны общим потребностям называется Закрытой транспортной задачей

Клеткой Пересчета называют ячейку, в которой сумма потенциалов наиболее превышает оценку.

При решении задачи на минимум План считается оптимальным в том случае, если для всех свободных ячеек соблюдается требование: 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)

3. Рекомендуемая литература

1. Исследование операций в экономике: Учебн. пособие для вузов / Н. Ш. Кремер, Б. А. Путко, И. М. Тришин. М. Н. Фридман; Под ред. проф. Н. Ш. Кремера. — М.: Банки и биржи, ЮНИТИ, 1997.

2. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.

3. Бугир М. К. Математика для экономистов. Линейная алгебра, линейные модели: Учеб. пособие. — К.: ВЦ «Академия», 1998.

4. Гвоздинський А. М. Оптимизационные задачи в организационном управлении: Учеб. посиб.-Харьков: ХГТУРЭ, 1997.

5. Гетманцев В. Д. Линейная алгебра и линейное программирование:

Уч. пособие. — М.: Просвещение, 2001.

6. Григорков BC, Бойчук М. В. Практикум по математическому программированию: Учеб. пособие. — Черновцы: Прут, 1995.

7. Деордица Ю. С., Савченко В. Т. Компьютерные технологии в экономике и менеджменте: Учеб. пособие. — Луганск: ВУГУ, 1999.

8. Зайченко Ю. П. Исследование операций: Учебник. — М.:

ВШОЛ, 2000.

9. Исследование операций в экономике: Учеб. пособие / Под ред. Н. Ш. Кремера. — М.: ЮНИТИ, 1999.

10. Кигель В. Р. Элементы линейного, целочисленного линейного, нелинейного программирования: Учеб. пособие. — М.: ИСДО, 1995.

11. Мазараки А. А., Толбатов Ю. А. Математическое программирование в Ехсе1: Учеб. пособие. — К.: Четвертая волна, 1998.

12.Романюк Т. П., Терещенко Т. А., Присенко Г. В., Городкова И. М. Математическое программирование: Учеб. пособие. — М.: ИЗМН, 1996.

13.Цегелик Г. Г. Линейное программирование: Учеб. пособие. — М.: Мир, 1995.

14.Экономико-математические методы и прикладные модели: Учеб. пособие / Под ред. В. В. Федосеев. — М.: ЮНИТИ, 1999.

15.Крушевський А. В. Справочник по экономико-математическим моделям и методам. — К.: Техника, 1982, — 208 с.

Iб. Вивальнюк Л. М. Элементы линейного программирования. — М.: Вищашк., 1975, -191 с.

17. Шуенкин В. А., Жуков И. А. Основы Математического программирования. — М.: КМУГА, 1999, — 306 с.

18. Ляшенко И. Н. Линейное и нелинейное программирование. — И К. Вищашк., 1975, -371 с.

19. Богаенко И. М., Григорков BC, Бойчук М. В., Рюмашин М.0. Математическое программирование: Учеб. пособие. — М.: Логос, 1996.

Tagged with: , ,
Posted in Математические модели в расчетах на эвм
1 Comment » for Нахождение оптимального плана тз методом потенциалов
  1. Nombres Women Argentina Canada Pharmacy 24 Hour Drug Store Buy Now Isotretinoin buy generic cialis online Pak Online Reliable Rx Pharmacy Coupon Codes Discount Tadalafil

4 Pings/Trackbacks for "Нахождение оптимального плана тз методом потенциалов"
  1. […] найти оптимальный план перевозок метод потенциалов […]

  2. […] найти методом потенциалов оптимальный путь от пункта 1… […]

  3. […] фигуры при решении методом потенциалов […]

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

Ваш 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с
Возможно Вы искали: