Транспортная задача

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

Цикл называется означенным, если его угловые клетки пронумерованы по порядку и нечетным клеткам приписан знак «+», а четным - знак «-» (рис 1.)

1 2 + - - 5 + 6 + - 3 4

Рис 1.

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

Если таблица транспортной задачи содержит опорное решение, то при сдвиге по любому циклу, содержащему  одну свободную клетку, на величину = получится опорное решение.

3. Распределительный  метод Павлова Т.Н., Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002.

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

Пусть для транспортной задачи найдено начальное опорное  решение и вычислено значение целевой функции на этом решении. Х2.

Определим, как изменится  целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l, k), приращение целевой функции равно разности двух сумм: =, где - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком «+», - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком «-».

В клетках, отмеченных знаком «+», величины груза прибавляются, что приводит к увеличению значения целевой функции, а в клетках, отмеченных знаком «-», величины груза уменьшаются, что приводит к уменьшению значения целевой функции.

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

4. Венгерский метод

Идея метода была высказана венгерским математиком  Эгервари и состоит в следующем. Строится начальный план перевозок, не удовлетворяющий в общем случае всем условиям задачи (из некоторых пунктов производства не весь продукт вывозится, потребность части пунктов потребления не полностью удовлетворена). Алгоритм венгерского метода состоит из подготовительного этапа и из конечного числа итераций. На подготовительном этапе строится матрица X0 = {xij[0]}, элементы которой неотрицательны и удовлетворяют неравенствам:

, i = 1,…,m ,

, j = 1,…, n,

Если эти условия  являются равенствами, то матрица Хo - решение транспортной задачи. Если среди условий имеются неравенства, то осуществляется переход к первой итерации. На k-й итерации строится матрица Хk = {xij[k]}. Близость этой матрицы к решению задачи характеризует число Dk -- суммарная невязка матрицы Хk:

В результате первой итерации строится матрица Хl, состоящая из неотрицательных элементов. При этом Dl D0. Если Dl 0, то Хl - оптимальное решение задачи. Если Dl 0, то переходят к следующей итерации. Они проводятся до тех пор, пока Dk при некотором k не станет равным нулю. Соответствующая матрица Хk является решением транспортной задачи.

Венгерский метод  наиболее эффективен при решении  транспортных задач с целочисленными объемами производства и потребления. В этом случае число итераций не превышает величины D0/2 (D0 - суммарная  невязка подготовительного этапа).

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

5. Метод решения  задачи об оптимальных перевозках  средствами Ms Excel

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

Схема выполнения Павлова  Т.Н., Ракова О.А. Решение задач линейного программирования средствами Excel. Учебное пособие. - Димитровград, 2002.:

Для удобства расчетов необходимо отдельно создать матрицу, отображающую стоимость перевозок (рис. 5.1), а также матрицу, которая  должна будет отображать искомый  план перевозок (рис. 5.2.).

В таблице «Стоимость перевозок» в ячейках запасов  поставщиков и потребностей потребителей записать количество запасов поставщиков  и потребностей потребителей соответственно, указанное в условии задачи.

Таблицу «План перевозок» создать с пустыми полями (заполненными единицами), заранее заданного числового  формата. В ячейках запасов (потребностей) каждого поставщика (потребителя) ввести формулу, выполняющую суммирование всех возможных поставок этого поставщика (потребителя).

Рис. 5.1. Фрагмент окна программы MS Excel: Модель таблицы «Стоимость перевозок".

Рис. 5.2. Фрагмент окна программы Ms Excel: Модель таблицы «План перевозок».

В ячейке целевой  функции ввести формулу, высчитывающую  сумму произведений элементов матрицы  «Стоимость перевозок» и соответствующих  элементов матрицы «План перевозок».

В диалоговом окне функции  «Поиск решения» установить необходимые  ограничения, в целевой ячейке указать  адрес ячейки с формулой целевой  функции и установить ее равной минимальному значению, в качестве изменяемых ячеек  выбрать диапазон всех элементов  матрицы «План перевозок». Ограничения  в «Поиске решений» заключаются  в необходимости равенства запасов (потребностей), в матрице «План  перевозок» соответствующим запасам  и потребностям, указанным в матрице  «Стоимость перевозок». Также все  элементы матрицы «План перевозок» должны быть неотрицательными и целочисленными.

В диалоговом окне «Параметры поиска решений» установить параметр «Линейная модель» и число  итераций, равное 100.

Выполнить функцию  «Поиск решения» нажатием на кнопку «Выполнить». В качестве отчета по результатам  выбрать необходимый пункт в списке «Тип отчета» диалогового окна «Результаты поиска решения».

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

6. Решение транспортной  задачи

6.1 Постановка транспортной  задачи

Есть 3 поставщика с  мощностями с1, с2, с3 и 5 потребителей (их спрос d1, d2, d3, d4, d5 соответственно) некоторого груза. Стоимость доставки единицы груза от каждого поставщика к каждому потребителю задается матрицей А размера 3Ч5. Найти оптимальный план поставок.

с1 = 40, с2 = 90, с3 = 50,

d1 = 20, d2 = 25, d3 = 65, d4 = 50, d5 = 20.

6.2 Решение задачи

Изобразим матричную  запись задачи (табл. 6.2.1):

Модель закрытая, т.к. запасы равны потреблению: 

Стоимость перевозки  единицы продукции 

объемы производства  

Рис. 6.2.1. Фрагмент окна программы Ms Excel: Матрицы «План перевозок» и «Стоимость перевозок»

В ячейки, которые  должны отображать запасы поставщиков  и потребности потребителей в  матрице «План перевозок» вводим формулы, суммирующие значения всех возможных поставок данных поставщиков  и потребителей, например: B4=СУММ(C4:G4), C3=СУММ(C4:C6).

В ячейку целевой  функции (R6) введем =СУММПРОИЗВ(C4:G6;L4:P6).

Задача решается при помощи меню Сервис, пункт Поиск  решения.

В диалоговом окне «Поиск решения», согласно вышеуказанным правилам установим все необходимые ограничения  и ссылки на необходимые ячейки (рис. 6.2.2.).

Рис. 6.2.2. Диалоговое окно «Поиск решения»

 В диалоговом  окне «Параметры поиска решения»  установить необходимые параметры  (рис. 6.2.3.):

Рис. 6.2.3. Диалоговое окно «Параметры поиска решения»

После нажатия на кнопку «Выполнить» в диалоговом окне «Результаты поиска решения» нажать «Сохранить найденное решение», выделить необходимые типы отчетов и нажать «ОК».

План поставок   

Рис. 6.2.4. Фрагмент окна программы Ms Excel: Результат поиска решения

Полученное значение целевой функции равно 680.

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

 Ответ

Затраты на перевозку  всей продукции - 680 ден. ед.

Заключение

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

Список литературы

1. Красс М.С., Чупрынов Б.П. ”Основы математики и ее приложения в экономическом образовании”, Издательство “Дело”, Москва 2001г.

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

3. Павлова Т.Н., Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002.

4. Павлова Т.Н., Ракова О.А. Решение задач линейного программирования средствами Excel. Учебное пособие. - Димитровград, 2002.

5. Ермаков В.И.  Сборник задач по высшей математике  для экономистов. - М.: Издательство  Инфра, 2001, 574с.

6. Кузнецов А.В., Сакович В.А., Холод Н.И. ”Высшая математика. Математическое программирование ”, Минск, Вышейшая школа, 2001г.

7. В.И. Ермаков  “Общий курс высшей математики  для экономистов”, Москва, Инфра-М, 2000г.

8. Гончаров Е.Н., Ерзин А.И., Залюбовский В.В. Исследование операций. Примеры и задачи: Учеб. Пособие / Новосиб. Гос. ун-т. Новосибирск, 2005. 78с.

9. Береснев В.Л., Дементьев В.Т. Исследование операций. Введение. Учебное пособие. НГУ, 1979, I - 92.

10. Авдей А.Н. Анализ данных в Excel: под ред. Проф. А.А. Прихожего. - Мн.: БГПА, 2000