Материал: 5462
16
оптимальный план закрепления складов за торговыми точками, обеспечивающий минимум затрат на перевозки.
9.Требуется организовать снабжение строительным песком, добываемым на трех карьерах, четырех строительных площадок. Минимизировать при этом общий пробег (т/км). Мощности карьеров составляют соответственно 142, 121, 97 т песка в сутки. Потребности в песке стройплощадок: 120; 34; 90; 76 т. Расстояния в км показаны в таблице
|
|
Стройка |
|
|
Карьер |
I |
II |
III |
IV |
|
|
|
|
|
I |
18 |
6 |
8 |
22 |
II |
21 |
20 |
10 |
13 |
III |
36 |
14 |
21 |
25 |
10.Четыре различных предприятия могут выпускать любой из четырех видов продукции. Производственные мощности предприятий
позволяют обеспечить выпуск продукции каждого вида в количествах 50; 70; 100; 30 тыс. шт., а плановое задание составляет
соответственно |
30; 80; 20; 100 тыс. шт. Матрица |
|||||
|
9 |
5 |
4 |
3 |
|
|
С Сij |
5 |
7 |
9 |
4 |
характеризует себестоимость единицы j-го |
|
6 |
4 |
8 |
6 |
|||
|
|
|||||
|
8 |
6 |
7 |
5 |
|
|
вида продукции при производстве его на i-м предприятии. Найти оптимальное распределение планового задания между предприятиями при условии минимальных суммарных затрат на производство.
17
Глава 2. Обобщенная транспортная задача (λ-задача)
λ-задача иначе называется обобщенной транспортной или распределительной задачей.
Постановка задачи. Требуется произвести ассортиментный набор продукции в количествах, удовлетворяющих спрос потребителей при минимизации суммарных затрат на изготовление продукции с учетом производственных мощностей изготовителей.
Пусть ai – производственная мощность |
|
|
i -го предприятия-изготовителя; |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
1, m |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|||||
b j |
– потребность в j -м виде продукции |
j |
1, n . |
|
|
|
||||||||||
Cij |
|
– издержки производства единицы |
|
|
|
j -го вида |
продукции |
i -м |
||||||||
изготовителем; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
ij |
|
– производительность |
i -го |
изготовителя |
(шт./час) |
по j -му |
виду |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
продукции. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Обозначим xij – искомое количество продукции |
j -го вида, изготовленное |
|||||||||||||||
на i -м предприятии. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Математическая модель задачи |
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
z |
Cij |
ij |
xij |
|
|
|
min ; |
|
(2.1) |
||||
|
|
|
j |
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
xij |
ai , |
i |
1, m ; |
|
|
(2.2) |
||||||
|
|
|
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
i |
ij xij |
b j , |
|
|
j 1, n ; |
|
(2.3) |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xij |
0 . |
|
|
|
|
|
|
|
|
(2.4) |
|
Условие (2.2) выражает требование, чтобы суммарный фонд времени, затраченный i -м предприятием на изготовление всех видов продукции, не превышал его возможностей.
Условие (2.3) означает, что должно быть изготовлено изделий не меньше планового задания b j , т.к. ij 
xij определяет количество j -х
изделий, изготовленных на i -м предприятии.
В зависимости от конкретного условия задачи может варьироваться конкретное содержание, а также размерность исходных величин ai ,bj ,ci , ij , что, в свою очередь, приведет к некоторой модификации
модели. Так, например, |
ij |
может выражать число единиц i -х ресурсов, |
||
|
|
|
|
|
затрачиваемых |
на единицу |
|
j -х потребностей. Тогда ограничение (2.2) |
|
заменится на |
xij / ij |
b j . |
Если же при этом Cij означает оценки |
|
|
i |
|
|
|
18
единицы j -го изделия в руб./шт., то изменится выражение для целевой функции:
z |
Cij / ij xij и т.д. |
i j |
|
Целевая функция z может |
максимизироваться, если Cij означают |
прибыль, стоимость или минимизироваться, если Cij означают затраты,
себестоимость и т.д.
При различных модификациях модель имеет сходство с транспортной задачей. Но наличие в одной из групп ограничений множителей ij (из-за
чего и возникло название -задачи) вызывает необходимость изменения алгоритма решения транспортной задачи.
Алгоритм решения -задачи рассмотрим на условном примере, в котором находится оптимальный вариант распределения производственной программы по группам оборудования.
Пример. Предположим, что имеется m 4 видов взаимозаменяемого оборудования, на котором обрабатываются n 5 видов изделий. Взаимозаменяемое оборудование на предприятии редко бывает однородным (различие по степени изношенности, конструктивным особенностям), что обусловливает различие в производительности оборудования и стоимости изделий из них. В задаче даны следующие величины:
ai – фонд времени i -го оборудования;
b j – задание по выпуску изделий j -го вида.
В левом верхнем углу каждой клетки Cij – затраты на производство единицы j -го вида изделия на i -м оборудовании в руб./час.
В правом верхнем углу клетки ij – производительность i -го оборудования при выпуске изделий j -го вида (шт./час).
Обозначим xij количество времени работы i -го оборудования при выпуске изделий j -го типа.
Модель задачи открытая, поэтому вводится столбец фиктивного потребителя. Спрос этого потребителя не указывается, так как он будет зависеть от конкретного распределения. Показатели Cij в столбце
фиктивного потребителя примем равными нулю, а коэффициенты |
ij =1. |
|||
1. Базисное распределение |
|
|||
Обозначим rij |
ij |
показатель, характеризующий, сколько |
единиц |
|
|
||||
Cij |
||||
|
|
|
||
продукции приходится на один рубль затрат.
19
|
|
|
|
|
|
|
5 1 |
10 |
5 |
3 |
10 |
|
|
|
|
|
|
|
|
|
|
rij |
|
|
15 |
5 |
1 |
5 |
1 . |
|
|
|
|
||
|
|
|
|
|
|
|
3 |
4 |
10 |
5 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
5 |
1 |
4 |
2 |
|
|
|
|
|
|
Виды изделий |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Потен- |
|
Виды |
и объемы |
В1 |
|
В2 |
|
В3 |
|
В4 |
|
В5 |
В6 |
циалы |
|||||
пр-ва |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
строк |
|
обор. и |
|
|
|
60 |
|
|
175 |
|
400 |
|
|
100 |
|
100 |
|
ui |
|
рес. времени |
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
А1 |
|
С11=1 |
λ11=5 |
1 |
10 |
4 |
20 |
5 |
|
15 |
2 |
20 |
0 |
1 |
|||
|
10 |
|
|
|
10 |
|
|
|
|
|
|
|
|
|
-1 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A2 |
|
10 |
|
2 |
1 |
|
5 |
5 |
5 |
2 |
|
10 |
4 |
4 |
0 |
1 |
|
|
50 |
|
|
|
15 |
20 |
10 |
|
|
|
5 |
0 |
|||||
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A3 |
|
10 |
|
30 |
2 |
|
8 |
2 |
20 |
5 |
|
25 |
1 |
5 |
0 |
1 |
|
|
15 |
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
-18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
A4 |
|
5 |
|
15 |
4 |
|
20 |
10 |
10 |
5 |
|
20 |
5 |
10 |
0 |
1 |
|
|
30 |
4 |
|
|
|
|
|
|
|
|
|
|
10 |
16 |
0 |
||
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Потенциалы |
1 |
|
|
1 |
|
1 |
|
|
1 |
|
|
1 |
|
0 |
|
||
столбцов vj |
|
|
|
|
5 |
|
|
5 |
|
|
|
|
|
||||
|
3 |
|
|
|
|
|
2 |
|
|
||||||||
Чем выше показатель rij , тем лучше с точки зрения минимизации целевой функции.
Поставка в клетку x(i, j) определяется по правилу xij min ai , |
b j |
. |
|
ij |
|||
|
|
Выбираем клетку с наибольшим rij . Из трех клеток (1,2), (1,5) (3,3)
выбираем любую. Запишем поставку в клетку (1,2) |
x |
min 10, |
175 |
10 , |
|
||||
|
12 |
10 |
|
|
|
|
|
||
x12 10 обведем кружком. Мощность по первой строке А1 исчерпана, эта строка при базисном распределении больше не рассматривается.
Переходим к клетке (3,3) x33 |
min 15, |
400 |
15. Строка А3 исключается |
|
20 |
||||
|
|
|
из дальнейшего рассмотрения.
В строках А2 и А4 находим наибольшее rij 5 для клеток (2,2), (2,4) (4,2). Потребность столбца В2 после поставки в клетку (1,2) уменьшилась
20 |
|
|
|
|
до 175 10 10 75. Поставка в клетку (2,2) x22 |
min 50, |
75 |
15 . |
|
5 |
||||
|
|
|
Исключается столбец В2.
Продолжая распределение, записываем поставки в клетки (2,4), (4,1), (4,5);
(2,3). |
Потребности |
реальных |
потребителей |
удовлетворены. |
|
Неиспользованную мощность в А2 |
и А4 |
принимаем в качестве поставки в |
|||
столбец фиктивного потребителя. |
|
|
|
||
Число кружков m n 1 |
4 6 1 |
9 . Получили опорный план. |
|||
2.Потенциалы
Показатель Cij клетки с поставкой должен быть равен сумме
Сij ui v j 
ij , отсюда
|
|
|
|
|
|
|
ui Cij v j |
|
ij ; |
||||
v j |
Cij |
|
ui |
. |
||
|
|
|||||
|
|
|
|
ij |
|
|
Расчет потенциалов начинают со столбца фиктивного потребителя, причем
потенциал этого столбца всегда равен нулю. |
|
|||
3. Характеристики |
|
|
|
|
Характеристика в λ-задаче Eij |
Cij |
ui v j ij . |
||
Если все Eij 0 , то план оптимальный |
|
|
||
|
0 |
15 |
|
7 |
Eij |
0 |
0 |
0 |
. |
|
0 |
|
||
|
|
|
|
|
0 |
0 |
0 |
|
0 |
План не является оптимальным. 4. Цепи
Выбираем клетку (1,3) с наименьшей отрицательной характеристикой. Цепи в λ-задаче строятся так, чтобы они обязательно имели выход на кружок (или два кружка) в столбце фиктивного потребителя. Соединение цепи с кружком в столбце фиктивного потребителя называется шлейфом. Цепи могут быть двух типов:
а) когда по кружкам, расположенным в столбцах реальных потребителей, удается построить замкнутую фигуру. В этом случае к ней пристраивается шлейф, который непосредственно или через другие кружки соединяет одну из вершин этой фигуры с каким-либо кружком в столбце фиктивного потребителя;
б) когда по кружкам, расположенным в столбцах реальных потребителей, такую замкнутую фигуру построить не удается. В этом случае в состав цепи входят два кружка в столбце фиктивного потребителя (цепь имеет два