Оптимальное управление в экономике. Матвейкин В.Г - 18 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

miax
i
n
j
ij
,1,
1
==
∑
=
; (3.7)
njbx
j
m
i
ij
,1,
1
==
∑
=
; (3.8)
njmix
ij
,1,,1,0 ==≥ . (3.9)
Таким образом, среди множества решений системы ограничений (3.7)–(3.8) требуется найти такое неотри-
цательное решение, которое минимизирует целевую функцию (3.6). Полученная задача является задачей ли-
нейного программирования. Решение ТЗ проводится с помощью общего приема последовательного улучшения
плана, который реализован в симплексном методе.
В общем случае транспортная задача решается в три этапа:
1. Определение исходного опорного плана.
2. Оценка этого плана.
3. Переход к следующему плану путём однократной замены одной из базисных переменных на свобод-
ную.
Теорема. Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы в пунктах от-
правления были равны потребностям в грузе в пунктах назначения, т.е. выполнялось равенство
∑∑
==
=
n
j
j
m
i
i
ba
11
. (3.10)
Если условие (3.10) выполнено, то модель ТЗ называется закрытой (сбалансированной). Задача с отсутст-
вием баланса между ресурсами и потребностями называется открытой
≠
∑∑
==
n
j
j
m
i
i
ba
11
.
1. Если
∑∑
==
>
n
j
j
m
i
i
ba
11
, то в математическую модель вводится фиктивный (п + 1)-й потребитель B
n+1
, для
которого потребность равна разности между суммарной мощностью поставщиков и фактическим спросом по-
требителей, т.е.
∑∑
==
+
−=
n
j
j
m
i
in
bab
11
1
. Все тарифы на доставку груза с фиктивными потребностями считают рав-
ными нулю, т.е.
.1,0,
1,
m=i=c
+ni
Поэтому для новой задачи значение целевой функции не изменится. Иными
словами, фиктивный потребитель не нарушит совместности системы ограничений. В транспортной таблице
задачи предусматривается дополнительный столбец.
2. Если же
∑∑
==
<
n
j
j
m
i
i
ba
11
, то вводится фиктивный (т + 1)-й поставщик A
m+1
. Для этого в транспортную
таблицу добавляется одна строка, запас груза для которой записывают равным
∑∑
==
+
−=
m
i
i
n
j
jm
aba
11
1
, а стоимости
перевозок полагают равными нулю:
.1,0,
1,
n=i=c
+mi
Поэтому в данном случае значение целевой функции не
изменится, а система ограничений останется совместной.
Приведем алгоритм решения транспортной задачи методом потенциалов:
1. Сравнивают общий запас груза с суммарным спросом и в случае нарушения баланса приводят задачу к
закрытой модели.
2. Условие задачи записывают в форме транспортной таблицы.
3. Строят начальный опорный план перевозок.
4. Проверяют условие для базисных клеток (их должно быть m+п-1). Если это условие не выполняется, то
в одну из свободных клеток (как правило, в клетку с наименьшим тарифом) вписывают число 0, и такая клетка
считается базисной. Однако число 0 записывают лишь в те свободные клетки, которые не образуют циклов с
ранее занятыми клетками.
5. Вычисляют потенциалы
. и
ji
vu
Каждому поставщику (каждой строке) ставят в соответствие некоторое
число ,
i
u называемое потенциалом поставщика )1,( m=iA
i
, и записывают справа от таблицы, а каждому по-

Страницы