Решение транспортной задачи методом потенциалов

 

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

F₀ = 1039,  F₁ = 958,  F₂ = 877,  F₃ = 859,  F₄ = 733,  F₅ = 727,  F₆ = 717, F₇ = 709,

F₈ = F_min = 703.

Следует отметить также, что оптимальный план может иметь  и другой вид, но его стоимость  останется такой же F_min = 703.

2.2. Транспортная  задача с неправильным балансом (открытая).

 

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

(4)

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

Баланс транспортной задачи может  нарушаться в 2-х направлениях:

1. Сумма запасов  в пунктах отправления превышает  сумму поданных заявок 

2. Сумма поданных заявок  превышает наличные запасы 

Условимся первый случай называть “транспортной задачей  с избытком запасов“, а второй — “транспортной задачей с избытком заявок”.

Рассмотрим последовательно  эти два случая:

Транспортная задача с избытком запасов.

В пунктах A₁, A₂, ... , A_m имеются запасы груза a₁, a₂, ... , a_m; пункты B₁, B₂, ... , B_n подали заявки b₁, b₂, ... , b_n, причём

Требуется найти такой план перевозок (X), при котором все заявки будут выполнены, а общая стоимость перевозок минимальна. Очевидно, при этой постановке задачи некоторые условия равенства транспортной задачи превращаются в условия неравенства, а некоторые остаются равенствами.

 

Мы умеем решать задачу линейного программирования, в какой  бы форме — равенств или неравенств ни были бы заданы её условия. Поставленная задача может бать решена, например, обычным симплекс-методом. Однако, задачу можно решить проще, если искусственным приёмом свести её к ранее рассмотренной транспортной задаче с правильным балансом. Для этого сверх имеющихся n пунктов назначения В₁, B₂, ... , B_n введём ещё один, фиктивный пункт назначения B_n+1, которому припишем фиктивную заявку, равную избытку запасов над заявками:

b_n+1 =

а стоимость перевозок  из всех пунктов отправления в  фиктивный пункт назначения b_n+1 будем считать равным нулю. Введением фиктивного пункта назначения B _n+1 с его заявкой b_n+1 мы сравняли баланс транспортной задачи и теперь его можно решать как обычную транспортную задачу с правильным балансом.

Транспортная задача с избытком заявок.

Эту задачу можно свести к обычной транспортной задаче с  правильным балансом, если ввести фиктивный пункт отправления A_m+1 с запасом a_m+1, равным недостающему запасу, и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.

Заключение.

 

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

В ходе проектирования курсовой работы передо мной была поставлена следующая задача: подробно изучить теорию распределительных задач, а именно транспортной, и реализовать решение такой задачи в среде программирования Borland Delphi7. Считаю, что с данной задачей я справился. Знания, полученные мной в результате проведенной работы, понадобятся мне при выполнении следующих курсовых работ.

Написанная мной программа позволяет осуществить расчеты по нахождению оптимального решения транспортной задачи и значения ее целевой функции при различных исходных данных.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список используемой литературы.

 

1. Исследовании операций в экономике: Учебник для студентов вузов. Под редакцией Н.Ш. Кремера, 1999.
2. Экономико – математические методы и прикладные модели: Учебник. /  Под редакцией проф. Федосеева В.В.– М.: ЮНИТИ, 2000.
3. Экономико-математическое моделирование: Учебник для студентов вузов. Под общ. ред. И.Н. Дрогобыцкого. – М.: Издательство «Экзамен», 2004.
4. Бахтин А.Е. Математическое моделирование в экономике: Учебное пособие. – Новосибирск: НГЭАУ, 1995.
5. Справочная система Borland Delphi 7.