WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 ||

Груз будет перераспределен по клеткам цикла на величину x = min xij следующим образом. В клетках со знаком «плюс» значение перевозки нужно увеличить на величину x, а в клетках со знаком «минус» – уменьшить на величину x. Так как после пересчета у нас добавилась лишняя базисная клетка, то их количество необходимо сократить, убрав нуль в одной из клеток цикла. Если таких клеток получилось несколько, то свободной делаем ту из них, в которой тариф перевозок максимален.

После этого полученный план проверяется на оптимальность описанным выше способом. Перераспределение груза производится до тех пор, пока очередной план не станет оптимальным. На этом действие алгоритма завершается.

Покажем, как нужно пользоваться методом потенциалов, на примере первоначального плана, полученного выше по методу северо-западного угла.

Вначале проверим, не является ли этот план вырожденным. Так как m + n -1 = 3 + 4 -1 = 6, и число базисных клеток в плане также равно 6, то план в пополнении не нуждается. Найдем потенциалы по базисным клеткам таблицы с помощью формул (7), положив u1 = 0, u1 + v1 = 4, u1 = 0, u + v2 = 8, u = -8, 1 -4, u1 + v3 = 10, u3 = u + v3 = 2, v = 4, 2 u + v3 = 6, v = 8, 3 v3 = 10, u3 + v4 = 5, u = 0, v = 9, 1 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-и занесем полученные значения в таблицу. Вычислим теперь разности cij для свободных клеток и также проставим эти данные в левых нижних углах соответствующих клеток. В итоге получим следующую таблицу 4.

Т а б л и ц а заказы B1 B2 B3 Bзапасы u 100 40 80 4 8 10 A100 40 20 – 4 6 2 A30 – 8 6 4 4 6 A30 – 4 v 4 8 10 Поскольку c14 = -4 < 0, то этот план не является оптимальным. Перераспределим груз по циклу, обозначенному в таблице 4 пунктиром, на величину x = min(20,60) = 20. Для этого в клетках со знаком «плюс» увеличим поставки на 20 единиц, а клетках со знаком «минус» – поставки на столько же уменьшим. Для сохранения количества базисных клеток число 0 в клетке (1,3) не записываем, и она становится свободной.

Вычислив потенциалы и разности cij для нового плана, видим, что снова есть отрицательная разность c32 = -4. Поэтому придется еще раз улучшать план. С этой целью перераспределим груз по циклу, отмеченному в таблице 5 пунктиром, на величину x = min(40,40) = 40. Так как в результате в цикле получаются две клетки с нулевыми перевозками: (1,3) и (3,4), то ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-сделаем свободной клетку (1,3), поскольку ее тариф перевозок больше. После перераспределения груза по циклу вычислим все необходимые разности cij.

Т а б л и ц а заказы B1 B2 B3 Bзапасы u 100 40 80 4 8 10 A 40 100 4 6 2 A30 – 4 2 4 4 6 A50 0 – 4 v 4 8 6 Как видим, все cij неотрицательны, значит, план оптимален (таблица 6).

Т а б л и ц а заказы B1 B2 B3 Bзапасы u 100 40 80 4 8 10 A100 4 4 6 2 A30 – 4 6 4 4 6 A40 50 0 v 4 4 6 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-6. Пример решения типовой транспортной задачи Задача 6.1. На складах трех поставщиков A1, A2, A3 хранится 300, 250 и 200 единиц одного и того же груза. Этот груз требуется доставить четырем потребителям B1, B2, B3 и B4, заказы которых составляют 220, 150, 250 и единиц груза соответственно. Стоимости перевозок cij единицы груза с i-го склада j -му потребителю указаны в правых верхних углах соответствующих клеток транспортной таблицы 7.

Т а б л и ц а заказы B1 B2 B3 Bзапасы 220 150 250 4 5 3 A7 2 1 A6 1 4 AСоставить такой план перевозок груза, при котором общая стоимость всех перевозок была бы минимальной.

Решение. Поскольку суммарный запас груза а = 300 + 250 + 200 = меньше суммарной потребности b = 220 + 150 + 250 + 180 = 800, то рассматриваемая транспортная задача является открытой. Сведем ее к закрытой, добавив фиктивного поставщика A'4 с нулевыми тарифами перевозок и запасом груза a'4 = b - a = 50.

Составим первоначальный план перевозок с помощью метода наименьшей стоимости, заполняя клетки в следующем порядке:

(4,2) (3,2) (2,3) (3,4) (1,1) (1,4).

Получим таблицу 8.

ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-Т а б л и ц а заказы B1 B2 B3 Bзапасы 220 150 250 4 5 3 A220 7 2 1 A6 1 4 A 100 0 0 0 A' Перейдем к анализу полученного плана. Заметим, что в этой задаче m + n -1 = 4 + 4 -1 = 7, а число занятых клеток в имеющемся плане равно 6.

Значит, необходимо пополнить план еще 1 клеткой, записав в ней 0, так, чтобы пополненный план получился ациклическим. Выберем для этой цели, например, клетку (4,3).

Вычислим потенциалы по базисным клеткам плана u1 + v1 = 4, u1 = 0, u + v4 = 6, u = -4, 1 -4, u2 + v3 =1, u3 = u + v2 =1, u = -5, 3 u3 + v4 = 2, v1 = 4, u4 + v2 = 0, v2 = 5, = 5, u + v3 = 0, vu = 0, v4 = 6, и вычислим для свободных клеток разности cij = cij - (ui + v ).

j Получим таблицу 9.

ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-Т а б л и ц а потребности B1 B2 B3 Bзапасы u 220 150 250 4 5 3 A220 – 7 2 1 A250 – 7 1 6 1 4 A – 6 0 0 0 A'– 50 1 – v 4 5 5 Поскольку среди чисел cij есть отрицательные, то перераспределим груз на величину x = min(80,100,0) = по циклу, обозначенному пунктиром. Клетка (1,3) станет базисной вместо клетки (4,3), и мы получим таблицу 10.

План, указанный в таблице 10, не является оптимальным, поскольку c22 = c44 = -1< 0.

Улучшим этот план с помощью перераспределения поставок по циклу, обозначенному в таблице 10 пунктиром, на величину x = min(100,50) = 50.

Получим таблицу 10.

ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-Т а б л и ц а заказы B1 B2 B3 Bзапасы u 220 150 250 4 5 3 A0 220 7 2 1 A250 – 5 – 1 6 1 4 A– 0 0 0 A'– – 1 v 4 5 3 В таблице 11 перераспределение осуществляется по ступенчатому циклу.

Т а б л и ц а заказы B1 B2 B3 Bзапасы u 220 150 250 4 5 3 A220 7 2 1 A250 – 5 – 1 6 1 4 A – 6 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28- 0 0 0 A'– 2 v 4 5 3 После еще одного перераспределения поставок на величину x = 80, получим таблицу 12.

Т а б л и ц а заказы B1 B2 B3 Bзапасы u 220 150 250 4 5 3 A220 1 7 2 1 A250 – 80 5 6 1 4 A– 5 0 0 0 A'50 – 1 1 v 4 4 3 Заметим, что после каждого перераспределения груза производились вычисления потенциалов и разностей cij для полученного плана, и эти данные проставлялись в таблицу.

В таблице 12 все разности cij 0, следовательно, план оптимален. Таким образом, 220 0 80 X = 0 80 170 0.

опт 0 70 0 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-Фиктивный груз a'4 = 50 в таблице12 означает, что потребителю Bбудет недопоставлено 50 единиц груза.

Найдем суммарную стоимость перевозок по оптимальному плану:

3 zmin = c xij = 4 220 + 3 80 + 2 80 + 1170 + 1 70 + 2 130 =1780.

ij i=1 j=ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ 1. Что называется транспортной задачей 2. Что называется тарифом перевозки в транспортной задаче 3. Какая транспортная задача называется закрытой 4. Какая транспортная задача называется открытой 5. В чем состоит процедура закрытия открытой транспортной задачи 6. Что называется фиктивным поставщиком 7. Что называется фиктивным потребителем 8. Что называется потенциалом в транспортной задаче 9. В чем состоит схема решения транспортной задачи с помощью метода потенциалов 10. Как строится первоначальный план перевозок с помощью метода северо-западного угла 11. Как строится первоначальный план перевозок с помощью метода наименьшей стоимости 12. Что называется циклом в транспортной таблице 13. Какие клетки транспортной таблицы называются базисными 14. Какие клетки транспортной таблицы называются свободными 15. Какой план перевозок называется вырожденным 16. Какой план называется ациклическим 17. В чем состоит схема пополнения вырожденного плана перевозок 18. В чем состоит критерий оптимальности плана при решении транспортной задачи методом потенциалов ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 1. Транспортная задача задана следующей транспортной таблицей:

заказы B1 B3 Bзапасы 20 25 6 4 A3 5 A3 6 A1.1. Выяснить, является задача открытой или закрытой;

1.2. Составить первоначальный план перевозок с помощью метода северо-западного угла;

1.3. Составить первоначальный план перевозок с помощью метода наименьшей стоимости;

1.4. С помощью метода потенциалов найти оптимальный план перевозок, обеспечивающий их минимальную стоимость;

1.5. Найти минимальную стоимость перевозок.

ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-ЛИТЕРАТУРА Основная:

1. Вентцель Е.С. Исследование операций: Задачи, принципы, методология.

Учебное пособие. – М.: Дрофа, 2004.

2. Колемаев В.А. Математическая экономика. Учебник для вузов. - М.:

ЮНИТИ-ДАНА, 2005.

3. Кремер Н.Ш. Исследование операций в экономике. – М.: ЮНИТИ, 2006.

4. Орехов Н.А., Левин А.Г., Горбунов Е.А. Математические методы и модели в экономике. Учебное пособие для вузов / Под ред. проф. Н.А. Орехова – М.: ЮНИТИ-ДАНА, 2004.

Дополнительная:

5. Экономико-математическое моделирование. Учебник для вузов / Под общ. ред. И.Н. Дрогобыцкого. – М.: Изд. «Экзамен», 2004.

6. Лунгу К.Н. Линейное программирование. Руководство к решению задач. – М.: Физматлит, 2005.

7. Малыхин В.И. Математика в экономике: Учебное пособие. – М.: ИНФРА-М, 2002.

8. Самаров К.Л., Шапкин А.С. Задачи с решениями по высшей математике и математическим методам в экономике: Учебное пособие – М.: Издательско-торговая корпорация «Дашков и Ко», 2007.

9. Таха Х.А. Введение в исследование операций. – М.: ВИЛЬЯМС, 2007.

ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10

Pages:     | 1 ||










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.