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

Автор: Пользователь скрыл имя, 17 Января 2013 в 21:49, курсовая работа

Описание работы

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

Содержание

Введение 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 файл

Курсовой проект.docx

— 7.38 Мб (Скачать)

                                                        (5)

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

    1. Выбрать клетку, для которой максимальна. Построить цикл, начинающийся и заканчивающийся в выбранной клетке, содержащий в качестве вершин заполненные клетки таблицы и состоящий из горизонтальных и вертикальных отрезков. В исходной клетке поставить знак «+», в остальных – чередовать знаки «-» и «+».
    2. Выбрать клетку со знаком «-» и минимальным числом единиц продукции. Это число прибавляют к значениям, стоящим в клетках со знаком «+» и отнимают от значений, стоящих в клетках со знаком «-». Получится новая транспортная таблица, перейти на шаг 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), а за переменную xij – количество поставленной продукции.

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

 
 

 

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

x11 + x12 + x13 + x14=400;


x21 + x22 + x23 + x24=300;

x31 + x32 + x33 + x34=200;

x11 + x21 + x31=150;

x12 + x22 + x32=250;

x13 + x23 + x33 = 150;

x14 + x24 + x34=350; 

Запишем начальный план перевозок. Для удобства, обозначим за B1, B2, B3, B4 магазины, а за A1, A2, A3 склады.

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

Потребитель

Поставщик

Склады

B1

B2

B3

B4

150

250

150

350

A1

400

6     -

4   250

9     -

5    150

A2

300

150

7     -

8     -

6   150

A3

200

9      -

4    -

6   150

7     50


U1=0;


V2=4;

V4=5;

U2=1;

V1=4;

U3=2;

V3=4

 

U1 + V2 = 4;


U1 + V4 = 5;

U2 + V1 = 5;

U2 + V4 = 6;

U3 + V3 = 6;

U3 + V4 = 7;

 

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


 

 

                                    =>

 

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

С111 = U1 + V1 = 0 + 4 = 4;

C113 = U1 + V3 = 0 + 4 = 4;

C122 = U2 + V2 = 1 + 4 = 5;

C123 = U2 + V3 = 1 + 4 = 5;

C131 = U3 + V1 = 2 + 4 = 6;

C132 = U3 + V2 = 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        -


U1 + V2 = 4;


U1 + V4 = 5;

U2 + V1 = 5;

U2 + V4 = 6;

U3 + V2 = 4;

U3 + V3 = 6;

 

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


U1 = 0;


V2 = 4;

V4 = 5;

U2 = 1;

V1 = 4;

U3 = 0;

V3 = 6;


 

                            =>

                                              

 

 

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

С211 = U1 + V1 = 4;

C213 = U1 + V3 = 6;

C222 = U2 + V2 = 5;

C223 = U2 + V3 = 7;

C231 = U3 + V1 = 4;

C234 = U3 + V4 = 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;
    • Нажать на кнопку fx. После этого, появилось диалоговое окно Мастера функций:
    • В окне Категория выбрать «Математические»;
    • В окне Функции выбрать СУММПРОИЗВ;
    • Нажать ОК.
    • В появившемся окне «Аргументы функции» (рисунок 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 – Найденное решение задачи

Информация о работе Закрытая транспортная задача