Закрытая транспортная задача

Изм.

Лист

№ докум.

Подпись

Дата

Лист

3

 

230105-КП.02-12-9176

 Разраб.

Н.С. Чугунов 

 Провер.

М.В. Кондурар

 

 

 

 

 

 

Закрытая транспортная задача

Лит.

Листов

36

В-31 ТПК

Изм.

Лист

№ докум.

Подпись

Дата

Лист

35

230105-КП.02-12-9176

 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

 

Государственное бюджетное образовательное

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

Тольяттинский политехнический  техникум

(ГБОУ СПО ТПТ)

 

 

 

 

 

 

 

 

 

Отделение по специальности 230105 «Программное обеспечение вычислительной техники и автоматизированных систем»

 

 

 

 

 

 

 

КУРСОВОЙ ПРОЕКТ

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

Тема: «Закрытая транспортная задача»

 

 

 

 

 

 

Специальность		230105 «Программное обеспечение  вычислительной техники и автоматизированных  систем»
Группа		В-31
Студент		Н.С.Чугунов
Руководитель проекта		М.В.Кондурар

 

 

Тольятти, 2012

 

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ  ФЕДЕРАЦИИ

 

Государственное бюджетное образовательное 

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

Тольяттинский политехнический  техникум

(ГБОУ СПО ТПТ)

 

 

 

 

 

УТВЕРЖДЕНО

Зав. УПР отделения №4

_____________  Л.Г.  Светличная

___.___.20___

 

 

 

 

 

ЗАДАНИЕ

на курсовое проектирование по дисциплине

«Математические методы»

 

Студенту специальности 230105 «          Программное обеспечение ВТ и АС                       » группы                                                                              В-31     

Фамилия, имя, отчество                            Чугунову Николаю Сергеевичу   

Тема проекта                                                Закрытая транспортная задача                                                                    

_____________________________________________________________________________

_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________

 

Начало проектирования 12.01.2012 Окончание проектирования 30.05.2012

 

Руководитель курсового  проекта Кондурар М.В.                                                                            

 

Задание получил______________________________________________________________

 

 

Содержание

Введение 4

1 Линейное  программирование 5

1.1 Основные  понятия линейного программирования 5

1.2 Общая задача  линейного программирования 6

1.3 Задача  об оптимальном плане перевозок грузов (транспортная задача) как специальная задача линейного программирования 7

1.4 Этапы решения  транспортной задачи 8

1.4.1 Нахождение  начального плана 8

1.4.2 Улучшение  начального плана и нахождение  оптимального решения 9

2 Задача об оптимальном плане перевозок (Транспортная задача) 10

2.1 Решение задачи 1 10

2.2 Решение задачи 2 21

2.3 Решение  задачи 3 29

Заключение 35

Список используемых источников 36

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

Такие задачи довольно часто  встречаются на практике, например при решении проблем, связанных  с распределением ресурсов, планированием  производства, организацией работы транспорта и т.д. Это и естественно, так  как во многих задачах практики «расходы»  и «доходы» линейно зависят от количества закупленных или утилизированных  средств (например, суммарная стоимость  партии товаров линейно зависит  от количества закупленных единиц; оплата перевозок производится пропорционально  весам перевозимых грузов и т.д.).

Разумеется, нельзя считать, что все  встречающиеся на практике типы зависимостей линейны; можно ограничиться более  скромным утверждением, что линейные (и близкие к линейным) зависимости  встречаются часто, а это уже  много значит.

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

алгоритмах линейного  программирования (учитывая их компьютерную эффективность) базируются оптимизационные алгоритмы для других, более сложных типов моделей и задач исследования операций включая целочисленное, нелинейное и стохастическое

программирование.

Целью курсового проекта  является углубленное изучение раздела «Линейное программирование», а, конкретно, задача об оптимальном плане перевозки грузов (Транспортная задача), анализ литературы по заданной теме, выполнение практической части проекта  в виде подробного решения задач.

 

1 Линейное программирование

1.1 Основные понятия линейного программирования

Линейное программирование – наука о методах исследования и  
отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения. Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений.

Математическое выражение  целевой функции и ее ограничений называется математической моделью экономической задачи.

Допустимым решением (планом) задачи линейного программирования называется вектор ,удовлетворяющий  системе ограничений.

Множество допустимых решений  образует область допустимых решений (ОДР).

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

Математическая модель – это система математических соотношений приближенных в абстрактной форме, описывающих реальный объект или явление. Математическая модель задачи линейного программирования может быть канонической и неканонической.

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

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

 

 

1.2 Общая задача линейного программирования

В общем виде, задача линейного  программирования записывается  
следующим образом:

 (1)

                                       

(2)

 

  

где x – управляющая переменная,

 F – целевая функция,

a, b, c, i, j – параметры, ,

Решить задачу линейного  программирования – это значит найти  значения управляющих переменных, удовлетворяющих  ограничениям, при которых целевая  функция принимает максимальное или минимальное значение. В зависимости  от вида целевой функции и ограничений, можно выделить следующие типы задач линейного программирования:

1. Общая задача линейного программирования;
2. Транспортная задача;
3. Задача о назначениях.

 

1.3 Задача об  оптимальном плане перевозок  грузов (транспортная задача) как  специальная задача линейного  программирования

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

Пусть, имеется m пунктов отправления A₁,A₂,…,A_m, имеющих a₁,a₂,…,a_m единиц груза и n пунктов назначения B₁,B₂,…,B_n, подавших заявки на b₁,b₂,…,b_n единиц груза, соответственно. Известны стоимости перевозки C_ij, , от каждого пункта отправления до каждого пункта назначения (тарифы). Требуется составить план перевозок, позволяющий выполнить заказы и имеющий минимальную стоимость.

Транспортная задача решается в два этапа:

1. Нахождение начального плана;
2. Улучшение начального плана и нахождение оптимального решения.

 

1.4 Этапы решения транспортной задачи

1.4.1 Нахождение начального плана

Алгоритм решения:

1. Составить транспортную таблицу вида:

Таблица 1- Транспортная таблица для решения транспортной задачи

Потребитель Поставщик		B1	B2	…	Bn
		b1	b2	…	bn
A1	a1	C1,1	C1,2	…	C1,n
A2	a2	C2,1	C2,2	…	C2,n
…	…	…	…	…	…
Am	am	Cm,1	Cm,2	…	Cm,n

2. Выбрать клетку таблицы, которой соответствует минимальное значение тарифа;
3. В выбранную клетку поместить максимально возможное число единиц продукции, разрешенной ограничениями на спрос и предложения;
4. Если предложения исчерпано, то вычеркнуть соответствующую строку, иначе столбец.
5. Если не все клетки таблицы заполнены, то перейти на шаг 2.

 

1.4.2 Улучшение начального плана и нахождение оптимального решения

Алгоритм решения:

1. Получить начальный план перевозок;
2. Общее число занятых клеток должно быть равно m+n-1, иначе формально считать некоторые клетки заполненными;
3. Определить потенциалы производителей и потребителей. Для этого, составить систему уравнений для всех заполненных клеток таблицы по формуле:

                                                             (3)

Решить полученную систему.

4. Определить сумму потенциалов для свободных клеток по формуле:

                                                          (4)

5. Проверить план на оптимальность. Для этого, найти разность потенциалов по формуле: