Решение задач линейного программирования транспортной задачей (стр. 1 из 4)
Федеральное агентство по образованиюФедеральное государственноеобразовательное учреждение
среднего профессиональногообразования
Железногорский горно-металлургическийколледж
КУРСОВАЯ РАБОТА
по дисциплине «Математические методы»
(230105.51)
Решение задач линейногопрограммирования транспортной задачей
Выполнил студент гр. ПО-08
А.В. Гудов
Проверил преподаватель:
Н.А. Панасенко
2010 г.
Содержание
Введение
1. Характеристика класса задач
1.1 Общий вид решения и обобщение транспортной задачи
2. Содержательная постановка задачи
3. Математическая постановка задачи
4. Решение задачи
4.1 Математическое решение задачи
4.2 Решение задачи с помощью программы MS Excel
4.3 Листинг программы
4.4 Руководство пользователя
5. Анализ результатов
Заключение
Список используемой литературы
Введение
Под названием “транспортная задача”объединяется широкий круг задач с единой математической моделью. Данные задачиотносятся к задачам линейного программирования и могут быть решены симплекснымметодом. Однако матрица системы ограничений транспортной задачи настолькосвоеобразна, что для ее решения разработаны специальные методы. Эти методы, каки симплексный метод, позволяют найти начальное опорное решение, а затем,улучшая его, получить оптимальное решение.
Распределительныезадачи связаны с распределением ресурсов по работам, которые необходимовыполнить. Задачи этого класса возникают тогда, когда имеющихся в наличииресурсов не хватает для выполнения каждой работы наиболее эффективным образом.Поэтому целью решения задачи, является отыскания такого распределения ресурсовпо работам, при котором либо минимизируются общие затраты, связанные свыполнением работ, либо максимизируется получаемый в результате общий доход.
Основной целью задачиявляется минимизировать затраты на транспортировку продукции потребителям.
1. Характеристика класса задач
1.1 Общий вид решения и обобщениетранспортной задачи
Пустьтребуется перевезти груз из пункта А1, А2,…,Аnв пункты В1, В2,…,Вn.
а11,а12,…,аnk-стоимость перевозки из пункта Аi в пункт Вj.
А1=100;А2=200; А3=150; В1=80; В2=90; В3=120; В4=160.
Распределитьпродукцию так со склада, чтобы затраты были минимальные.
Построим начальную таблицу длязаполнения ячеек:
Таблица 1
Начальная таблица для заполненияячеек
| 4 | 7 | 7 | 1 | 100 | |||||
| 80 | 20 | ||||||||
| 12 | 3 | 8 | 8 | 200 | |||||
| 70 | 120 | 10 | |||||||
| 8 | 10 | 16 | 5 | 150 | |||||
| 150 | |||||||||
| 80 | 90 | 120 | 160 | ||||||
Прежде чем начать заполнение ячеек,необходимо проверить условие:
Сумма запаса и сумма потребления былиравны:
100+200+150=80+90+120+160; 450=450.
Принцип заполнения ячеек состоит втом, чтобы в выбранную ячейку заносилось минимальное число из стоящих напротивячеек с параметрами, например: для заполнения ячейки 1-А берутся значения 80 и 100: min= (80;100). Затем меньшее числовычитается из обеих ячеек-значений.
После заполнения необходимо найтицелевую функцию:
Z=80*4+20*7+70*3+120*8+10*8+150*5=3180
Получение начального опорного плана
- метод северо-западного угла
- метод наименьшей стоимости
I. Метод наименьшей стоимости:
· Определим ячейку с наименьшейстоимостью;
· Распределим как можно больше единиц вэту ячейку и вычеркнем строку или столбец, который исчерпан;
· Найдем ячейку с наименьшей стоимостьюиз оставшихся;
· Повторим пункт 2 и 3 пока все единицыне будут распределены.
Таблица 2
Определение ячеек методом наименьшейстоимости.
| 4 | 7 | 7 | 1 | 100 | ||||
| 100 | ||||||||
| 12 | 3 | 8 | 8 | 200 | ||||
| 90 | 110 | |||||||
| 8 | 10 | 16 | 5 | 150 | ||||
| 80 | 10 | 60 | ||||||
| 80 | 90 | 120 | 160 | |||||
Находим целевую функцию:
100*1+90*3+110*8+80*8+10*16+60*5=2350
Получили начальное решение.
II. Проверка решения на оптимальность:
- метод по камням
- метод Modi.
Проверка на оптимальность заключаетсяв оценке пустых ячеек, используя так называемый цикл.
Метод по камням:
Камни – заполненные ячейки
· Поставим знак «+», в ячейку которуюоцениваем;
· Двигаясь горизонтально иливертикально к заполненной ячейке(при этом можем пропустить заполненную илипустую ячейку которая, разрешит следующий переход к заполненной ячейке),поставим знак «-»;
· Изменяем направление и перемещаемся кдругой заполненной ячейке, выбираем ту разрешит следующий переход, ставим в неезнак «+»;
· Процесс перемещения в заполненнойячейке и чередование знаков продолжаем пока не вернемся к первоначальной.
Таблица 3
Оценивание ячеек
| 1-А | |
| 1А+4 | -8 3А |
| 3D+5 | -1 1D |
| 0 | |
| 1-C | |
| 1C+7 | -1 1D |
| 3D+5 | -16 3C |
| -5 | |
Оценка пустых ячеек методами возможнапри условии: число заполненных ячеек равна сумме строк и столбцов и -1:
k=R+L-1
Значение оценки показывает на сколькосократятся(увеличатся) затраты на перевозку единиц продукции если в эту ячейкупереместить значение.
Выбираем из оценок наибольшее помодулю отрицательное значение. Из отрицательных выбираем наименьшее и вычитаемего из всех ячеек пути.
Таблица 4
Изменение начальной таблицы
| 4 | 7 | 7 | 1 | 100 | |||||
| 10 | 90 | ||||||||
| 12 | 3 | 8 | 8 | 200 | |||||
| 90 | 110 | ||||||||
| 8 | 10 | 16 | 5 | 150 | |||||
| 80 | 70 | ||||||||
| 80 | 90 | 120 | 160 | ||||||
Таким образом, производим решение,находя новое оптимальное решение пока все оценки пустых ячеек будут содержатьтолько положительные значения и нули.
Метод MODI (модифицированное распределение).
Оценка пустых ячеек вычислениеминдексных значений строки и столбца.