Щербаков Б.Г., Попов А.А. Информационные технологии
Подождите немного. Документ загружается.
21
количество перестановок резко увеличивается с ростом m и равно M = m!. В
рассматриваемом ниже примере m = 5. В этом случае число перестановок
составляет 5!=120. Студент должен разобраться в методе решения задачи на
этом более общем примере и при выполнении «своего варианта» («m»
определяется по согласованию с преподавателем, но не менее m=3), провести
расчеты.
В научно-технической литературе задача относится к классу задач
линейного программирования.
Решение задачи традиционными методами
Алгоритм решения. Для решения задач данного типа разработано
множество методов. Рассмотрим самый распространенный – итерационный
метод Эгервари-Куна. Студент должен в нем разобраться и уметь объяснить.
Алгоритм включает четыре основных этапа. Для поиска оптимального
решения потребуется не более чем m - 2 последовательно проводимых
итераций.
1. Получение нулей в каждой строке и каждом столбце. Находим
наименьший элемент в каждой строке исходной таблицы (табл. 1), вычитаем
его из всех ее элементов и получаем новую таблицу (табл. 2). Аналогично
производим действия для каждого столбца новой таблицы (табл. 2). Получаем
табл. 3.
2. Проверка решения на оптимальность. Ищем строку с наименьшим
числом нулей (в нашей задаче это строка 3), отмечаем звездочкой один из них и
зачеркиваем все остальные нули строки и столбца, где есть нуль со звездочкой
Таблица 1. В этой таблице и ниже О(i) и К(i) – соответственно блоки и
группы
O(1)
O(2)
O(3)
O(4)
O(5)
K(1)
30 70 50 80 60
К(2)
20 40 40 50 70
К(3)
40 70 20 80 90
К(4)
90 70 30 80 100
К(5)
60 40 30 60 70
22
Таблица 2
O(1)
O(2)
O(3)
O(4)
O(5)
K(1)
0 40 20 50 30
К(2)
0 20 20 30 50
К(3)
20 50 0 60 70
К(4)
60 40 0 50 70
К(5)
30 10 0 30 40
Аналогичные операции последовательно выполняем для всех строк. Если
число нулей, отмеченных звездочкой, равно m, то решение является
неоптимальным, в противном случае следует переходить к очередному шагу. В
нашей задаче количество отмеченных звездочкой нулей не равно m,
следовательно, решение неоптимально (табл. 4). Переходим к следующему
этапу.
Таблица 3
O(1)
O(2)
O(3)
O(4)
O(5)
K(1)
0 30 20 20 0
К(2)
0 10 20 0 20
К(3)
20 40 0 30 40
К(4)
60 30 0 20 40
К(5)
30 0 0 0 10
Таблица 4
O(1)
O(2)
O(3)
O(4)
O(5)
K(1)
0∆
∆∆
∆
30 20 20 0*
К(2)
0
*
10 20 0 20
К(3)
20 40 0* 30 40
К(4)
60 30
0∆
∆∆
∆
20 40
К(5)
30 0
0∆
∆∆
∆
0* 10
23
Замечание:
0∆
∆∆
∆- в таблице 4 и других означает «перечеркнутый ноль»
3. Поиск минимального набора строк и столбцов, содержащих нули.
Необходимо отметить звездочкой:
а) все строки, не имеющие ни одного отмеченного звездочкой нуля (табл. 5,
строка 4);
б) все столбцы, содержащие перечеркнутый нуль хотя бы в одной из
отмеченных звездочкой строк (табл. 5, столбец 3);
в) все строки, содержащие отмеченные звездочкой нули хотя бы в одном
из помеченных столбцов (табл. 5, строка 3), Далее поочередно повторяются
действия б) и в) до тех пор, пока есть что отмечать.
После этого необходимо зачеркнуть каждую непомеченную строку, и
каждый помеченный столбец. Цель этого этапа - провести минимальное
количество горизонтальных и вертикальных прямых, пересекающих, по
крайней мере, один раз все нули.
4. Перестановка некоторых нулей. В не вычеркнутых клетках (табл. 5,
число 20) наименьший элемент вычитается из каждого элемента для
непомеченных столбцов и прибавляется к каждому элементу непомеченной
строки. Результаты расчета вносятся в новую таблицу (см. табл. 6).
Таблица 5
O(1)
O(2)
O*(3)
O(4)
O(5)
K(1)
0∆
∆∆
∆
30 20 20 0
*
К(2)
0* 10 20 0 20
К*(3)
20 40 0* 30 40
К*(4)
60 30 0 20 40
К(5)
30 0 0 0* 10
Таблица 6
O*(1)
O(2)
O*(3)
O*(4)
O*(5)
K*(1)
0* 30 20 20 0
К*(2)
0∆
∆∆
∆
10 20 0* 20
К*(3)
20∆
∆∆
∆
40
0∆
∆∆
∆
30 40
К*(4)
60 30 0*
20∆
∆∆
∆
40
К(5)
30 0* 0
0∆
∆∆
∆
10
24
Эта операция не изменяет оптимального решения. После нее выполняется
новая итерация, цикл расчета начинается с этапа 2, и так до тех пор, пока не
будет получено оптимальное решение. Поскольку число нулей, отмеченных
звездочкой, не равно m, выполняется новый итерационный цикл, по
завершении которого находится оптимальное решение (табл. 7).
Таблица 7
O(1)
O(2)
O(3)
O(4)
O(5)
K(1)
0∆
∆∆
∆
20 40 20 0*
К(2)
0*
0∆
∆∆
∆
40
0∆
∆∆
∆
20
К(3)
0∆
∆∆
∆
10 0* 10 20
К(4)
40
0∆
∆∆
∆ 0∆
∆∆
∆
0* 20
К(5)
40 0* 30 10 20
Согласно ему распределение групп по блокам должно быть проведено так:
• первая группа разрабатывает пятый блок;
• вторая - первый;
• третья - третий;
• четвертая - четвертый;
• пятая - второй,
при этом себестоимость выполнения всех работ будет минимальной и
составит Y
мин.
= 220 условных единиц
Решение задачи с использованием системы Mathcad
(Пример)
Студент должен свободно владеть алгоритмом и с его помощью решить на
ЭВМ задачу «своего варианта» (для своей «округленной» матрицы-задания).
Прежде всего, введем пояснительный текст в рабочем листе. Для этого
установим курсор (визир - красный крестик) в место ввода. Затем выберем
(щелчком мыши или с помощью клавиш) пункт Insert (Вставка) главного
меню Mathcad. В появившемся падающем меню выберем пункт Text Region
(Текстовая область) или в месте расположения курсора нажмем комбинацию
клавиш Shift + “ (двойная кавычка). В обоих случаях появится шаблон,
указывающий начало ввода текста. По мере заполнения текстовая область
25
будет автоматически увеличиваться. По окончании этой операции выведем
курсор (маркер ввода - красная вертикальная черточка) за рамки области.
Зададим критерий оптимизации - целевую функцию. Для этого установим
курсор в место ввода математического выражения. Начнем с нажатия
соответствующих клавиш. Сначала зададим имя критерия оптимизации Y с
аргументами, записанными через запятые и заключенными в скобки. Далее
нажмем комбинацию клавиш Shift+: (двоеточие) для получения знака
присваивания :=. На месте правой метки расположим «свое» выражение
критерия оптимизации, он равен раскрытому определителю исходной матрицы
«своего» варианта задачи. Аналогично вводятся начальные приближения.
Для решения задачи используем блок функций Given ... Minimize С этой
целью нужно:
• ввести, если необходимо, комментарии, нажав комбинацию клавиш
Shift + “;
• ввести ключевое слово Given;
• ввести систему ограничений, такую же, как в примере. При этом
используйте жирный знак равенства, вызвав его нажатием комбинации клавиш
Ctrl + =;
• ввести граничные условия (рис. 3.2.1) (такие же, как в примере);
26
Рис 3.2,1 Формирование математической модели в Mathcad
• ввести шаблон присваивания := (двоеточие и знак равенства);
• ввести в левую метку шаблона вектор искомых переменных;
• ввести в правую метку шаблона имя функции Minimize с искомыми
параметрами, например Minimize (Y,X11,X12,...);
• вывести результаты расчета.
На рис 3.2.2 представлены результаты решения задачи о назначении.
Оптимальное распределение фиксируется в векторе (X11 Х12 Х21 ...) Из
решения примера видно, что Х12 = 1, Х21 = 1 и ХЗЗ = 1 (Первая цифра в
переменной X определяет группу, а вторая - блок). При таком распределении
«групп по блокам» минимальная себестоимость Y в примере составляет 100
условных единиц.
Для другой исходной матрицы оптимальное распределение другое. Оно
будет соответствовать полученной матрице.
27
Рис 3.2.2 Поиск оптимальных распределений в Mathcad
§ 3.3. Распределение однородных и неоднородных ресурсов
§3.3.1 Однородные ресурсы
Постановка задачи
Постановка задачи А. Пусть имеется m источников финансирования А
1
,
А
2
, …, А
m
и n периодов финансирования В
1
, В
2
, …, В
n
. Известны затраты,
связанные с выделением единицы денежных ресурсов С
ij
из i-го источника в j-
ом периоде, а также объемы финансирования из каждого i-го источника в
течение всего времени - a
j
Известны суммарные объемы финансирования из
всех источников в каждый i-й период времени - b. Требуется определить
объемы финансирования X из i-го источника в j-ом периоде, чтобы
• ресурсы всех источников были реализованы,
• обеспечить финансирование в полном объеме в каждом периоде,
• достигнуть экстремума выбранного критерия оптимизации
Исходная информация представлена в табл. 3.1.
28
Таблица 3.3.1.1
B
1
B
2
B
3
B
4
a
A
1
70
38
24 92
14
A
2
58
18
56 72
20
A
3
19
10
100
30
26
A
4
3
36
121
8
41
b
j
30 22 15 34
Постановка задачи В. Пусть имеется m пунктов отправления (или
производства некоторого ресурса (например, компьютеров, мебельных
гарнитуров и т.д.) -
A
I
;
А
2
,..., А
n
и n пунктов назначения (или потребления)
ресурса - В
1
, В
2
,..., В
n
. Обозначим количество ресурсов (компьютеров,
мебельных гарнитуров и т.д.) в i-ом пункте отправления через а
i
(i = 1,..., m), а
потребность каждого j-ro пункта потребления через b
j
(j = 1,..., n). Известны
затраты на перевозку одной единицы ресурса из каждого пункта i-ro
отправления в каждый j-й пункт назначения. Требуется определить, какое
количество ресурсов х
|
> 0 необходимо поставить (перевезти) из каждого i-ro
пункта отправления в каждый j-й пункт назначения, чтобы:
• вывести все ресурсы (компьютеры, мебельные гарнитуры и т.д.) всех
поставщиков;
• обеспечить всех потребителей данным видом ресурсов;
• все перевозки выполнить с минимальными затратами.
Выявление основных особенностей, взаимосвязей и количественных
закономерностей
Предположим, что общий объем (поставляемых ресурсов) финансирования
из всех источников равен объему потребления ресурсов во всех периодах:
∑∑
==
=
n
j
j
m
i
i
ba
11
В такой постановке данная задача называется сбалансированной задачей
финансирования. Проставим объемы финансирования Х
ij
из i-ro источника в j-
ом периоде в левых нижних углах клеток таблицы.
Введем ограничения:
1. Ресурсы всех источников должны быть реализованы. Это ограничение
можно записать в таком виде:
i
n
j
ij
aX =
∑
=1
, (i = l,2,...,m)
29
2. Выполнить объем финансирования в каждом периоде. Это ограничение
можно записать так:
j
m
i
ij
bX =
∑
=1
, (j = l,2,...,n)
Введем граничные условия, определяющие предельно допустимые
значения искомых переменных. Для нашей задачи их можно представить в
таком виде:
X
1
>0,(i = l,2,...,m),(j = l,2,...,n) (3.3.1.1)
Решение задачи традиционными методами
Построение математической модели. Суммарные затраты, связанные с
распределением объемов финансирования Х
ij
из каждого i-ro источника в
каждом j-ом периоде, можно записать в таком виде:m n
∑ ∑
= =
=
m
i
ij
n
j
ij
XCY
1 1
. 3.3.1.2
Совокупность систем линейных ограничений (см.выше), граничных
условий (3.3.1.1) и линейной целевой функции (3.3.1.2) образует
математическую модель задачи, которую часто называют транспортной.
Рассмотрим один из эффективных алгоритмов решения транспортной
задачи метод потенциалов. В качестве начального допустимого решения
опорного плана возьмем план, приведенный в табл. 3.3.1.2.
Основой вычислительного процесса (алгоритма) этого метода является
определение критерия оптимальности вида:
ijijij
ZCd
−
=
где C
ij
– фактические затраты, связанные с выделением единицы денежных
ресурсов из i-ro источника в j-ом периоде,
Z
ij
- расчетные затраты, связанные с выделением единицы денежных
ресурсов из i-ro источника в j-ом периоде.
Расчетные затраты Z
ij
определяются только для клеток, куда финансовые
ресурсы не распределены.
Если все d
ij
> 0 (i = l
,
2,..., m), (j = 1,2,..., n), то полученное допустимое
решение (опорный план) является оптимальным
,
если нет
,
то с помощью этого
критерия оптимизации можно указать способ улучшения решения.
30
Таблица 3.3.1.2
B
1
B
2
B
3
B
4
a
A
1
0
70
0
38
0
24
0
92
14
A
2
0
58
20
18
0
56
0
72
20
A
3
23
19
2
10
1
100
0
30
26
A
4
7
3
0
36
0
121
34
8
41
b
j
30 22 15 34
Алгоритм решения.
Алгоритм решения включает следующие основные этапы:
1. Составление и решение системы уравнений. Вводятся условные цены-
оценки единицы ресурса для каждого поставщика U
i
(i = 1, 2, ..., m) и каждого
потребителя V (j = 1, 2,..., n). Эти оценки или, как их чаще называют
,
потенциалы выступают в задаче как локальные цены (или наценки к единой
цене), создающие заинтересованность в правильном распределении ресурсов.
Так
,
цена в пункте потребления Vj равна цене в пункте поставщика U
j
плюс
наценка С
ij
. В нашей задаче наценка С
ij
представляет собой дополнительные
затраты на выделение единицы ресурса из i-ro источника в j-ом периоде. Таким
образом:
V
J
=
U
1
+ C
1J
.
С целью нахождения значений V
j
(j = 1,2,..., n) и U
i
(i = 1,2,...
,
m)
составляются уравнения для клеток, в которые распределены ресурсы в
опорном плане:
V
3
– U
1
= C
13
= 24
V
2
– U
2
= C
22
= 18
V
1
– U
3
= C
31
= 19
V
2
– U
3
= C
32
= 10
V
1
– U
4
= C
41
= 3
V
3
- U
3
= C
33
= 100;
V
4
- U
4
= C
44
= 8.
Мы имеем 7 уравнений и 8 неизвестных, поэтому одной из искомых
переменных наиболее часто встречающейся в уравнениях, для облегчения счета
необходимо присвоить произвольное значение равное нулю. В нашей системе
уравнений чаще всех встречается переменная U
3
. Предположим, U
3
= 0.
Последовательно решая соответствующие уравнения, получим: V, = 19, V
2
= 10,
V
3
= 100, U, = 76, U
2
= - 8, U
4
= 16, V
4
= 24.
2. Определение расчетных значений Z
ij
.
Z
ij
= V
j
- U
i