Смекни!
smekni.com

Нахождение минимальных затрат при распределении товаров среди магазинов методами решения транспо (стр. 3 из 3)

Для этого построим систему уравнений:

Из этой системы уравнений находим потенциалы , полагая, что u1 = 0:

v1=0, v2=27, v3=18, v4=25, v5=24, u1=0, u1=-3, u3=6

v1=0

v2=27

v3=18

v4=25

v5=24

u1=0

28

27[10]

18[120]

27

24[70]

u2=-3

18[190]

26

27

32

21[60]

u3=6

27

33[90]

23

31[110]

34

Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij, (3;3): 6 + 18 > 23

Выбираем максимальную оценку свободной клетки (3;3): 23

Для этого в перспективную клетку (3;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.


Из грузов стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 90. Прибавляем 90 к объемам грузов, стоящих в плюсовых клетках и вычитаем 90 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

B1

B2

B3

B4

B5

Запасы

A1

28

27[100]

18[30]

27

24[70]

200

A2

18[190]

26

27

32

21[60]

250

A3

27

33

23[90]

31[110]

34

200

Потреб.

190

100

120

110

130

Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij (Алгоритм нахождения потенциалов описан выше).

v1=0

v2=27

v3=18

v4=26

v5=24

u1=0

28

27[100]

18[30]

27

24[70]

u2=-3

18[190]

26

27

32

21[60]

u3=5

27

33

23[90]

31[110]

34

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

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Подсчитаем затраты на распределение товаров:

F = 27*100 + 18*30 + 24*70 + 18*190 + 21*60 + 23*90 + 31*110 = 15080

Результат: Затраты на распределение товаров между магазинами найденные методом наименьшей стоимости составят 15080рублей.

2.5 Метод аппроксимации Фогеля

Используя построенную матрицу тарифов, найдём оптимальный опорный план методом аппроксимации Фогеля.

B1

B2

B3

B4

B5

Запасы

A1

28

27

18

27

24

200

A2

18

26

27

32

21

250

A3

27

33

23

31

34

200

Потребности

190

100

120

110

130

Проверим необходимое и достаточное условие разрешимости задачи.

Условие баланса соблюдается. Запасы равны потребностям. Построим опорный план транспортной задачи:

B1

B2

B3

B4

B5

Запасы

Δcij

A1

28

27[100]

18

27[30]

24[70]

200

6,6,3,0

A2

18[190]

26

27

32

21[60]

250

3,5,5

A3

27

33

23[120]

31[80]

34

200

4,8,2,2

Потреб.

190

100

120

110

130

Δcij

9

1,6

5

4,4

3,10

Для нахождения опорного плана данным методом нужно найти разность между наименьшими элементами в столбцах и строках. Затем определяем наибольшую разность(Δcij). Дальше находим минимальный тариф в столбце (или строке) которому принадлежит Δcij, и отдаём ему сколько можно отдать : это тариф [A2;B1]. Исключаем из вычислений первый столбец .

И так продолжаем до тех пор пока все товары не будут найдены.

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

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Подсчитаем затраты на распределение товаров:

F = 27*100 + 30*30 + 24*70 + 18*190 + 21*60 + 23*120 + 31*80 = 15110

Результат: Затраты на распределение товаров между магазинами найденные методом наименьшей стоимости составят 15110 рублей.

2.6 Применение возможностей электронных таблиц при решении транспортной задачи

Для решения транспортной задачи также можно применять электронные таблицы (Microsoft Office Excel ).

Для решения задачи сначала нужно подготовить рабочий лист как показано на рис 1.


Рис 1. Исходные данные для решения транспортной задачи

Далее производим ввод данных в окно "Поиск решения" как показано на рис 2.

Рис 2. Ввод данных в окно "Поиск решения"

И нажимаем кнопку выполнить. Результат решения задачи представлен на рис 3.


Рис 3. Оптимальное решение для транспортной задачи

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

ЗАКЛЮЧЕНИЕ

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

Получены следующие результаты

Метод северо-западного угла: 19040 рублей

Метод наименьшей стоимости: 15170 рублей

Метод потенциалов: 15080 рублей

Метод аппроксимации Фогеля: 15110 рублей

Из этих методов наиболее оптимальным для данной задачи является метод потенциалов, так как при распределении товаров этим методом затраты оказались самыми минимальными в размере 15080 рублей

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

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


СПИСОК ЛИТЕРАТУРЫ И ИСТОЧНИКОВ

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

2. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании, М.: Дело, 2006г.

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

4. Боборыкин В.А. Математические методы решения транспортных задач. Л.: СЗПИ, 2007

5. Геронимус Б.А. Экономико-математические методы в планировании на автомобильном транспорте. М.: Транспорт, 2006

6. .Кузнецов Ю.Н., Кузубов В.И., Волощснко А. Б. Математическое программирование. М.: Высшая школа, 2009

7. Большакова И. В. , Кураленко М. В. Линейное программирование: учебно-методическое пособие М.: Айрис-пресс, 2009

8. Агальцов В.П., Волдайская И.В. Математические методы в программировании. М.: Инфра-М, 2006.

9. Рудикова Л.В. Microsoft Excel для студента СПб.: БХВ-Петербург, 2006

10. Партыка Т.Л., Попов И.И. Математические методы М.:Форум,2007