Материал: 5462
21
шлейфа), причем непосредственно между собой эти два кружка не соединяются и цепь получается незамкнутой.
Наличие в каждой цепи шлейфа дает возможность сбалансировать изменение поставок в столбцах реальных потребителей за счет поставок в столбце фиктивного потребителя. Для клетки (1,3) цепь имеет один шлейф
|
|
(1,2) - |
|
|
+ |
(1,3) |
|
|
|
|
|
||||
|
|
+ |
|
|
|
|
|
|
|
|
- |
+ (2,6) |
|||
|
|
(2,2) |
(2,3) |
|
|
||
5. Дельты |
|
|
|
|
|
|
|
Условимся через |
ij |
обозначать показатели, характеризующие размер |
|||||
|
|
|
|
|
|
|
|
изменения xij в соответствующей клетке, при перераспределении единицы
поставки в пустую клетку.
При записи поставки в клетку (1,3) не должен нарушиться баланс по строкам и столбцам цепи.
Для строк |
12 |
13 |
0; |
|
|
|
|||
|
|
|
0. |
|
|
22 |
23 |
26 |
|
|
|
Баланс по столбцу отличается от баланса по строке тем, что в нем участвуют λ. Если в (1,3) записать поставку, равную 1, это удовлетворит спрос на 20 единиц, а поставка единицы в клетку (2,3) удовлетворит спрос
только на 5 единиц. Таким образом, сумма изменений значений xij |
в этих |
|||||
клетках с учетом λ должна быть равна нулю: |
20 |
13 5 23 0 |
– для |
|||
столбца В3. Аналогично для столбца В2: 10 12 5 |
22 |
0 . |
|
|||
Окончательно система уравнений имеет вид: |
|
|
|
|
||
13 |
12 |
0 |
|
|
|
|
|
|
|
|
|
||
22 |
23 |
26 |
0 |
|
|
|
|
|
|
|
|||
20
10
13
12
5
5
23
22
0
0
Система содержит 4 линейно независимых уравнений и 5 неизвестных,
следовательно, имеет |
множество решений. Положим |
13 |
1. |
Во |
всех |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
случаях |
ij |
клетки, |
для которой |
построена |
цепь |
будем |
принимать |
||||
|
|
|
|
|
|
|
|
|
|
|
|
равной 1. Значения остальных ij : |
12 |
1; |
23 |
4 ; |
22 |
2 ; |
26 |
2 . |
|||
Эти значения показывают, на сколько изменится поставка в соответствующей клетке, если в (1,3) записать поставку, равную 1. Так 23 
4 означает, что поставка в клетку (2,3) уменьшится на 4. Таким
22
образом, при перераспределении по цепи поставки уменьшаются в тех
клетках, в которых |
0. |
ij
6. Гаммы Необходимо определить, в какой отрицательной вершине поставка
лимитирует величину поставки в клетку (1,3). Разделив величину поставки
в каждой отрицательной вершине на модуль соответствующей |
ij , |
устанавливаем величину возможной поставки в (1,3). |
|
Величина поставки в клетку, для которой построена цепь |
– |
|
min |
|
|
xij |
|
|
|
min |
10 |
, |
20 |
|
5. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
min |
|
|
|
|
|
|
|
1 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
ij |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7. Перераспределение поставок. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
Величина изменения поставки в вершине |
|
|
ij |
|
|
min |
ij |
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
1 |
|
5 |
5; |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13 |
1 |
5 |
|
5; |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
23 |
|
|
4 |
5 |
20; |
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
22 |
2 |
|
|
5 |
|
10; |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
26 |
2 |
|
|
5 |
|
10. |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Сложив теперь (с учетом знаков) показатели |
xij |
|
с соответствующими |
||||||||||||||||||||||||||||||||
показателями |
|
ij , получим новое распределение поставок: |
|
||||||||||||||||||||||||||||||||
|
60 |
|
|
175 |
|
|
400 |
|
100 |
|
|
100 |
|
|
|
|
В6 |
|
ui |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
1 |
5 |
1 |
10 |
4 |
|
|
20 |
5 |
|
15 |
|
2 |
20 |
|
0 |
1 |
|
|
||||||||||||||||
10 |
|
|
|
|
|
|
5 |
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
+ |
|
|
|
|
|
|
|
-1 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
10 |
2 |
1 |
|
5 |
|
|
5 |
2 |
|
10 |
|
4 |
4 |
|
0 |
1 |
|
|
||||||||||||||||
|
|
5 |
|
|
|
|
|
|
|
||||||||||||||||||||||||||
50 |
|
|
|
|
|
|
25 |
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
|
|
15 |
|
0 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
10 |
30 |
2 |
8 |
2 |
|
|
20 |
5 |
|
25 |
|
1 |
5 |
|
0 |
1 |
|
-3 |
||||||||||||||||
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
5 |
15 |
4 |
20 |
10 |
|
10 |
5 |
|
20 |
|
5 |
10 |
|
0 |
1 |
|
|
|||||||||||||||||
30 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
16 |
|
0 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
1 |
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
1 |
|
|
|
|
1 |
|
|
|
|
0 |
|
|
||||||
Vj |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
3 |
|
|
|
|
15 |
|
|
|
|
4 |
|
|
|
5 |
|
|
|
|
2 |
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
23
2-я итерация. Определяем потенциалы и характеристики. Наименьшая
отрицательная характеристика E |
2 20 |
1 |
1 |
7 . В цепи к этой |
|
||||
15 |
2 |
|
|
|
|
|
|
||
клетке два шлейфа, каждый из которых оканчивается кружком в столбце
фиктивного потребителя. Определяем |
ij |
из системы уравнений |
|
|
|
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
|
15 |
|
0, |
|
|
|
|
|
|
|
|
15 |
1 |
|
|
|
|
|
12 |
1; |
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
22 |
|
26 |
|
0, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
22 |
2; |
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
45 |
|
46 |
|
0, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
26 |
2; |
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
10 |
12 |
5 |
|
22 |
0, |
|
|
|
|
|
|
|
|
|
|
|
|
|
45 |
2; |
|
|
|
|
|
|
|
|||||||
20 |
15 |
10 |
45 |
|
0. |
|
|
|
|
|
|
|
|
|
|
46 |
2. |
|
|
|
|
|
|
|
||||||||||
|
|
min |
5 |
; |
15 |
|
; |
|
10 |
|
5. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
min |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
1 |
|
2 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
Определяем, |
на сколько изменятся поставки в цепи |
15 |
5 |
; |
12 |
5 |
; |
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
22 |
10 ; |
|
26 |
|
|
10; |
45 |
10 |
; |
46 |
|
10 . |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
60 |
|
|
|
|
175 |
400 |
|
100 |
|
|
100 |
|
|
В6 |
|
|
ui |
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
1 |
|
5 |
|
1 |
10 |
4 |
20 |
5 |
15 |
|
2 |
20 |
0 |
1 |
|
|
|
|
|
|
||||||||||||
10 |
|
|
|
|
|
|
|
|
0 |
|
|
5 |
|
|
|
|
|
|
5 |
|
|
|
|
|
-1 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
10 |
|
2 |
1 |
5 |
5 |
5 |
2 |
10 |
|
4 |
4 |
0 |
1 |
|
|
|
|
|
|
|||||||||||||
50 |
|
|
|
|
|
|
|
|
35 |
|
|
|
|
|
10 |
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
10 |
|
30 |
2 |
8 |
2 |
20 |
5 |
25 |
|
1 |
5 |
0 |
1 |
|
-3 |
|
|
|
|
|||||||||||||
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
5 |
|
15 |
4 |
20 |
10 |
10 |
5 |
20 |
|
5 |
10 |
0 |
1 |
|
|
|
|
|
|
|||||||||||||
30 |
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
26 |
|
|
0 |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Vj |
|
1 |
|
|
|
|
|
1 |
|
|
|
1 |
|
|
1 |
|
|
|
3 |
|
0 |
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
5 |
|
|
|
4 |
|
|
5 |
|
|
|
20 |
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
Все |
Еij 0 |
для |
свободных |
клеток. |
E42 |
0 . Оптимальный план не |
|
единственный. |
|
|
|
|
|
||
Zmin |
4 5 |
2 5 |
1 35 2 10 |
2 15 |
5 4 |
135. |
|
Замечание. В случае, если |
ij |
пропорциональны по всем строкам, задачу |
|||||
|
|
|
|
|
|
|
|
можно привести к обычной транспортной при помощи коэффициента
|
|
24 |
|
|
пропорциональности |
кi . |
Рассмотрим |
задачу |
выполнения |
производственной программы группой предприятий при полной загрузке производственных мощностей.
Пусть Ai |
– полезный |
(эффективный) фонд времени работы i-го |
|
предприятия |
(смен); B j |
– |
количество изделий j-го вида, подлежащее |
производству по плану; |
ij |
– производительность i-го предприятия при |
|
изготовлении единицы j-й продукции (изделий / смену); Сij – затраты на
изготовление единицы j-й продукции на i-м предприятии (руб./изделия); xij – количество изделий j-го вида, подлежащее изготовлению на i-м
предприятии по оптимальному плану.
Для сведения задачи к транспортной введем дополнительные показатели и обозначения.
Выберем предприятие, производительность которого будет служить в качестве эталона (обычно выбирают наиболее производительное предприятие) и установим для него коэффициент производительности ( кi ),
равный 1. На этой основе определим коэффициенты, производительности
для остальных предприятий ki 
(отношение производительности данного предприятия к производительности эталонного предприятия).
Спомощью коэффициента производительности ki 
найдем
приведенные фонды времени работы предприятий Ai 
ki 
Ai .
Экономический смысл приведенного фонда времени состоит в том, что каждая смена работы i-го предприятия равноценна смене работы предприятия любой другой группы, то есть производительность предприятий всех видов в одну смену приведенного фонда времени одинакова и равна производительности предприятия, взятого в качестве эталона. Количество изделий, подлежащих производству по плану, можно выразить как количество приведенного фонда времени, которое необходимо затратить для их производства. Для этого достаточно заданное количество изделий j-го вида по плану ( В j ) разделить на
производительность по этому виду изделий предприятия, взятого в качестве эталона. В результате получим количество приведенного фонда
времени ( В j ), необходимого для планового производства j-го вида изделий.
xij 
– количество приведенного фонда времени работы i-го предприятия,
расходуемого по оптимальному плану при производстве j-го вида изделий. В этом случае математическая модель задачи оптимального использования производственных мощностей имеет вид
25
|
|
|
|
|
|
|
|
|
xij |
B j |
, |
j |
|
1, n; |
|||
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
xij |
Ai |
, |
i |
1, m; |
||||
j |
|
|
|
|
|
|
|
|
z |
Cij |
|
xij |
|
|
|
min . |
|
i |
j |
|
|
|
|
|
|
|
Пример. Рассмотрим задачу оптимизации ассортиментной загрузки производственных мощностей при следующих исходных данных
Предприятие- |
Производительность предприятий |
Эффективный |
||||
изготовитель |
(изделий в смену) |
|
|
фонд рабочего |
||
|
А |
Б |
В |
Г |
Д |
времени (смен) |
1 |
4 |
8 |
2 |
14 |
6 |
350 |
2 |
2 |
4 |
1 |
7 |
3 |
700 |
3 |
10 |
20 |
5 |
35 |
15 |
580 |
4 |
6 |
12 |
3 |
21 |
9 |
740 |
План |
3000 |
5000 |
2500 |
3500 |
3000 |
|
производства |
|
|
|
|
|
|
|
|
|
||||
Предприятие- |
Затраты на изготовление одного |
|
||||
изготовитель |
|
|
изделия |
|
|
|
|
А |
Б |
В |
Г |
Д |
|
1 |
4 |
4 |
6 |
5 |
8 |
|
2 |
5 |
5 |
6 |
6 |
8 |
|
3 |
5 |
6 |
5 |
4 |
6 |
|
4 |
6 |
7 |
4 |
4 |
6 |
|
Необходимо определить оптимальное распределение производства изделий по отдельным предприятиям, обеспечивающее выполнение производственной программы при минимальных затратах.
Решение. Выбираем в качестве эталонного третье предприятие с наибольшей производительностью и принимаем его производительность за единицу ( к3 1). Определяем коэффициенты производительности для
остальных |
предприятий |
|
ki |
(отношение |
производительности этих |
|||||||||
предприятий к производительности 3 предприятия): |
||||||||||||||
k1 |
4 |
0,4 |
; k2 |
2 |
0,2 |
; |
k3 |
1; k4 |
6 |
|
0,6 . |
|||
|
|
|
|
|
|
|
||||||||
10 |
10 |
10 |
|
|||||||||||
|
|
|
|
|
|
|
|
|
||||||