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

                                                        (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 – Найденное решение задачи