Щербаков Б.Г., Попов А.А. Информационные технологии
Подождите немного. Документ загружается.
31
При этом используются те индексы i и j, на пересечении которых в
соответствующих клетках ресурсы не распределены;
Z
11
= V
1
– U
1
= 19 - 76 = -57;
Z
12
= V
2
– U
1
= 10 - 76 = -66;
Z
14
= V
4
– U
1
= 24 – 76 = -52;
Z
21
= V
1
- U
2
= 19 + 8 = 27;
Z
23
= V
3
- U
2
=100 + 8 = 108;
Z
24
= V
4
- U
2
= 24 + 8 = 32;
Z
34
= V
4
- U
3
= 24 + 0 = 24;
Z
42
= V
2
- U
4
= 10 - 16 = -6;
Z
43
= V
3
- U
4
= 100 - 16 = 84.
3. Определение значений d
t
и проверка условия оптимальности.
Если все d > 0 (i = 1, 2,..., m), (j = 1, 2,..., п), то полученное допустимое
решение (опорный план) является оптимальным, если нет, то переходят к
новому:
d
11
= C
11
– Z
11
= 70 + 57 = 127;
d
12
= C
12
- Z
12
= 38 + 66 = 104;
d
14
– С
14
– Z
14
= 92 + 52 = 144;
d
21
= C
21
- Z
21
= 58 - 27 = 31;
d
23
= C
23
- Z
23
= 56-108 = -52;
d
24
= C
24
- Z
24
= 72 - 32 = 40;
d
34
= C
34
- Z
34
= 30 - 24 = 6;
d
42
= C
42
- Z
42
= 36 + 6 = 42;
d
43
= C
43
- Z
43
= 121 - 84 = 37.
В нашей задаче не все d
23
> 0, а это означает, что решение еще
неоптимально, и мы переходим к определению нового опорного плана.
4. Определение нового опорного плана с меньшим значением целевой
функции. Для этого в решение вводится та переменная X
ij
, которой отвечает
наименьшее отрицательное значение d
ij
. Вводя ее, одновременно изменяют
величины других переменных, по меньшей мере в трех заполненных клетках,
чтобы не нарушались итоговые величины в строках и столбцах таблицы - a., b.
Для этого строят многоугольник, одна из вершин которого находится в
свободной клетке, а остальные - в заполненных ресурсами (загруженных). Для
этой вершины d
ij
< 0 и имеет наименьшее значение. При этом все углы
многоугольника должны быть прямыми. Перемещение ресурсов производят в
пределах клеток, лежащих в вершинах многоугольника (рис. 3.3.1.1). Если для
свободной клетки поставить знак + (плюс), а в следующей вершине - (минус),
затем снова + и т.д., поочередно изменяя знак, то в нее переносится меньшее из
чисел, стоящих в клетках с отрицательными знаками. В результате она, как
основная переменная, исключается из опорного плана. Одновременно
необходимо установить равновесие по всему многоугольнику.
Если использовать правило перераспределения ресурсов в пределах
многоугольника, распределение будет выглядеть, как на рис. 3.3.1.2р.
32
Рис. 3.3.1.1 Схема перераспределения ресурсов
Рис. 3.3.1.2. Схема перераспределенных ресурсов
При этом сумма ресурсов по всем строкам и столбцам осталась без
изменений. Проводя соответствующие преобразования в исходном допустимом
решении (плане), получим новый опорный план (табл. 3.3.1.3).
В результате построения нового допустимого решения (начального плана)
способом потенциалов величина критерия оптимизации (целевой функции)
будет равна:
Y = 14 х 24 + 19 х 18 + 1 х 56 + 23 X 19 + 3 X 10 + 7 х 3 + 34 х 8 = 1494.
Нахождением нового опорного плана заканчивается первое приближение
(итерация). Далее все этапы повторяются.
Таблица 3.3.1.3
B
1
B
2
B
3
B
4
a
A
1
0
70
0
38
14
24
0
92
14
A
2
0
58
19
18
1
56
0
72
20
A
3
23
19
3
10
0
100
0
30
26
A
4
7
3
0
36
0
121
34
8
41
b
j
30 22 15 34
33
Решение задачи с помощью Mathcad
Введите в рабочем листе поясняющий текст. Для этого поместите в
позицию ввода курсор (визир - красный крестик) и выберите (щелчком мыши
или с помощью клавиш) пункт Insert (Вставка) главного меню Mathcad. В
появившемся падающем меню щелкните по пункту Text Region (Текстовая
область) или в месте расположения курсора нажмите комбинацию клавиш
Shift+" (двойная кавычка). В обоих случаях появится шаблон, указывающий
начало ввода. По мере заполнения текстовая область будет автоматически
увеличиваться. После этого курсор (маркер ввода) необходимо вывести за
рамки текстовой области.
Задайте критерий оптимизации - целевую функцию. Для этого вначале
поместите курсор (визир - красный крестик) в позицию ввода математического
выражения. Затем с помощью соответствующих клавиш введите:
Y (X11, Х12, Х13, Х21, Х22, Х23, Х31, Х32, ХЗЗ)
Далее нажмите комбинацию клавиш Shift+: (двоеточие) для ввода знака
присваивания :=. На месте правой метки расположите все выражение критерия
оптимизации. Начальные приближения вводятся аналогично.
Для решения задачи используем блок функций Given... Minimize. С этой
целью нужно:
• ввести, если необходимо, комментарии, воспользовавшись комбинацией
клавиш Shift+";
• ввести ключевое слово Given;
• ввести систему ограничений. При этом используйте жирный знак
равенства, вызываемый нажатием комбинации клавиш Ctrl+=;
• ввести граничные значения (рис. 3.3.1.3);
• ввести шаблон присваивания :=(двоеточие и знак равенства);
• ввести в левую метку шаблона вектор искомых переменных;
• ввести в правую метку шаблона имя функции Minimize с искомыми
параметрами, например Minimize (Y,X11,X12,...), - рис. 3.3.1.4;
• вывести результаты расчета.
На рис. 3.3.1.3 показано начало процесса оптимизации распределения
однородных ресурсов с помощью Mathcad. Это математическое описание
конкретной транспортной задачи. Здесь представлены критерий оптимизации,
начальные приближения и граничные значения. В описании двух первых
пунктов использован знак присваивания := (двоеточие и равно). Он вводится
щелчком левой кнопки мыши по второй кнопке в первой строке панели
инструментов Evalu... (Вычисления), если панель выведена на рабочий лист.
Знак присваивания может быть введен и нажатием комбинации клавиш Shift+:
(двоеточие).
Следует обратить внимание на представление системы ограничений в
Mathcad. При ее написании используется жирное равно, вызываемое щелчком
по кнопке с жирным знаком равенства - второй в первом столбце панели
инструментов Evalu...
34
На рис. 3.3.1.3 показано продолжение процесса оптимизации
распределения однородных ресурсов с помощью Mathcad. Жирный знак равно
(его еще называют булевым равенством) можно вывести нажатием комбинации
клавиш Ctrl+= (равно).
Оптимальное распределение однородных ресурсов зафиксировано в
векторе (XI1 Х12 Х13...). Из полученного решения видно: XI1 - 4, Х12 = 2, Х13
- 8, Х21 - О, Х22 = 20, Х23 = О, Х31 = 26, Х32 = О, ХЗЗ = 0. Это означает, что
источник 1 должен профинансировать в первом периоде 4 единицы, во втором
2 и в третьем 8 единиц. Источник 2: в первом периоде 0 единиц, во втором 20 и
в третьем 0 единиц. Источник 3: в первом периоде 26 единиц, во втором 2 и в
третьем финансирование отсутствует. Первая цифра в переменной X
определяет источник, а вторая - период финансирования. Такое распределение
денежных средств из источников обеспечит минимальные суммарные затраты
Y, которые составят 1402 х 10
3
единиц.
Рис 3.3.1.3 Оптимизация распределения однородных ресурсов с помощью
Mathcad
35
Рис 3.3.1.4 Продолжение оптимизации распределения однородных ресурсов с
помощью Mathcad
В рассмотренных задачах сумма объемов ресурсов поставщиков равна
сумме объемов ресурсов потребителей. Однако в некоторых случаях такое
равенство отсутствует.
Если объем ресурсов всех поставщиков больше объема ресурсов всех
потребителей, то вводят фиктивного потребителя В
п+1
с объемом потребления
равным
Затраты на доставку единицы ресурса из пункта отправления до
фиктивного пункта потребления должны быть одинаковыми и их принимают
равными нулю:
Если объем ресурсов потребителей больше объема ресурсов поставщиков,
то вводят фиктивного поставщика А
щ+1
с объемом поставки
Затраты на доставку единицы ресурса из фиктивного пункта отправления
до каждого пункта потребления должны быть одинаковыми, и их принимают
равными нулю:
По преобразованным таблицам расчет выполняется так же, как и для
сбалансированной транспортной задачи.
36
3.3.2 Неоднородные ресурсы
Постановка задачи
На предприятии постоянно возникают задачи определения оптимального
плана производства продукции при наличии конкретных ресурсов (сырья,
полуфабрикатов, оборудования, финансов, рабочей силы и др.) или проблемы
оптимизации распределения неоднородных ресурсов на производстве.
Рассмотрим несколько возможных примеров постановки таких задач.
Постановка задачи А. Для изготовления n видов изделий И., И
2
,..., И
п
необходимы ресурсы m видов: трудовые, материальные, финансовые и др.
Известно требуемое количество отдельного i-ro ресурса для изготовления
каждого j-ro изделия. Назовем эту величину нормой расхода с
ij
. Пусть
определено количество каждого вида ресурса, которым предприятие
располагает в данный момент, - а
i
Известна прибыль П., получаемая
предприятием от изготовления каждого j-ro изделия. Требуется определить,
какие изделия и в каком количестве должны производиться предприятием,
чтобы прибыль была максимальной. Исходные данные представлены в табл.
3.3.2.1.
Постановка задачи В. Пусть в распоряжении завода железобетонных
изделий (ЖБИ) имеется m видов сырья (песок, щебень, цемент) в объемах а
i
Требуется
Таблица 3.3.2.1
Изготавливаемые изделия
Используемые ресурсы,
QJ
И. И
2
Из И4
Наличие
ресурсов,
а j
Трудовые 3 5 2 7 15
Материальные 4 3 3 5 9
Финансовые 5 6 4 8 30
Прибыль, rij 40 50 30 20
произвести продукцию п видов. Дана технологическая норма с.
потребления отдельного i-ro вида сырья для изготовления единицы продукции
каждого j-ro вида. Известна прибыль П.., получаемая от выпуска единицы
продукции j-ro вида. Требуется определить, какую продукцию и в каком
количестве должен производить завод ЖБИ, чтобы получить максимальную
прибыль. Исходные данные представлены в табл. 3.3.2.2.
37
Таблица 3.3.2.2
Изготавливаемых изделий Используемые
ресурсы, о.
И
1
И
2
Из И
4
Наличие
ресурсов, а.
Песок 3 5 2 7 15
Щебень 4 3 3 5 9
Цемент 5 6 4 8 30
Прибыло, rij 40 50 30 20
Постановка задачи С. Пусть на предприятии после модернизации
производства появился свободный ресурс времени оборудования. Предлагается
организовать производство новых изделий нескольких наименований. Известно
время, требуемое на изготовление отдельного изделия на каждом
оборудовании, свободные резервы времени на каждой машине, а также
прибыль, получаемая от выпуска каждого изделия. Требуется определить, какие
изделия и в каком количестве целесообразно производить, чтобы получить
максимальную прибыль.
Выявление основных особенностей, взаимосвязей и количественных
закономерностей
Количество изделий j-ro наименования, которое может производить
предприятие, обозначим через х.
Зная количество каждого вида i-ro ресурса для изготовления отдельного j-
ro типа изделия - норму расхода с
г
- и количество каждого i-ro ресурса а. (табл.
3.3.2.2), можно задать следующую систему неравенств:
Зх
1
+5х
2
+2х
3
+7х
4
<15
4х
1
+3х
2
+3х
3
+5х
4
<9 (3.3.2.1)
5х
1
+6х
2
+4х
3
+8х
4
<30
Полученную систему неравенств можно записать в виде совокупности
равенств, если в каждое из них ввести фиктивные изделия (дополнительные
переменные) х
5
, х
6
, х
7
, при изготовлении которых используют каждый
оставшийся вид ресурса.
В этом случае система равенств примет вид:
3x
1
+ 5х
2
+ 2х
3
+ 7х
4
+x
5
= 15
4x
1
+ 3x
2
+ 3х
3
+ 5х
4
+ х
6
= 9 (3.3.2.2)
5x
t
+ 6х
2
+ 4хз + 8х
4
+ х
7
= 30
Это преобразование необходимо для дальнейшего упрощения вычислений.
Прибыль, получаемая от фиктивных изделий, принимается равной нулю.
Построение математической модели. Критерий оптимизации (суммарная
величина прибыли) можно представить как:
EcjXj (3.3.2.3)
38
Граничные условия будут записаны следующим образом:
Xj
>0 (j = l,2,...,7) (3.3.2.4)
Совокупность системы ограничений (3.3.2.2), целевой функции (3.3.2.3) и
граничных условий (3.3.2.4) образует математическую модель для нашей
задачи.
Решение задачи традиционными методами
Алгоритм решения. Для решения данной задачи разработано много
способов. Рассмотрим один из наиболее распространенных - симплекс-метод
Для его использования необходимо определить начальный базис, то есть
решение, удовлетворяющее системе равенств (3.3.2.2). В некоторых задачах
базис просматривается непосредственно, но во многих его необходимо найти.
В данной задаче базис определить легко. Для этого требуется взять m
неизвестных - по числу уравнений в системе (3.3.2.2). В нашей системе
уравнений (т = 3) это х
5
, х
6
, х
7
, которые и выражаем через оставшиеся
неизвестные х., х
2
, х
3
, х
4
.
Систему уравнений необходимо записать в следующем виде:
x
5
=15-(3х
1
+ 5х
2
+2х
3
+ 7х
4
)
x
6
=9 - (4х
1
+ 3х
2
+3х
3
+ 5х
4
) (3.3.2.5)
х
7
= 30 - (5x
t
+6x
2
+ 4x
3
+ 8х
4
)
Переменные, находящиеся в левой части системы, называются базисными
(основными), а находящиеся справа - небазисными (неосновными). Для
определения значений базисных переменных х
5
, х
6
, х
7
необходимо приравнять к
нулю небазисные
x
1,
х
2
, х
3
, x
4
и подставить их в систему уравнений (3.3.2.5). Полученное
таким образом решение является базисным. В нашей задаче оно будет
выглядеть следующим образом:
(Х
1
, Х
2
, Х
3
, Х
4
, Х
5
, Х
6
, Х
7
)
(0, 0, 0, 0, 15, 9, 30)
После определения начального базиса можно перейти непосредственно к
использованию алгоритма симплекс-метода, который содержит следующие
основные этапы:
1. Заполнение исходной симплекс-таблицы. В соответствии с полученной
системой уравнений и критерием оптимизации заполним исходную симплекс-
таблицу (табл. 3.3.2.3).
2. Проверка базисного решения на оптимальность. Просматриваются знаки
коэффициентов при небазисных переменных в целевой функции (критерий
оптимизации) - последняя строка табл. 3.3.2.3.
Если все коэффициенты при небазисных переменных неположительные, то
исходный базис является оптимальным; в противном случае переходят к
39
следующему этапу. В нашей задаче решение неоптимально, так как все
коэффициенты целевой функции при небазисных переменных положительны.
3. Проверка задачи на наличие решения. Если столбец коэффициентов при
какой-либо неоазисной переменной, имеющей положительный коэффициент в
целевой функции, в системе уравнений состоит из одних неположительных
чисел, то максимальное значение целевой функции стремится к бесконечности,
то есть задача решения не имеет. В нашей задаче решение существует.
4. Выбор из небазисных переменных той, которая способна при введении
ее в базис увеличить значение целевой функции. Наиболее простой и чаще
всего используемый способ состоит в выборе той небазисной переменной,
которой соответствует наибольший положительный коэффициент в целевой
функции. В нашей задаче это переменная х
2
(наибольший положительный
коэффициент равен 50). Значит, х
2
необходимо ввести в базис.
5. Определение базисной переменной, которая должна быть выведена из
базиса. Для всех положительных коэффициентов в системе уравнений
определяется отношение свободного члена уравнения к коэффициенту при
вводимой в базис переменной. Для нашей задачи это будут следующие
отношения: 15/5 = 3; 9/3 = 3; 30/6 = 5.
Минимальное из полученных отношений указывает строку и базисную
переменную, которая должна быть выведена из базиса. При наличии
нескольких одинаковых отношений берется любое. В нашей задаче выведем из
базиса переменную х
5
.
6. Представление новой базисной переменной через небазисные. Строится
новая симплекс-таблица (табл. 3.3.2.4). Отмечается звездочкой строка и столбец
в предыдущей симплекс-таблице (табл. 3.3.2.3) для выводимой из базиса и для
вводимой в него переменной.
Коэффициент, находящийся на пересечении строки и столбца, отмеченных
звездочками, называется разрешающим и также помечается звездочкой (табл.
3.3.2.3). Все коэффициенты строки со звездочкой делятся на разрешающий
Таблица 3.3.2.3
Базисные
переменн
ые
Свободны
е члены
Коэффициенты при базисных и небазисных переменнвх
X
J
°i
X]
х|
Х
3
*4
Х
5
Хб
х?
V*
Х
5
15
3
ri*l
i_ — _j
2
7
1
0
0
Хб
9
4
3
3
5
0
1
0
X?
30
5
6
4
8
0
0
1
П
. 0 40 50 30 20 0 0 0
40
Таблица 3.3.2.4
Базисные
переменн
ые
Сбободни
е члены
Коэффициенты при базисных и небаэисных
переменных
х,
а,
X)
Х2
*3
Х4
*5
Хб
*7
Х2
3
3/5
1
2/5
7/5
1/5
0
0
Хб
0
11/5
0
9/5
4/5
-3/5
1
0
Х7
12
7/5
0
8/5
-2/5
-6/5
0
1
п.
-150
10
0
10
-50
-10
0
0
элемент, а результаты расчета заносятся в новую симплекс-таблицу. В нашей
задаче на первой итерации разрешающий элемент равен 5 (табл. 3.3.2.3).
Результаты деления каждого элемента строки, отмеченной звездочкой, на
разрешающий коэффициент заносятся в строку 1 новой таблицы (табл. 3.3.2.4).
7. Представление остальных базисных переменных и целевой функции через
новый набор небазисных переменных. Для этого коэффициенты в последней
таблице при новой базисной переменной умножаются на такое число, чтобы
после сложения с преобразуемой строкой предыдущей таблицы в столбце
новой таблицы при базисной переменной появился ноль. Результаты сложения
заносятся в новую симплекс-таблицу. Исходя из этого, для получения
коэффициентов второй строки в новой таблице (табл. 3.3.2.4) умножаем
коэффициенты при новой базисной переменной х
2
на число -3, складываем с
соответствующими коэффициентами второй строки предыдущей симплекс-
таблицы (табл. 3.3.2.3) и результаты расчета заносим во вторую строку новой
таблицы (табл. 3.3.2.4).
Аналогичные преобразования проводим и для других строк. После этого
выполняем новую итерацию. Цикл расчета начинается с этапа 2 и повторяется
до нахождения оптимального решения.
Поскольку в последней строке табл. 3.3.2.4 не все коэффициенты целевой
функции при небазисных переменных положительны, то решение
неоптимально; следовательно, выполняется следующий итерационный цикл
расчета и строится новая симплекс-таблица (табл. 3.3.2.5). В качестве вводимой
в базис небазисной переменной принимаем х
а
(или х,), имеющую наибольший
положительный коэффициент. Отмечаем звездочкой столбец х
3
. В качестве
выводимой из базис переменной берем х
6
, так как для нее частное от деления
свободного члена на соответствующий положительный коэффициент
минимально. Разрешающий множитель равен 9/5. Результаты расчета
представлены в табл. 3.3.2.5