Задача о минимизации стоимости перегона транспортных средств

Овощехранилища	Магазины
	1	2	3
1	2	7	4
2	3	2	1
3	5	6	2
4	3	4	7

 

Составить план перевозок, минимизирующий суммарные транспортные расходы.

 

2. Экономико-математическая модель

 

Пусть xij, i=, j= – количество картофеля, поставляемого от i-ого овощехранилища к j-ому магазину.

Целевая функция:

F= 2x11+7x12+4x13+3x21+2x22+x23+5x31+6x32+2x33+3x41+4x42+7x43 ->min

Ограничения:

 

 

 

2. Практическая часть

 

Решение задачи методом северо-западного угла представлено в таблице 3.

Таблица 3 – Метод северо-западного угла

	17	12	32	19
20	2 17	7 3	4	0
20	3	2 9	1 11	0
15	5	6	2 15	0
25	3	4	7 6	0 19

F=2*17+7*3+2*9+1*11+2*15+7*6=156

 

Метод минимальной стоимости дает другой первоначальный план поставок груза и в соответствии с названием метода наименьшие суммарные затраты на доставку. Решение задачи методом минимальной стоимости представлено в таблице 4.

Таблица 4 – Решение методом минимальной стоимости

	17	12	32	19
20	2 1	7	4	0 19
20	3	2	1 20	0
15	5	6 3	2 12	0
25	3 16	4 9	7	0

F=2*1+1*20+6*3+2*12+3*16+4*9=148

 

1. Компьютерная модель

 

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

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

В книге Математические методы на листе Транспортная задача вводятся в соответствующие ячейки исходные данные задачи (рис. 1).

 

Рисунок 1 – Исходные данные

 

В ячейку С9 заносится целевая функция (единственная функция в таблице) (рис. 2).

Общая стоимость всех «элементарных» перевозок вычисляется как сумма произведений цены доставки одной тонный груза на объем груза, перевозимого в данном направлении: =C3*D3 + C4*D4 + C5*D5 + C6*D6 + E3*F3 + E4*F4 + E5*F5 + E6*F6 + G3*H3 + G4*H4 + G5*H5 + G6*H6 + I3*J3 + I4*J4 + I5*J5 + I6*J6.

 

Рисунок 2 – Компьютерная модель задачи

 

2. Компьютерный эксперимент

 

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

Выделить ячейку С9, в которой находится целевая функция. Выбрать команду Данные, Поиск решения (рис. 3).

 

Рисунок 3 – Поиск решения

 

В диалоговом окне в поле ввода Оптимизировать целевую функция уже содержится $С$9 (при необходимости эту ссылку можно изменить). Установить переключатель До Минимума.

 

Рисунок 4 – Окно поиска решения

 

Щелкнуть кнопку Предложить, и в поле ввода Изменяя ячейки переменных появится $C$2:$C$4;$E$2:$E$4;$G$2:$G$4;$I$2:$I$4;$K$2:$K$4 (рис. 5).

 

Рисунок 5 – Изменяемые ячейки

 

Щелкнуть кнопку Добавить, чтобы ввести первое ограничение задачи. В диалоговом окне Добавление ограничения в поле ввода Ссылка на ячейку указать $B$3. Правее в выпадающем списке с условными операторами выбрать =. В поле ввода Ограничение вводят $D$3+$F$3+$H$3+$J$3. Щелкнуть кнопку Добавить и ввести другие ограничения. Щелкнуть кнопку Ок. Добавление первого ограничения представлено на рисунке 6.

 

Рисунок 6 – Добавление ограничения

 

Оказавшись в диалоговом окне можно наблюдать введенные ограничения. С помощью кнопок Изменить и Удалить можно изменить и удалить ограничения. Все введенные ограничения представлены на рисунке 7.

 

Рисунок 7 - Ограничения

 

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

 

Рисунок 8 – Запуск Поиска решения

 

Установив кнопку Сохранить найденное решение, можно сохранить предложенные значения. С помощью этого диалогового окна (рис. 9) можно сформировать отчет.

 

Рисунок 9 – Решение задачи

 

Овощехранилище № 1 поставляет магазину № 1 17 т. картофеля, магазину № 4 3 т. картофеля. Овощехранилище № 2 поставляет магазину № 2 3 т. картофеля, магазину № 3 17 т. картофеля. Овощехранилище № 3 поставляет магазину № 3 15 т. картофеля. Овощехранилище № 4 поставляет магазину № 2 9 т. картофеля, магазину № 4 16 т. картофеля.

 

 

 

Заключение

 

В рамках курсовой работы была рассмотрена транспортная задача, ее применение и назначение. Найдены и рассмотрены методы решения транспортной задачи: метод северо-западного угла, метом минимальной стоимости, метод потенциалов. На основе этих методов, в частности, методе потенциалов построен Поиск решения, который позволяет решать не только транспортные задачи, но и многие другие, например: составление плана производства изделий; задача о назначениях; задача о диете (о смесях); задача о раскрое материала; задача о снабжении предприятий сырьем и другие.

 

 

 

 

Список использованных источников

 

1. Могилев А. В., Пак Н. И., Хённер Е. К. Информатика. – М.: Академия, 1999. – 587 с.
2. Просветов Г.И. Математические методы в экономике: Учебно-методическое пособие. – М.: Издательство РДЛ, 2004. – 160 с. – ISBN5-9340-047-3
3. Бережная Е. В., Бережной В. И. – Математические методы моделирования экономических систем: Учеб. пособие. – 2-е изд., перераб. и доп. – М.: Финансы и статистика, 2006. – 432 с.: ил. – ISBN5-279-02940-8
4. Фомин Г. П. – Математические методы и модели в коммерческой деятельности: Учебник. – 2-е изд., перераб. и доп. – М.: Финансы и статистика, 2005. – 616 с.: ил. – ISBN5-279-02828-2
5. Партыка Т. Л., Попов И. И. – Математические методы: учебник. 2-е изд., испр. и доп. – М.: ФОРУМ: ИНРФА-М, 2007. – 464 с.: ил. – ISBN978-5-91134-152-7 (ФОРУМ) ISBN978-5-16-003157-6 (ИНФРА-М)
6. http://ru.wikipedia.org/Транспортная_задача