Решение транспортной задачи методом Фогеля

Содержание

	Введение	4
1	Аналитическая часть	5
2	Технологическая часть	6
	Заключение	15
	Список литературы	26
	Приложения А Текст  программы	27

 

Введение

 

Исторически математическая экономика началась с моделей  простого и расширенного воспроизводства. В них отражались потоки денег и потоки товаров и продуктов. Это, например, модель Ф. Кенэ. Позднее эти модели подробно и более глубоко изучались в экономической кибернетике - здесь можно указать на работы О. Ланге. Рассмотрены схемы денежных и материальных потоков, обеспечивающих простое и расширенное воспроизводство, их идентификацию, модели математической статистики. Далее возникли концепции производственных функций, предельных и маргинальных значений, предельных полезностей и субъективных полезностей. Дальнейшее развитие - в рамках линейного и выпуклого программирования, выпуклого анализа, развитие тонких техник моделирования: имитационное моделирование, экспертные системы, нейронные сети.

Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации поставок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.  
Аналитическая часть

1. Описание и постановка задачи

 

Транспортная задача – это задача о наиболее экономном плане перевозок однородного продукта из пунктов производства (станций отправления) в пункты потребления (станции назначения).

Общая формулировка.

Некоторый однородный продукт  производится в m пунктах производства A₁, А₂,…,A_m. Задан объём производства  a_i пункта A_i ( ). Произведённый продукт должен быть перевезён в n пунктов потребления B₁, B₂, …,B_n. Известен спрос b_j пункта B_j ( ). Заданы также транспортные издержки C_ij, связанные с перевозкой единицы продукта из пункта A_i в пункт B_j. Требуется составить план перевозок, обеспечивающий при минимальных транспортных расходах удовлетворение спроса всех пунктов потребления за счёт продукта, произведённого во всех пунктах производства.

 

2. Описание и анализ математической модели

 

В поставленной задаче обозначив через х_ij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю, сведём задачу в так называемую матрицу планирования, представленную в таблице 1.1

 

Таблица 1.1

Поставщики	Потребители									Запасы
	B1		…	Bj		…	Bn
A1		x11			x1j			x1n		a1
	c11		…	c1j		…	c1n
…	…		…	…		…	…			…
Ai		xi1			xij				xin	ai
	ci1		…	cij		…	cin
…	…		…	…		…	…			…
Am		xm1			xmj				xmn	am
	cm1			cmj			cmn
Потребности	b1		…	bj		…	bn			Sai Sbj

 

Тогда математическая формулировка транспортной задачи сводится к минимизации линейной формы

                                                 

                                                    (1.1)

при ограничениях:

 ограничение по запасам:

                                                 

                                             (1.2)

ограничение по потребностям:

                                                                                                 (1.3) 

                                                           x_ij³0                                                           (1.4)                                     

Различают задачи с закрытой моделью, когда Sa_i=Sb_j и открытой моделью, когда Sa_i¹Sb_j, т.е. баланс между запасами и потребностями отсутствует.

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

                                                                                          (1.5)

Если  , то вводят фиктивный (n+1)-й пункт назначения с потребностью и полагают c_i,n+1=0, .

Если  , то вводят фиктивный (m+1)-й пункт отправления с запасами и принимают c_m+1,j=0, .

Основные особенности  транспортной задачи:

1. ограничения заданы в виде равенств;
2. каждая неизвестная входит лишь в 2 уравнения;
3. коэффициенты при неизвестных равны 1.

И хотя транспортная задача относится к задачам линейного  программирования, в связи с вышеперечисленными особенностями для её решения созданы специальные алгоритмы.

Решение транспортной задачи разбивается на 2 этапа:

1. Определение начального опорного плана.
2. Улучшение опорного плана.

Опорный план называется невырожденным, если содержит ровно (m+n-1) перевозку. Если перевозок меньше, чем m+n-1, то это вырожденный опорный план.

Для решения транспортной задачи используют различные методы, такие как: метод северо-западного  угла, метод минимальной стоимости, метод Фогеля и метод потенциалов.

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

Был выбран метод потенциалов, т.к. этот метод производит улучшение  опорного плана.

 

В методе Минимальной стоимости для отыскания опорного плана необходимо просмотреть всю матрицу стоимостей и выбрать наименьшую стоимость. Если таких стоимостей окажется несколько, то выбрать ту из них, в столбце или строке которой имеется наибольшая стоимость. Разместить в соответствующую клетку наибольшее возможное количество груза, при этом строка или/и столбец выпадает из дальнейших расчётов. С оставшимися стоимостями произвести те же действия. По окончании расчётов проверить правильность размещения перевозок в соответствии с отграничениями по запасам и по потребностям, посчитать стоимость перевозки.

 

Метод потенциалов можно  применить только к невырожденному опорному плану. Если план вырожден, то его можно дополнить необходимым  количеством нулевых перевозок.

Алгоритм метода потенциалов.

 

1. Любым методом построить опорный план, убедиться, что он невырожденный.
2. Каждому поставщику A_i поставить в соответствие некоторый потенциал u_i, а каждому потребителю B_j – потенциал p_j.
3. Для каждой перевозки опорного плана составить сумму потенциалов, приравнять её к стоимости перевозки: u_i+ p_j=с_ij. Таким образом будет получена система (m+n-1) уравнений с (m+n) неизвестными. Такая система имеет бесконечное множество решений.
4. Выделить одно из возможных решений системы, присвоив любому из неизвестных произвольное значение. Из полученных значений потенциалов составить матрицу :

 

5. Вычислить max( - c_ij). Если max( - c_ij)=0, то вычисления прекращаются и последний план является оптимальным. В противном случае в ячейку, соответствующую максимальной разности, ввести перевозку Q>0. Чтобы не нарушился баланс перевозок, нужно отнять и прибавить Q в строках и столбцах так, чтобы по стокам и столбцам суммы Q были равны 0.
6. Выписать все разности, содержащие Q и присвоить Q значение наименьшего из уменьшаемых. Пересчитать опорный план с учётом полученного значения Q, проверить правильность размещения перевозок в соответствии с отграничениями по запасам и по потребностям, посчитать стоимость перевозки. При этом стоимость перевозки в каждой следующей таблице не должна превышать стоимости из предыдущей таблицы.
7. Убедиться, что опорный план невырожден (или привести его к невырожденному виду) и перейти к п.2.

 

По окончании расчётов проверить правильность размещения перевозок в соответствии с отграничениями по запасам и по потребностям, посчитать стоимость перевозки.

Пример решения транспортной задачи методом Фогеля представленный в таблице 1.2

 

Таблица 1.2

3. Обоснование выбора инструментальных средств

 

Для написания программы, позволяющей решить данную проблему, был выбран язык Delphi (а именно Borland Delphi 7.0).  Причины такого выбора представлены ниже:

• Delphi - один из самых распространенных языков программирования (наряду с несколькими другими) и является языком высокого уровня.
• Delphi имеет очень мощную модель объектно-ориентированного программирования.
• В высших учебных заведениях и колледжах очень популярен язык Delphi, так как он является модернизированным «потомком» языка Pascal, широко применяемого во многих школах и лицеях, в качестве обучающего языка программирования.
• Создаваемые с его помощью программы могут работать не только под управлением Windows, а сама она относится к классу инструментальных средств ускоренной разработки программ.
• Визуальное конструирование форм избавляет программиста от многих аспектов разработки интерфейса программы, так как Delphi автоматически готовит необходимые программные заготовки и соответствующий файл ресурсов. Программист использует специальное окно, которое называется окном формы, как прототип будущего окна программы и наполняет его компонентами, реализующими нужные интерфейсные свойства (разного рода списки, кнопки, полосы прокрутки и т.п.). После размещения на форме очередного компонента, Delphi автоматически вставляет в связанный с формой модуль ссылку на компонент, и корректирует специальный файл описания формы с расширением DFM, который после компиляции преобразуется в ресурсный файл Windows.
• Использование компонентов не только во много раз сокращает сроки разработки программ, но и существенно снижает вероятность случайных ошибок, от которых, увы, не защищен ни один крупный программный проект. Однако в их применении есть оборотная сторона. Как правило, даже простые в функциональном отношении компоненты представляют лишь «вершину айсбергов» так как они создаются по объектно-ориентированной технологии и многие их функциональные черты наследуются от многочисленных родительских компонентов. В результате даже несложные программы, созданные в Delphi, редко имеют объем меньше сотен килобайт.
• Во всех случаях Delphi имеет самый быстрый среди продуктов подобного рода оптимизирующий компилятор, позволяющий создавать быстрые и относительно компактные программы.