Математические методы решения задачи о получении оптимального плана перевозок (транспортной задачи)

Стоимость перевозок по этому плану

 

Исследуем базисное решение на оптимальность.

Вычислим потенциалы и , исходя из базисных переменных:

 

 

 

,

,

 

 

 

 

Полагая, например, , найдем:

 

,
,
,

 

Для каждой свободной клетки вычислим относительные оценки:

 

 

 

 

 

 

 

 

Условие оптимальности плана перевозок  не выполняется, так как одна из оценок отрицательна.

Определим новое базисное решение.

Построим замкнутый цикл пересчета для свободной клетки (2, 1), для которой не выполняется неравенство, и перераспределим поставки согласно этому означенному циклу, аналогично п.3.

В клетку (2, 1) поместим груз .

После преобразований получаем новый  план перевозок:

 

 

	Пункты	B1	B2	B3	B4	Запасы
	A1	2	3	5 10	1 50	60
	A2	3 40	4 30	9	4 0	70
	A3	2	5	2 20	5	20
	Потребности	40	30	30	50	150

Стоимость перевозок по этому плану

 

Исследуем базисное решение на оптимальность.

Вычислим потенциалы и , исходя из базисных переменных:

 

 

,

,

 

,

 

 

Полагая, например, , найдем:

 

,
,
,

 

Для каждой свободной клетки вычислим относительные оценки:

 

 

 

 

 

 

 

 

Так как для всех свободных клеток таблицы неравенство  выполняется, то полученное решение

           

 

будет оптимальным. При этом значение целевой функции будет:

 

Таким образом, получен следующий план перевозок:

из пункта A₁ в пункт B₃ необходимо перевезти 10 ед. груза,

из пункта A₁ в пункт B₄ необходимо перевезти 50 ед. груза,

из пункта A₂ в пункт B₁ необходимо перевезти 40 ед. груза,

из пункта A₂ в пункт B₂ необходимо перевезти 30 ед. груза,

из пункта A₃ в пункт B₃ необходимо перевезти 20 ед. груза,

При таком  плане перевозок затраты на перевозку  будут наименьшими и составят 380 ден.ед.

 

3 РЕШЕНИЕ ЗАДАЧИ С ПОМОЩЬЮ НАДСТРОЙКИ EXCEL «ПОИСК РЕШЕНИЯ»

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

,

.

При таком подходе практически  все грузы будут перевезены и  все потребности удовлетворены.

3.1 Табличное представление модели

Вид электронной таблицы  в режиме отображения формул представлен  на рисунке 3.1.

В диапазон C6:F8 как исходные данные вводятся затраты на перевозку единицы груза от каждого поставщика к каждому потребителю. Искомая матрица объемов перевозок от каждого поставщика каждому потребителю расположена в диапазоне C13:F15. После работы оптимизатора в эти ячейки будет записан оптимальный план перевозок. В диапазоне C16:F16 вычисляются потребности в грузе как суммы по столбцам. В диапазоне G13:G15 – запасы поставщиков как суммы по строкам. Запасы груза у поставщиков и потребности в грузе представлены в диапазонах C17:F17 и  H13:H15. Затраты на перевозки по каждому направлению в отдельности вычисляются в диапазоне C22:G25. Общие затраты на перевозку в ячейке G25 необходимо минимизировать.

 

Рисунок 3.1 - Вид электронной таблицы в режиме отображения формул

В диапазон C6:F8 как исходные данные вводятся затраты на перевозку единицы груза от каждого поставщика к каждому потребителю. Искомая матрица объемов перевозок от каждого поставщика каждому потребителю расположена в диапазоне C13:F15. После работы оптимизатора в эти ячейки будет записан оптимальный план перевозок. В диапазоне C16:F16 вычисляются потребности в грузе как суммы по столбцам. В диапазоне G13:G15 – запасы поставщиков как суммы по строкам. Запасы груза у поставщиков и потребности в грузе представлены в диапазонах C17:F17 и  H13:H15. Затраты на перевозки по каждому направлению в отдельности вычисляются в диапазоне C22:G25. Общие затраты на перевозку в ячейке G25 необходимо минимизировать.

 

 

 

3.2 Настройка модели

В меню Сервис выполним команду Поиск решения. Появится диалоговое окно (Рисунок 3.2).

Рисунок 3.2 - Диалоговое окно «Поиск решения»

В поле Установить целевую ячейку вводим адрес G25. Для ввода адреса можно щелкнуть указателем мыши на этой ячейке.

В поле Равной выбираем вариант минимальному значению.

В поле Изменяя ячейки указываем переменные решения модели, в данном случае это диапазон C13:F15. Чтобы ввести их в данное поле, нужно щелкнуть на этом поле, а затем выделить на рабочем листе ячейки C13:F15. Ячейки данного диапазона выполняют роль переменных целевой функции и ограничений.

В поле Ограничения вводим две строки.

G13:G15<= H13:H15 – количества перевезенных грузов не может превышать возможности поставщиков (Рисунок 3.3);

Рисунок 3.3 - Диалоговое окно «Добавление ограничения»

 

C16:F16>= C17:F17 – количества доставляемых грузов не может быть меньше потребностей в нем (Рисунок 3.4).

 

Рисунок 3.4 - Диалоговое окно «Добавление ограничения»

Щелкнем по кнопке Параметры и в появившемся окне Параметры поиска решения установим переключатели: Линейная модель и Неотрицательные значения (Рисунок 3.5).

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

Щелчок по кнопке ОК позволяет вернуться в диалоговое окно Поиск решения.

 

 

 

 

 

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

Настройка модели произведена. Запускаем  процесс поиска решения нажатием кнопки Выполнить окна Поиск решения. По окончании счета появляется диалоговое окно Результаты поиска решения (Рисунок 3.6). Нажав соответствующую кнопку, можно сохранить найденное решение на рабочем листе или восстановить исходные значения, а также выбрать типы предлагаемых отчетов.

Рисунок 3.6 - Диалоговое окно «Результаты поиска решения»

 

 

3.4 Анализ решения

В результате решения получен оптимальный  план перевозок              (Рисунок 3.7), который отображается в диапазоне ячеек C13:F15:

,	,	,
	,	,
,			.

При таком  плане перевозок затраты на перевозку  будут наименьшими и составят (целевая ячейка G25) 380 ден. ед.

Рисунок 3.7 – Результаты поиска решения

 

  Заключение

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

В работе рассмотрена лишь одна из таких задач-транспортная, которая имеет важное значение в экономической деятельности при оптимальном планировании поставок.

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

 

 

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Агальцов В. П. Математические методы в программировании: учебник / В. П. Агальцов. – 2-е изд., перераб. и доп. – М.: ИД «ФОРУМ», 2010. – 240 с.: ил. – (Профессиональное образование).

Математические методы: учебник. – 2-е изд., испр. и доп. / Т.Л.Партыка, И. И. Попов. – М. : ФОРУМ : ИНФРА-М, 2009. – 464 с.: ил.

Методы оптимизации: практикум / Б. В. Соболь, Б. Ч. Месхи, Г. И. Каныгин. – Ростов н/Д: Феникс, 2009. – 380, [4]  с. (Высшее образование)

Палий И. А. Линейное программирование. Учебное пособие / И. А. Палий. – М.: Эксмо, 2008. – 256 с. – (Техническое образование).

Просветов Г. И. МЕТОДЫ ОПТИМИЗАЦИИ. Учебно-практическое пособие / Г. И. Просветов – М.: Издательство «Альфа-Пресс», 2009. – 168 с.