Федеральное агентство по образованию
Федеральное государственное образовательное учреждение
среднего профессионального образования
Железногорский горно-металлургический колледж
КУРСОВАЯ РАБОТА
по дисциплине «Математические методы»
(230105.51)
Решение задач линейного программирования транспортной задачей
Выполнил студент гр. ПО-08
А.В. Гудов
Проверил преподаватель:Н.А. Панасенко
2010 г.
Содержание
Введение
Глава 1
1.1 Гипотеза и описание алгоритма математической задачи
1.2 Теорема решения поставленной задачи
1.3
Глава 2 Решение задачи
2.1 Построение и решение математической модели данной задачи
2.2 Решение задачи с помощью программы MS Excel
2.3 Решение задачи с помощью MathCAD
Заключение
Список используемой литературыВведение
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найтиначальное опорное решение, а затем, улучшая его, получить оптимальное решение.
Распределительные задачи связаны с распределением ресурсов по работам, которые необходимо выполнить. Задачи этого класса возникают тогда, когда имеющихся в наличии ресурсов не хватает для выполнения каждой работы наиболее эффективным образом. Поэтому целью решения задачи, является отыскания такого распределения ресурсовпо работам, при котором либо минимизируются общие затраты, связанные с выполнением работ, либо максимизируется получаемый в результате общий доход.
Основной целью задачи является минимизировать затраты на транспортировку продукции потребителям.
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
108
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.
Проверка на оптимальность заключается в оценке пустых ячеек, используя так называемый цикл.
Метод по камням:
Камни – заполненные ячейки
Поставим знак «+», в ячейку которую оцениваем;
Двигаясь горизонтально или вертикально к заполненной...
Федеральное государственное образовательное учреждение
среднего профессионального образования
Железногорский горно-металлургический колледж
КУРСОВАЯ РАБОТА
по дисциплине «Математические методы»
(230105.51)
Решение задач линейного программирования транспортной задачей
Выполнил студент гр. ПО-08
А.В. Гудов
Проверил преподаватель:Н.А. Панасенко
2010 г.
Содержание
Введение
Глава 1
1.1 Гипотеза и описание алгоритма математической задачи
1.2 Теорема решения поставленной задачи
1.3
Глава 2 Решение задачи
2.1 Построение и решение математической модели данной задачи
2.2 Решение задачи с помощью программы MS Excel
2.3 Решение задачи с помощью MathCAD
Заключение
Список используемой литературыВведение
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найтиначальное опорное решение, а затем, улучшая его, получить оптимальное решение.
Распределительные задачи связаны с распределением ресурсов по работам, которые необходимо выполнить. Задачи этого класса возникают тогда, когда имеющихся в наличии ресурсов не хватает для выполнения каждой работы наиболее эффективным образом. Поэтому целью решения задачи, является отыскания такого распределения ресурсовпо работам, при котором либо минимизируются общие затраты, связанные с выполнением работ, либо максимизируется получаемый в результате общий доход.
Основной целью задачи является минимизировать затраты на транспортировку продукции потребителям.
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
108
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.
Проверка на оптимальность заключается в оценке пустых ячеек, используя так называемый цикл.
Метод по камням:
Камни – заполненные ячейки
Поставим знак «+», в ячейку которую оцениваем;
Двигаясь горизонтально или вертикально к заполненной...
Поделиться рефератом
Расскажи своим однокурсникам об этом материале и вообще о СкачатьРеферат