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

Изм.

Лист

№ докум.

Подпись

Дата

Лист

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. Проверить план на оптимальность. Для этого, найти разность потенциалов по формуле:

                                                        (5)

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

6. Выбрать клетку, для которой максимальна. Построить цикл, начинающийся и заканчивающийся в выбранной клетке, содержащий в качестве вершин заполненные клетки таблицы и состоящий из горизонтальных и вертикальных отрезков. В исходной клетке поставить знак «+», в остальных – чередовать знаки «-» и «+».
7. Выбрать клетку со знаком «-» и минимальным числом единиц продукции. Это число прибавляют к значениям, стоящим в клетках со знаком «+» и отнимают от значений, стоящих в клетках со знаком «-». Получится новая транспортная таблица, перейти на шаг 3.

 

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

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

Московский филиал фирмы  “The Coca-Cola Company”, выпускающей газированные напитки, складируемые в разных местах, должен поставить продукцию в четыре московских супермаркета: «Рамстор-1», «Рамстор-2», «Седьмой континент», «Арбатский». Каждая упаковка содержит 6 ёмкостей по 2 литра. Тарифы на доставку товара, объемы запасов и заказы на продукцию приведены в таблице 2.

Таблица 2 – Тарифы на доставку товара, объемы запасов и заказы на продукцию для задачи 1

Склады	Супермаркеты				Запасы
	«Рамстор-1»	«Рамстор-2»	«Седьмой континент»	«Арбатский»
Coca-Cola	6	4	9	5	400
Sprite	5	7	8	6	300
Fanta	9	4	6	7	200
Заказы, уп.	150	250	150	350

Требуется составить план перевозок, позволяющий выполнить  весь объем заказов и имеющий  минимальную стоимость.

Обозначим за переменную i – номер склада (от 1 до 3), за переменную j – номер супермаркета (от 1 до 4), а за переменную x_ij – количество поставленной продукции.

Составим математическую модель. Для этого, обозначим за x_ij количество доставленной поставщиком продукции для магазина. Итак, математическая модель будет иметь следующий вид:

 
 

 

Итак,  мы имеем линейную функцию. Теперь, необходимо записать ограничивающие условия по всем складам  и супермаркетам (ОДР).

x₁₁ + x₁₂ + x₁₃ + x₁₄=400;

x₂₁ + x₂₂ + x₂₃ + x₂₄=300;

x₃₁ + x₃₂ + x₃₃ + x₃₄=200;

x₁₁ + x₂₁ + x₃₁=150;

x₁₂ + x₂₂ + x₃₂=250;

x₁₃ + x₂₃ + x₃₃ = 150;

x₁₄ + x₂₄ + x₃₄=350; 

Запишем начальный план перевозок. Для удобства, обозначим за B₁, B₂, B₃, B₄ магазины, а за A₁, A₂, A₃ склады.

Таблица 3 – Начальный план перевозок продукции для решения задачи 1

Потребитель Поставщик		Склады
		B1	B2	B3	B4
		150	250	150	350
A1	400	6     -	4   250	9     -	5    150
A2	300	5  150	7     -	8     -	6   150
A3	200	9      -	4    -	6   150	7     50

U₁=0;

V₂=4;

V₄=5;

U₂=1;

V₁=4;

U₃=2;

V3=4

 

U₁ + V₂ = 4;

U₁ + V₄ = 5;

U₂ + V₁ = 5;

U₂ + V₄ = 6;

U₃ + V₃ = 6;

U₃ + V₄ = 7;

 

Определим потенциалы производителей и потребителей:

 

 

                                    =>

 

Теперь, определим сумму  потенциалов для всех незаполненных  клеток таблицы:

С1₁₁ = U₁ + V₁ = 0 + 4 = 4;

C1₁₃ = U₁ + V₃ = 0 + 4 = 4;

C1₂₂ = U₂ + V₂ = 1 + 4 = 5;

C1₂₃ = U₂ + V₃ = 1 + 4 = 5;

C1₃₁ = U₃ + V₁ = 2 + 4 = 6;

C1₃₂ = U₃ + V₂ = 2 + 4 = 6;

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

;

;

;

;

;

;

Не все разности потенциалов  являются отрицательными или нулевыми, следовательно, начальный план перевозок  не является оптимальным.  Перейдем в клетку таблицы, для которой  разность потенциалов положительна. В нашем случае, это клетка располагается на пересечении третьей строки и второго столбца. Поставим в исходной клетке таблицы знак «+» и, чередуя знаки в клетках, построим цикл, содержащий в качестве вершин заполненные клетки таблицы и состоящий из горизонтальных и вертикальных отрезков, который начнется и закончится в исходной точке:

Таблица 4 – Построение цикла  для получения новой транспортной таблицы

Потребитель Поставщик		Склады
		B1	B2	B3	B4
		150	250	150	350
A1	400	6       -	4   250 -	9       -	5     150   +
A2	300	5    150	7     -	8      -	6     150
A3	200	9      -	4        +	6     150	7       50    -

Выберем клетку со знаком «-»  и минимальным числом единиц продукции. В нашем случае, это число 50. Отнимем  это число из значений вершин цикла  со знаком «-» и прибавим его ко всем значениям вершин цикла со знаком «+». Составим новую транспортную таблицу:

 

Таблица 5 – Вторая транспортная таблица для решения задачи 1

Потребитель Поставщик		Склады
		B1	B2	B3	B4
		150	250	150	350
A1	400	6           -	4      200	9       -	5       200
A2	300	5         150	7        -	8      -	6      150
A3	200	9         -	4      50	6     150	7        -

U₁ + V₂ = 4;

U₁ + V₄ = 5;

U₂ + V₁ = 5;

U₂ + V₄ = 6;

U₃ + V₂ = 4;

U₃ + V₃ = 6;

 

Аналогично предыдущему  плану перевозок, определим потенциалы производителей и потребителей:

U₁ = 0;

V₂ = 4;

V₄ = 5;

U₂ = 1;

V₁ = 4;

U₃ = 0;

V₃ = 6;

 

                            =>

                                              

 

 

Аналогично предыдущему  плану перевозок, определим суммы  потенциалов:

С2₁₁ = U₁ + V₁ = 4;

C2₁₃ = U₁ + V₃ = 6;

C2₂₂ = U₂ + V₂ = 5;

C2₂₃ = U₂ + V₃ = 7;

C2₃₁ = U₃ + V₁ = 4;

C2₃₄ = U₃ + V₄ = 5;

Проверим план на оптимальность:

;

;

;

;

;

;

 

Данный план является оптимальным, т.к. все разности потенциалов отрицательны.

Теперь, вычислим целевую  функцию:

 

Ответ: Таким образом, оптимально перевозить грузы так:

Из А1 в B2 – 200 упаковок напитка;

Из А1 в B4 – 200 упаковок напитка;

Из А2 в B1 – 150 упаковок напитка;

Из А2 в B4– 150 упаковок напитка;

Из А3 в B2 – 50 упаковок напитка;

Из А3 в B3 – 150 упаковок напитка.

При этом, стоимость перевозки минимальна и составляет 4550 рублей.

 

 

 

Решение задачи 1 в программе Microsoft Office Excel:

Ввод условий задачи состоит  из ввода условий основных шагов:

1. Создание формы для ввода условий задачи.
2. Ввод исходных данных.
3. Ввод зависимостей из математической модели.
4. Назначение целевой функции
5. Ввод ограничений и граничных условий

Алгоритм ввода  данных для решения транспортной задачи:

• Для задачи 1, сделать форму для ввода условий задачи (рисунок 1)

Рисунок 1 – Условие задачи № 1

• Ввести исходные данные в форму (рисунок 1);
• Установить курсор в ячейку D14;
• Нажать на кнопку f_x. После этого, появилось диалоговое окно Мастера функций:
• В окне Категория выбрать «Математические»;
• В окне Функции выбрать СУММПРОИЗВ;
• Нажать ОК.

• В появившемся окне «Аргументы функции» (рисунок 2) в текстовое поле «Массив1»;

 

 

• Ввести C3:F5. После этого, в текстовое поле «Массив2» ввести С9:F11. Нажать «ОК»

Рисунок 2 – Функция СУММПРОИЗВ

• Установить курсор в ячейку С6. Нажать кнопку , а после этого, нажать клавишу Enter;
• Растянуть формулу вправо по ячейку F6 включительно;
• Установить курсор в ячейку B3. Нажать кнопку , выделить диапазон C3:F3 а после этого, нажать клавишу Enter;
• Растянуть формулу вниз по ячейку B5 включительно;
• Выбрать на ленте вкладку «Данные», а затем нажать на кнопку «Поиск решения». В появившемся диалоговом окне «Поиск решения», заполнить текстовое поле «Установить целевую ячейку» значение $D$14;
• Ввести направление целевой функции: к минимальному значению;
• В качестве изменяемых ячеек, установить диапазон С$3:F$5;
• Ввести ограничения – рисунок 3:

• Нажать на кнопку «Добавить». В появившемся диалоговом окне, в текстовом поле «Ссылка на ячейку», установить диапазон $B$3:$B$5;
• Из выпадающего списка выбрать знак «=»;
• В текстовом поле «Ограничение», установить диапазон «$B$9:$B$11»;
• Нажать клавишу «Добавить»;

 

 

• Проделать ту же операцию с диапазонами $C$6:$F$6 и $C$8:$F$8 и нажать кнопку «ОК».

Рисунок 3 – Добавление нового ограничения

• После этого, на экране появится окно «Поиск решения» с введенными ограничениями, представленными на рисунке 4:

Рисунок 4 – Диалоговое окно надстройки «Поиск решения»

• Нажать кнопку «Найти решение». Отобразится диалоговое окно «Результаты поиска». Нажать кнопку «ОК» (Рисунок 5)

 

 

 

 

 

 

Рисунок 5 – Результат

• В ячейках B3:B5, C6:F6 и D14 появится ответ (Рисунок 6)

Рисунок 6 – Найденное решение задачи