Материал: 5462
11
Е11 |
70 |
(0 |
10) |
60, |
|
||
Е12 |
50 |
(0 |
30) |
20, |
|
||
Е13 |
30 |
(0 |
60) |
|
30 |
0, |
|
E21 |
30 |
(20 |
10) |
|
0, |
|
|
E22 |
40 |
(20 |
30) |
|
10 |
0, |
|
E24 |
50 |
(20 |
10) |
|
20, |
|
|
E31 |
20 |
( |
10 |
10) |
20, |
|
|
E33 |
50 |
( |
10 |
60) |
0, |
|
|
E34 |
60 |
( |
10 |
20) |
50, |
|
|
E35 |
90 |
( |
10 |
10) |
90, |
|
|
E44 |
50 |
(0 |
20) |
30, |
|
||
E45 |
80 |
(0 |
10) |
70. |
|
||
Условие оптимальности не выполнено для клеток (1.3) и (2.2). Выбираем клетку (2.2) с наименьшей отрицательной характеристикой и строим для нее контур (1.3) – (1.4) – (2.4) – (2.3).
Помечаем клетку (2.2) знаком «плюс», далее знаки чередуем по вершинам. Определяем величину поставки, перемещаемой по контуру
min(60,55) 55 (минимальная из поставок в вершинах со знаком
" "
минус). Величину 55 прибавляем к поставкам со знаком плюс и отнимаем
из поставок со знаком минус. Получаем план Х2 (табл. 2) |
|
||||||
|
План Х2 |
|
|
|
|
Таблица 2 |
|
|
60 |
100 |
95 |
125 |
40 |
ui |
|
|
70 |
50 |
30 |
20 |
10 |
|
|
100 |
|
|
55 |
5 |
40 |
u1=0 |
|
|
90 |
50 |
|
|
|||
|
|
|
|
|
|
||
120 |
30 |
40 |
80 |
40 |
50 |
|
|
|
|
|
|
120 |
|
u2=20 |
|
|
30 |
20 |
30 |
|
20 |
||
|
|
|
|
||||
80 |
20 |
20 |
50 |
60 |
90 |
u3=20 |
|
|
80 |
|
|
|
|
||
|
20 |
0 |
|
20 |
60 |
|
|
|
|
|
|
||||
120 |
10 |
30 |
60 |
50 |
80 |
u4=30 |
|
60 |
20 |
40 |
|
|
|||
|
0 |
40 |
|
||||
|
|
|
|
|
|
||
Vj |
V1=-20 |
V2=0 |
V3=30 |
V4=20 |
V5=10 |
|
|
12
Изменение целевой функции составит
z1 E13 |
30 55 1650 |
Значение z2 для плана Х2
z2 X1 
z1 12800 1650 11150.
Процесс решения продолжаем аналогично. Вычисляем потенциалы ui
иv j и характеристики свободных клеток для плана Х2. Все
характеристики свободных клеток в плане Х2 неотрицательны,
следовательно, план Х2 |
оптимальный и не единственный, т.к. |
Е33 Е44 0. При этом Zmin |
11150. |
Замечание. Если решается простая распределительная задача, то ее можно решить методом потенциалов по критерию максимума целевой функции. В этом случае условия оптимальности по теореме о потенциалах имеют вид
|
1) ui* |
v*j |
Cij , если xij* |
0 ; |
|
|
|
2) u* |
v* |
C |
, если x* |
0 . |
|
|
i |
j |
ij |
ij |
|
|
|
Первоначальный опорный план при этом можно находить по методу |
|||||
северо-западного угла или по методу максимального элемента Сij |
матрицы |
|||||
C |
(Cij )m n . |
|
|
|
|
|
|
Пример. Найти оптимальное распределение трех видов механизмов, |
|||||
имеющихся в количествах а1 |
45 , |
a2 20, |
a3 35 между четырьмя |
|||
участниками работ, потребности |
которых |
соответственно |
равны |
|||
b1 |
10, b2 20, b3 30, b4 40 |
|
|
при |
следующей |
матрице |
производительности каждого из механизмов на соответствующем участке работы
|
5 |
4 |
0 |
5 |
С |
3 |
5 |
3 |
0 |
|
0 |
6 |
7 |
6 |
Нулевые элементы означают, что данный механизм на данном участке работы не может быть использован.
Решение. Дана простая распределительная задача, которую можно решить по алгоритму транспортной задачи. Критерием оптимальности задачи является максимум целевой функции. В качестве поставщиков рассмотрим механизмы, в качестве потребителей участки работ.
Проверим условие баланса ai |
b j 100 . Задача закрытого типа. |
i |
j |
Решим задачу методом потенциалов по критерию максимума целевой функции. Первоначальный опорный план задачи находим по методу максимального элемента матрицы С. Первой заполняем клетку (3,4) с наибольшим С34 7 x34 min(35,30) 30 . Затем заполняются клетки в
13
порядке убывания Сij с учетом предыдущих поставок. Находим
потенциалы поставщиков и потребителей по занятым клеткам. Вычисляем характеристики свободных клеток по формуле Еij Cij (ui v j ) .
|
10 |
|
20 |
|
30 |
|
40 |
|
ui |
|||||
|
|
5 |
|
4 |
0 |
|
|
|
5 |
|
||||
|
|
|
|
|
|
|
||||||||
45 |
|
10 |
|
|
|
|
|
|
|
35 |
|
u1=-1 |
||
|
|
|
|
-1 |
|
-6 |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
20 |
|
3 |
20 |
5 |
3 |
|
|
|
0 |
u2=-1 |
||||
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
-2 |
|
|
-2 |
|
|
|
-5 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
||||
35 |
0 |
0 |
6 |
7 |
|
|
|
6 |
u3=0 |
|||||
-6 |
|
|
|
30 |
|
|
5 |
|
||||||
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Vj |
|
V1=6 |
V2=6 |
|
V3=7 |
V4=6 |
|
|
||||||
Все характеристики свободных клеток не положительны, следовательно, полученный план оптимальный и единственный.
Ответ. План оптимального распределения механизмов между участками работ
|
10 |
0 |
0 |
35 |
X опт |
0 |
20 |
0 |
0 . |
|
0 |
0 |
30 |
5 |
При этом наибольшая суммарная производительность работы всех механизмов равна
Zmax 565
Вопросы для самопроверки
1.Какова постановка транспортной задачи?
2.Какая задача называется открытой, закрытой?
3.Каким образом открытую задачу привести к закрытой?
4.Каково условие разрешимости транспортной задачи?
5.Как составляется первоначальный опорный план по методу минимального элемента матрицы С?
6.Сколько клеток в таблице должно быть занято в невырожденном плане?
7.Каково условие оптимальности транспортной задачи?
14
8.Как вычисляются характеристики свободных клеток и каков экономический смысл Eij ?
9.Каков критерий оптимальности при решении задачи на максимум целевой функции?
Задачи для самостоятельного решения
1.Составить оптимальное распределение специалистов четырех профилей, имеющихся в количествах 60; 30; 45; 25 между пятью видами работ. Потребности в специалистах для каждого вида работы
соответственно |
|
равны 20, 40, |
25, 45, |
30. Матрица |
|||||
|
7 |
5 |
2 |
0 |
4 |
|
|
|
|
С |
4 |
0 |
8 |
6 |
3 |
характеризует |
эффективность |
использования |
|
5 |
7 |
0 |
9 |
8 |
|||||
|
|
|
|
||||||
|
6 |
4 |
5 |
7 |
6 |
|
|
|
|
специалистов на данной работе.
2.Распределить четыре сорта топлива в количестве 70, 40, 50, 40 т между четырьмя агрегатами, потребности которых соответственно
|
8 |
3 |
5 |
9 |
равны 30, 50, 30, 80 т. Известна матрица С |
4 |
7 |
2 |
6 . |
|
6 |
5 |
8 |
6 |
|
4 |
2 |
7 |
4 |
Сij характеризуют теплотворную способность i-го сорта топлива при использовании его на j-м агрегате.
3.Ресурсы угля трех сортов составляют 300, 800, 400 т, а их теплотворная способность соответственно 1800, 2500, 3000 кал/кг. Уголь сжигается в четырех печах, потребности которых составляют 750, 920, 1110, 800 млн кал. Суммарные затраты на производство и доставку каждого сорта угля до каждой печи (в руб./т) задаются
27 36 18 18
матрицей С 30 25 15 20 . Найти оптимальный план
36 30 24 21
распределения ресурсов угля по печам.
Указание. Выразить данные задачи в одних единицах измерения.
4.Найти оптимальное распределение трех взаимозаменяемых механизмов по четырем видам земляных работ при заданных
ресурсах времени работы каждого механизма 240, 160, 150 часов, производительности механизмов 30, 55, 18 м3/час, объеме
|
15 |
|
|
|
|
подлежащих выполнению |
работ 5, 2, 3, |
8 тыс.м3 |
и |
матрице С |
|
|
|
2 |
1 |
0,5 |
1,2 |
себестоимости работ |
в усл.ед/м3 |
С 0,8 |
1,2 |
0,9 |
0,8 . |
|
|
0,5 |
1 |
0,6 |
0,9 |
Указание. Выразить данные задачи в одних единицах измерения.
5.На четырех ткацких станках с объемом рабочего времени 200, 300, 250, 400 станко-часов может изготовлятся ткань трех артикулов в количествах 260, 200, 340, 500 м за 1 час. Составить оптимальную программу загрузки станков, если прибыль от реализации 1 м ткани i-го артикула при изготовлении ее на j-м станке характеризуется
2,5 |
2,2 |
2 |
2,8 |
элементами матрицы С 1,6 |
1 |
1,9 |
1,2 , а суммарная |
0,8 |
1 |
0,6 |
0,9 |
потребность в ткани каждого из артикулов равна 200, 100, 150 тыс.м. Указание. Выразить данные задачи в одних единицах измерения.
6.Имеется три сорта бумаги в количествах 10, 8, 5 т, которую можно использовать на издание четырех книг тиражом 8000, 6000, 15000, 10000 экземпляров. Расход бумаги на одну книгу составляет 0,6; 0,8; 0,4; 0,5 кг, а себестоимость печатания книги при использовании i-го
24 16 32 25
сорта бумаги задается матрицей С 18 24 24 20 . Определить
30 24 16 20
оптимальное распределение материальных ресурсов.
Указание. Выразить данные задачи в одних единицах измерения.
7.Предприятие имеет два цеха и три склада. Цех №1 производит за определенное время 40 тыс. шт., цех №2 – 20 тыс. шт. одинаковых деталей. Пропускная способность складов предприятия: склад №1 – 16, №2 – 32, №3 – 12 тыс. шт. деталей. Стоимость перевозки 1
тыс. шт. деталей С |
30 |
30 |
20 |
. Определить оптимальную схему |
|
60 |
50 |
10 |
|
перевозок продукции, позволяющую достигнуть минимума расходов на транспортировку.
8.Имеется три склада, из которых необходимо вывезти муку в четыре
2 3 4 3
торговые точки. Стоимость перевозки 1 т груза С |
5 3 1 2 . |
2 1 1 4
Запасы муки на складах составляют соответственно 90; 30; 40 т. Потребность торговых точек в муке: 70; 30; 20; 40 т. Определить