<<
>>

3.Метод потенциалов.

Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система n+m действительных чисел, и , , удовлетворяющих следующим условиям:

                              при                                (5)

при .                              (6)

Числа и называют потенциалами.

Группа равенств (5) используется как система уравнений для нахождения потенциалов. Данная система уравнений имеет n+m неизвестных, и , .

Число уравнений системы, как  число отличных от нуля координат невырожденного опорного решения, равно m+n-1. Т.к. число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно (чаще нуль), а остальные найти из системы.

Группа неравенств (6) используется для проверки оптимальности опорного решения. Эти неравенства удобнее представить в следующем виде:

, при .

Числа называются оценками для свободных клеток таблицы (векторов условий) транспортной задачи.

Опорное решение является оптимальным, если для всех векторов условий (клеток таблицы) оценки неположительные.

Оценки для свободных клеток транспортной таблицы используются при улучшении опорного решения. Для этого находят клетку (l,k), соответствующую . Если , то решение оптимальное. Если же  , то для соответствующей клетки (l,k) строят цикл и улучшают решение, перераспределяя груз по этому циклу.

Особенности решения транспортных задач с неправильным балансом:

1. Если суммарные запасы поставщиков превосходят суммарные запросы потребителей, т.е. , то необходимо ввести фиктивного (n+1)- го потребителя с запросами , равным разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза .

2. Если суммарные запросы потребителей превосходят суммарные запросы поставщиков, т.е. , то необходимо ввести фиктивного (m+1)-го поставщика с запасами , равными разности суммарных запросов потребителей и запасов поставщиков, и нулевыми стоимостями перевозок единиц груза .

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

Алгоритм решения транспортных задач методом потенциалов.

  1. Проверить выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводится фиктивный поставщик или потребитель с недостающими запасами или запросами и нулевыми стоимостями перевозок.
  2. Построить начальное опорное решение (методом северо-западного угла или др. методом).
  3. Построить систему потенциалов, соответствующих опорному решению.
  4. Проверить выполнение условия оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам , и те из них, которые больше нуля записывают в левые нижние углы клеток. Если для всех свободных клеток , то вычисляют значение целевой функции и решение задачи заканчивается, т.к. полученное решение является оптимальным. Если же имеется, хотя бы одна клетка с положительной оценкой.
    Опорное решение не является оптимальным.
  5. Перейти к новому опорному решению. На котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка . Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину . Клетка со знаком «-», в которой достигается , остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным m+n-1.
  6. Далее перейти к п.3.

Пример.Решить транспортную задачу, исходные данные которой представлены в таблице:

200

200

300

400

200

4

3

2

1

300

2

3

5

6

500

6

7

9

12

1.Находим суммарные запасы поставщиков и суммарные запасы потребителей:        

.

Т.о. задача с неправильным балансом. Вводим четвертого, фиктивного поставщика с запасами и нулевыми стоимостями перевозок единиц груза. Получаем следующую таблицу

200

200

300

400

200

4

3

2

1

200

300

2

200

3

100

5

6

500

6

7

100

9

300

12

100

100

0

0

0

0

100

2.Находим начальное опорное решение методом минимальной стоимости. Полученное решение имеет m+n-1=4+4-1=7 базисных переменных. Вычисляем значение целевой функции на этом опорном решении:

3.Для проверки оптимальности опорного решения необходимо найти потенциалы.

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

Пусть =0. Остальные потенциалы находятся однозначно:

-

.

Запасы потенциалов записывают в следующую таблицу.

                                                                             

200

200

300

400

nbsp;

200

4

-

3

-

2

-

1

200

300

2

200

3

-

100

5

0

   6

         +

2

500

6

0

7

100

+

9

300

12

100

         -

100

0

-

0

-

0

-

0

100

Любой неизвестный потенциал, соответствующий занятой клетке, равен находящейся в этой клетке стоимости минус известный потенциал, соответствующий этой же клетке.

4.Проверяем опорное решение на оптимальность. С этой целью вычисляем оценки для всех незаполненных клеток таблицы (для всех занятых ):

, ,

, .

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

5.Переходим к новому опорному решению. Для клетки (2, 4) с положительной оценкой строим цикл. Ставим в эту клетку «+», присоединяем ее к занятым клеткам и, применяя метод вычеркивания, находим цикл (2,4), (3,4), (3,2), (2,2). Цикл представлен в таблице. В угловых точках цикла расставляем поочередно знаки «+» и «-», начиная с клетки (2,4). В клетки, отмеченные знаком «+», добавляется груз , а из клеток со знаком «-», убавляется такой же по величине груз. Определяем величину , перераспределяемого по циклу. Она равна значению наименьшей из перевозок в клетках цикла, отмеченных знаком «-»:. Осуществляем сдвиг по циклу на величину .

Получаем второе опорное решение .

                                                                              

200

200

300

400

nbsp;

200

4

-

3

-

2

-

1

200

300

2

200

3

0

5

0

6

100

500

6

0

7

200

9

300

12

-

100

0

-

0

-

0

-

0

100

Находим для этого решения потенциалы (приведены в таблице) и вычисляем оценки:

, ,

  ,

, .

Все оценки неположительные, следовательно, решение является оптимальным. Значение целевой функции:

Ответ: min Z(X)=5200, при .

<< | >>
Источник: А.А.Копанева, А.В. Овсянникова, И.Ф.Авдеев. Математические методы в экономике. Учебно-методическое пособие для студентов экономических специальностей.- М.: МГУТУ,2009.. 2009

Еще по теме 3.Метод потенциалов.:

- Авторское право - Аграрное право - Адвокатура - Административное право - Административный процесс - Антимонопольно-конкурентное право - Арбитражный (хозяйственный) процесс - Аудит - Банковская система - Банковское право - Бизнес - Бухгалтерский учет - Вещное право - Государственное право и управление - Гражданское право и процесс - Денежное обращение, финансы и кредит - Деньги - Дипломатическое и консульское право - Договорное право - Жилищное право - Земельное право - Избирательное право - Инвестиционное право - Информационное право - Исполнительное производство - История - История государства и права - История политических и правовых учений - Конкурсное право - Конституционное право - Корпоративное право - Криминалистика - Криминология - Маркетинг - Медицинское право - Международное право - Менеджмент - Муниципальное право - Налоговое право - Наследственное право - Нотариат - Обязательственное право - Оперативно-розыскная деятельность - Права человека - Право зарубежных стран - Право социального обеспечения - Правоведение - Правоохранительная деятельность - Предпринимательское право - Семейное право - Страховое право - Судопроизводство - Таможенное право - Теория государства и права - Трудовое право - Уголовно-исполнительное право - Уголовное право - Уголовный процесс - Философия - Финансовое право - Хозяйственное право - Хозяйственный процесс - Экологическое право - Экономика - Ювенальное право - Юридическая деятельность - Юридическая техника - Юридические лица -