Решение задач линейного программирования транспортной задачей (309875)

Посмотреть архив целиком

Федеральное агентство по образованию

Федеральное государственное образовательное учреждение

среднего профессионального образования

Железногорский горно-металлургический колледж






КУРСОВАЯ РАБОТА

по дисциплине «Математические методы»

(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







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