Применение метода двойного предпочтения и метода потенциалов для решения транспортной задачи в линейном программировании
Введение
В 1930 г. впервые прозвучала постановка задачи линейного программирования
в работах советского экономиста А.Н. Толстого, имеющая вид предложения по
составлению такого плана перевозки груза между пунктами, чтобы общий пробег
транспорта был наименьшим; основы математического аппарата для решения
экономических задач линейного программирования были созданы в 1939 г.
академиком Л.В. Канторовичем и его учениками.
В настоящее время транспортная задача линейного программирования широко
применяется как в теоретических разработках, так и в практике планирования
различных экономических процессов. Особо важное значение она имеет при решении
вопросов рационализации поставок важнейших видов промышленной и
сельскохозяйственной продукции, а также оптимального планирования грузопотоков
и работы различных видов транспорта.
Также транспортная задача применяется при решении экономических задач,
которые по своему характеру не имеют ничего общего с транспортировкой груза. К
задачам такого типа относят:
· Увеличение производительности автомобильного транспорта за
счет минимизации порожнего пробега;
· Оптимальное закрепление за станками операций по обработке
деталей;
· Оптимальное назначения, или проблема выбора;
· Задачи размещения с учетом транспортных и производственных затрат.
Как и для других задач линейного программирования, итерационный процесс
по отыскании. Оптимального плана транспортной задачи начинают с нахождения
опорного плана, найти который можно с помощью следующих методов:
· Метод северо-западного угла;
· Метод минимальной стоимости;
· Метод двойного предпочтения;
А оптимальный план находится с помощью следующих методов:
· Метод потенциалов;
· Дельта-метод решения транспортной задачи;
В данной курсовой работе используется для нахождения опорного плана
используется метод двойного предпочтения. Для определения оптимального плана -
метод потенциалов.
оптимальный план
минимизация перевозка
1. ПОСТАНОВКА ЗАДАЧИ
Нефтеперерабатывающий завод получает 4 вида полуфабрикатов: 200 тыс.
литров алкилата, 350 тыс. литров бензина прямой перегонки, 250 тыс. литров
крекинг бензина, 100 тыс. литров изопентана.
В результате смешивания этих 4-ех компонентов в разных пропорциях
образуется 3 сорта авиационного бензина:
Бензин А-2:3:5:2
Бензин В-3:1:2:1
Бензин С-2:2:1:3
Стоимость 1 тыс. литров указанных сортов бензина характеризуется числами:
А-120 руб. В-100руб, С-150руб.
Таблица 1
Виды полуфабрикатов
|
Пропорциональное содержание
полуфабрикатов
|
Ограничения полуфабрикатов
в бензине, тыс.л.
|
Марка бензина
|
А
|
В
|
С
|
|
Алкилат
|
2
|
3
|
2
|
100
|
Крединг-бензин
|
3
|
1
|
2
|
125
|
Бензин прямой перегонки
|
5
|
2
|
1
|
150
|
Изопентон
|
2
|
1
|
3
|
50
|
Стоимость 1 тыс.л. Бензина
(руб.)
|
120
|
100
|
150
|
|
Определить план смешивания компонентов, при котором будет достигнута
максимальная стоимость всей продукции.
Задачу решить симплексным методом, используя язык программирования Turbo C и реализовать на ПЭВМ IBM PC 486
2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ
Математическая модель в общем виде:
при ограничениях
Вводятся обозначения для искомой задачи:
m -
вид полуфабрикатов,
n -
сорта бензина,
ai - пропорциональное содержание полуфабрикатов в бензине,
bj - ограничения полуфабрикатов в бензине, тыс.л.
Сij - стоимость бензина,
xij - объем выпуска бензина,
Z -
минимальная стоимость всей продукции.
Математическая модель данной ЗЛП:
при
ограничениях:
3. МЕТОД РЕАЛИЗАЦИИ МОДЕЛИ
Поставлена задача линейного программирования. Найти максимальное
значение функции
Z=C1X1+C2X2+...+CnXn
при ограничениях
a11x1+a12x2+...+a1nxn=b1
a21x1+a22x2+...+a2nxn=b2
............................................x1+am2x2+amnxn=bm≥0(j=1,2,...n)
bi≥0(i=1,2,...m)
Предполагается, что система ограничений задачи содержит m единичных векторов, причем без
ограничения общности можно положить, что единичными являются первые m векторов.
Z=C1X1+C2X2+...+CnXn
при ограничениях
x1+a1,m+1 xm+1+...+a1nxn=b1+a2,m+1 xm+1+...+a2nxn=b2
.....................................................+am,m+1+xm+1+...+amnxn=bm≥0(j=1,2,...n)
Алгоритм симплексного метода представляет собой способ целенаправленного
перебора планов, чтобы значения линейной формы в задачах на минимум уменьшалось
при переходе от одного опорного плана к другому, число шагов для достижения
этой цели m≤k≤2m, где
m-число уравнений или размеренность
базиса.
Заполняется исходная таблица. После чего производится вычисления в
последовательности:
Подсчитывается Zj-Cj и определяется, не является ли
рассматриваемый план оптимальным, т.е. не выполняется ли для всех xj условие: Zj-Cj≤0
Если для некоторого значение Zj -Cj>0, то выбирается вектор, который
может быть введен в базис. Для этого разыскивается какое-нибудь, для которого max(Zj-Cj)=Zk-Ck>0, тогда Pk
вводится в базис.
Выбирается вектор, который подлежит исключению из базиса. Это вектор для
которого: для всех xik>0, тогда Pi -исключается из базиса.
Если все, то линейная форма неограниченна снизу.
После выделения направляющей строки и направляющего столбца, таблица
преобразуется по формуле полного исключения.
В результате каждой итерации образуется новый опорный план. В конце
концов, либо придем к оптимальному плану, либо убедимся в неограниченности
линейной формы задачи.
Вычисления сводятся в табл.2
Таблица №2
i
|
Б
|
СБ
|
Ро
|
С1
|
С2
|
…
|
С1
|
…
|
Сm
|
Cm+1
|
...
|
Cj
|
...
|
Ck
|
...
|
Cn
|
|
|
|
|
P1
|
P1
|
...
|
P1
|
...
|
Pm
|
Pm+1
|
...
|
Pj
|
...
|
Pk
|
...
|
Pn
|
1
|
P1
|
С1
|
X1
|
1
|
0
|
...
|
0
|
...
|
0
|
X1
|
...
|
|
...
|
|
...
|
X1n
|
2
|
P2
|
С2
|
X2
|
0
|
1
|
...
|
0
|
...
|
0
|
|
...
|
|
...
|
|
...
|
X2n
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
|
...
|
|
...
|
...
|
1
|
P1
|
С1
|
X1
|
0
|
0
|
...
|
1
|
...
|
0
|
|
...
|
|
...
|
|
...
|
X1n
|
...
|
...
|
...
|
...
|
…
|
...
|
...
|
|
...
|
...
|
...
|
...
|
|
...
|
|
...
|
|
m
|
Pm
|
Сm
|
Xm
|
0
|
0
|
...
|
0
|
...
|
1
|
|
...
|
|
...
|
|
...
|
Xmn
|
m+1
|
|
|
Z0
|
0
|
0
|
...
|
0
|
...
|
0
|
|
...
|
|
...
|
|
...
|
|
. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ
.1 Вводятся А,В,С
.2 Заполняется симплексная таблица
.3 Вычисляется базис
.4 Находится опорный план и Z0
.5 Проверяется условие в (m+1)-
строки Zj-Cj<=0 на min
.6 Если условие выполняется, то выполняется переход на пункт 4.10
.7 Выбирается вектор Pk по max(Zj-Cj)=Zk-Ck>0
.8 Выбирается вектор Pl,
подлежащий исключению из базиса для которого: для всех xik>0
.9 Таблица преобразуется продолжением полного исключения и переход на
пункт 4.4
.10 Печать Xopt и Zopt
. ВЫЧИСЛИТЕЛЬНАЯ СХЕМА
Находится первоначальный опорный план методом двойного предпочтения.
Таблица 4
10 0
|
16 0
|
3 14
|
8 0
|
15 0
|
14
|
3 0
|
14 0
|
12 0
|
9 0
|
1 25
|
25
|
2 40
|
20 16
|
4 0
|
11 0
|
5 0
|
56
|
7 0
|
17 24
|
13 6
|
8 10
|
15 5
|
45
|
40
|
40
|
20
|
10
|
30
|
140
|
.
Решение
данной задачи осуществляется методом потенциалов.
Таблица
5
Шаг 1
|
Строки
|
Ui
|
Столбцы
|
ai
|
|
|
1
|
2
|
3
|
4
|
5
|
|
|
|
Vj
|
|
|
|
3
|
7
|
-2
|
5
|
-11
|
|
1
|
0
|
10 0
|
16 0
|
3 14
|
8 0
|
15 0
|
14
|
2
|
10
|
3 0
|
14 0
|
12 0
|
9 0
|
1 25
|
25
|
3
|
13
|
2 40
|
20 11
|
4 0
|
11 0
|
5 5
|
56
|
4
|
-4
|
7 0
|
17 29
|
13 6
|
8 10
|
15 0
|
45
|
bj
|
40
|
40
|
20
|
10
|
30
|
140
|
.
Таблица
6
Шаг 2
|
Строки
|
Ui
|
Столбцы
|
ai
|
|
|
1
|
2
|
3
|
4
|
5
|
|
|
|
Vj
|
|
|
|
-11
|
7
|
3
|
-2
|
-8
|
|
1
|
0
|
10 0
|
16 0
|
8 0
|
15 0
|
14
|
2
|
9
|
3 0
|
14 0
|
12 0
|
9 0
|
1 25
|
25
|
3
|
13
|
2 40
|
20 5
|
4 6
|
11 0
|
5 5
|
56
|
4
|
10
|
7 0
|
17 35
|
13 0
|
8 10
|
15 0
|
45
|
bj
|
40
|
40
|
20
|
10
|
30
|
140
|
.
Таблица
7
Шаг 3
|
Строки
|
Ui
|
Столбцы
|
ai
|
|
|
1
|
2
|
3
|
4
|
5
|
|
|
|
Vj
|
|
|
|
1
|
19
|
3
|
10
|
4
|
|
1
|
0
|
10 0
|
16 5
|
3 9
|
8 0
|
15 0
|
14
|
2
|
-3
|
3 0
|
14 0
|
12 0
|
9 0
|
1 25
|
25
|
3
|
1
|
2 40
|
20 0
|
4 11
|
11 0
|
5 5
|
56
|
4
|
-2
|
7 0
|
17 35
|
13 0
|
8 10
|
15 0
|
45
|
bj
|
40
|
40
|
20
|
10
|
30
|
140
|
Так
как , то
получается оптимальный план на третьем шаге.
.
6. БЛОК-СХЕМА
7. ПРОГРАММА
Данная задача линейного программирования реализована посредством MS Excel. Для этого используется процедура Excel «Поиск решения»,
где:
· Установить целевую ячейку - служит для указания целевой
ячейки, значение которой необходимо максимизировать, минимизировать или
установить равным заданному числу. Эта ячейка должна содержать формулу:
o Равной - служит для выбора варианта оптимизации значения
целевой ячейки (максимизация, минимизация или подбор заданного значения числа).
Чтобы установить число, необходимо ввести его в поле;
o Изменяя ячейки - служит для указания ячеек, значения которых
изменяются в процессе поиска решения до тех пор, пока не будут выполнены
наложенные ограничения и условие оптимизации значения ячейки, указанной в поле
Установить целевую ячейку;
o Предположить - используется для автоматического поиска ячеек,
влияющих на формулу, ссылка на которую дана в поле Установить целевую ячейку.
Результат поиска отображается в поле Изменяя ячейки;
o Ограничение - служит для отображения списка граничных условий
поставленной задачи;
o Добавить - используется для отображения диалогового окна
Добавить ограничение;
o Изменить - применяется для отображения диалогового окна
Изменить ограничение;
o Удалить - служит для снятия указанного ограничения;
o Выполнить - используется для запуска поиска решения
поставленной задачи;
o Закрыть - служит для выхода из окна диалога без запуска
поиска решения поставленной задачи. При этом сохраняются установки, сделанные в
окнах диалога, появлявшихся после нажатий на кнопки Параметры, Добавить,
Изменить или Удалить;
o Параметры - применяется для отображения диалогового окна
Параметры поиска решения, в котором можно загрузить или сохранить
оптимизируемую модель и указать предусмотренные варианты поиска решения;
o Восстановить - служит для очистки полей окна диалога и
восстановления значений параметров по умолчанию.
8. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ
8.1 Включить ЭВМ.
.2 Запустить прикладную программу MS Excel.
.3 Открыть новый рабочий лист (Вставка/Лист).
.4 В ячейки диапазона А1:Е4 разместить таблицу стоимости перевозок.
.5 В ячейки диапазона А10:Е10 ввести следующие формулы:
А10 = СУММ(А6:А9)
В10 = СУММ(В6:В9)
С10 = СУММ(С6:С9)
D10 =
СУММ(D6:D9)
Е10 = СУММ(Е6:Е9)
.6 В ячейки диапазона F6:F10 ввести следующие формулы:
F6 =
СУММ(А6: E6)
F7 =
СУММ(А7: E7)
F8 =
СУММ(А8: E8)
F9 =
СУММ(А9: E9)
.7 В ячейки диапазона G6:G9 ввести значения соответствующие
запасам на складах.
.8 В ячейки диапазона А11:Е11 ввести значения соответствующие
потребностям на птредприятиях.
.9 В ячейку F10
ввести формулу целевой функции = СУММПРОИЗВ(A1:E4;A6:E9).
.10 Выбрать на панели инструментов Данные/Анализ/Поиск решения.
.11 Установить целевую ячейку содержащую оптимизируемое значение (F10).
.12 Установить переключатель Равной минимальному значению, т.к. в
поставленной задаче требуется вычислить минимальный объем затрат.
.13 В поле Изменяя ячейки задать диапазон подбираемых параметров
($A$6:$E$9).
.14 Определить набор ограничений. Для этого щелкнуть на кнопке
Добавить и ввести следующие ограничения $A$10:$E$10 =
$A$11:$E$11, $A$6:$E$9 = целое, $A$6:$E$9
>= 0, $F$6:$F$9 = $G$6:$G$9.
.15 Щелкнуть на кнопке Выполнить.
.16 В диалоговом окне Результаты поиска решения установить
переключатель в положение Сохранить найденное решение.
.17 Полученные результаты вывести на печать.
9. РЕЗУЛЬТАТ СЧЕТА ПО ПРОГРАММЕ
Результат вычислений:
Оптимальный план:
Xопт =
|
0 0 40 0
|
5 0 0 35
|
9 0 11 0
|
0 0 0 10
|
0 25 5 0
|
14 25 56 45
|
|
40
|
40
|
20
|
10
|
30
|
|
Целевая функция: Zопт
= 956.
. ЭКОНОМИЧЕСКОЕ ОБЪЯСНЕНИЕ РЕЗУЛЬТАТОВ
В результате решения транспортной задачи по
минимизации затрат на перевозку товаров с четырех складов на пять предприятий
был получен оптимальный план:
Xопт =
|
0 0 40 0
|
5 0 0 35
|
9 0 11 0
|
0 0 0 10
|
0 25 5 0
|
14 25 56 45
|
|
40
|
40
|
20
|
10
|
30
|
|
Чтобы затраты на перевозку товара с четырех складов на
пять предприятий были минимальны, необходимо таким образом спланировать
перевозки:
На первое предприятие 40 т товара с четвертого склада.
На второе предприятие 5 т товара с первого склада и 35
т с четвертого склада.
На третье предприятие 9 т товара с первого склада и 11
т с третьего склада.
На четвертое предприятие 10 т товара с четвертого
склада.
На пятое предприятие 25 т товара со второго склада и 5
т с третьего склада.
При таком плане стоимость перевозок составляет 956
рублей.
В результате оптимизации плана получена экономия Zо - Zопт =
= 1108 - 56 = 152 рубля.
ЗАКЛЮЧЕНИЕ
В результате выполнения курсовой работы закрепила знания по
математическим и программным средствам моделирования при решении конкретной
производственной программы.
При выполнении курсовой работы закрепила навыки нахождения оптимального
плана транспортной задачи с помощью метода потенциалов.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
·
Ю.Н. Кузнецов,
В.И. Кузубов, А.Б. Волощенко «Математическое программирование» М. «Высшая
школа», 1980г.
·
С.А. Соколицин
«Применение математических методов в экономике и организации
машиностроительного производства» Л, «Машиностроение», 1970г.
·
ЕСПД Схема
алгоритмов и программ ГОСТ 19.002 - 80, ГОСТ 19.003-80, издательства
стандартов, 1980г.
·
Методические
указания к курсовой работе по дисциплине «Математические методы», Таганрог,
ТАК, 2010г.