Оптимальное распределение однородных ресурсов
Постановки задач
Постановка задачи А. Пусть имеется m источников финансирования А1, А2, ..., Аm и n периодов финансирования В1, B2, ..., Вn. Известны затраты, Связанные с выделением единицы денежных ресурсов Сij из i-го источника в j-ом периоде, а также объемы финансирования из каждого i-го источника в течение всего времени - а.. Известны суммарные объемы финансирования из всех источников в каждый j-й период времени - bj. Требуется определить объемы финансирования Xij из i-го источника в j-ом периоде, чтобы:
1. Ресурсы всех источников были реализованы.
2. Обеспечить финансирование в полном объеме в каждом периоде.
3. Достигнуть экстремума выбранного критерия оптимизации.
Исходная информация представлена в табл. 3.8.
Таблица 3.8
Постановка задачи В. Пусть имеется m пунктов отправления (или пунктов производства) некоторого ресурса (например, компьютеров, мебельных гарнитуров,...) А1, А2, ..., Аm и n пунктов назначения (или пунктов потребления) ресурса В1, B2, ..., Вn. Обозначим количество ресурсов (компьютеров, мебельных гарнитуров, ...) в i-ом пункте отправления через ai (i = 1, ..., m), а потребность каждого j-го пункта потребления этого вида ресурсов через bj (j = 1, ..., n). Известны затраты на перевозку одной единицы ресурса из каждого i-го пункта отправления в каждый j-ый пункт назначения. Требуется определить, какое количество ресурсов хij ³. 0 необходимо поставить (перевезти) из каждого i-го пункта отправления в каждый j-й пункт назначения, чтобы:
1. Вывести все ресурсы (компьютеры, мебельные гарнитуры,...) всех поставщиков.
2. Обеспечить всех потребителей данным видом ресурсов.
3. Все перевозки выполнить с минимальными затратами.
Выявление основных особенностей,
взаимосвязей и количественных закономерностей
Предположим, что общий объем (поставляемых ресурсов) финансирования из всех источников равен объему потребления ресурсов во всех периодах:
.
В такой постановке данная задача называется сбалансированной задачей финансирования. Объемы финансирования X.. из i-го источника Bj-ом периоде будем проставлять в левых нижних углах клеток таблицы. Введем ограничения в задаче:
1. Ресурсы всех источников должны быть реализованы. Это ограничение можно записать в таком виде:
2. Выполнить объем финансирования в каждом периоде. Это ограничение можно записать так:
1^= b„U - U,...,«) (3.5)
Введем граничные условия, которые определяют предельно допустимые значения искомых переменных. Для нашей задачи их можно представить в таком виде: X^0,(i= 1,2,..., m\U=\^..,n) (3.6)
Решение задачи традиционными методами
Построение математической модели. Суммарные затраты, связанные с распределением объемов финансирования Xij из каждого i-го источника в каждом j-ом периоде, можно записать в таком виде:
^=ES^^. ^ (3-7)
i=\ j=\
Совокупность систем линейных ограничений (3.4), (3.5), граничных условий (3.6) и линейной целевой функции (3.7) образует математическую модель для нашей задачи, которую часто называют транспортной.
Рассмотрим один из эффективных алгоритмов решения транспортной задачи - метод потенциалов. В качестве начального допустимого решения (начального, опорного плана) возьмем распределение, приведенное в табл. 3.9.
Таблица 3.9
Основ» >ii вычислительного процесса (алгоритма) этого метода является определение критерия оптимальности следующего вида:
^^-^
где С.. - фактические затраты, связанные с выделением единицы денежных ресурсов из i-го источника в j-ом периоде;
Z. - расчетные затраты, связанные с выделением единицы денежных ресурсов из i-го источника Bj-ом периоде.
Расчетные затраты Z.. определяются только для клеток, в которые финансовые ресурсы не распределены.
Если все cL > 0 (i = 1, 2, ..., m), (j = 1, 2, ..., п), то полученное допустимое решение (опорный план) является оптимальным, если нет, то с помощью этого критерия оптимизации можно указать способ улучшения решения.
Алгоритм решения. Алгоритм решения включает следующие основные этапы: < * 1. Составление и решение системы уравнений.
Вводятся условные цены-оценки единицы ресурса каждого поставщика U. (i = 1,2,..., m) и каждого потребителя V. (j = 1,2,..., п). Эти оценки, или
потенциалы, выступают в задаче как локальные цены (или наценки к единой цене), создающие заинтересованность в правильном распределении ресурсов. Так, цена в пункте потребления V. равна цене в пункте поставщика U. плюс наценка С. В на-шей задаче С.. представляет собой дополнительные затраты на выделение единицы ресурса из i-го источника в j-ом периоде. Таким образом:
^Ц^г
С целью нахождения значений V. (j = 1,2, ..., п) и U (i =- 1,2, ..., m) составляются уравнения для клеток, в которые распределены ресурсы в опорном плане: Уз-Ц-С^24;
^2-^-^22-^'
V, - Ц, - С^ = 19;
V, - U, = C^ = 3;
уз-^-^з^^ V4-^-^=8.
Имеем 7 уравнений и 8 неизвестных, поэтому одной из искомых переменных, желательно наиболее часто встречающейся в уравнениях, для облегчения счета дадим произвольное значение равное нулю. В нашей системе уравнений наиболее часто встречающаяся переменная - \]у Предположим, U^ =• 0.
Последовательно решая соответствующие уравнения, получим: V, = 19, V, -10, V^ = 100, U, - 76, U, = -8, U, = 16, V, - 24.
2. Определение расчетных значений Z.: Z. = V. - U.. "
IJ J I
При этом используются те индексы i и j, на пересечении которых в соответствующих клетках не распределены ресурсы: Z, i - V, - Ц == -57; Z„ = V, - U, = ;
zh - ^ - ^ =; Z^ = V^ - U, = 19+8 = 27; Z^ = Уд - Ц, -100 + 8 = 108; ^ - ^ - ^ = 24 + 8 = 32;
234 = ^-^-24 +0 = 24; ^2^2-^-^-^--^
Z^ = Уз - U, == 84.
3. Определение значений d.. и проверка условия оптимальности. Если все d.. >0 (i = 1,2, ...,m), (j' = 1,2, ..., n), то полученное допустимое решение (опорный план) является оптимальным, если нет, то переходят к новому: d^=C^-Z^=70+57-127;
d^ = C^-Z^ = 38+66 = 104;
^4 = ^ - zh - 92 +; d^ = C„ - Z^ - 58 - 27 = 31; d^=C^-Z^-56-108 = -52; d„ = C„ - Z„ == 40; ^-^-23^30-24-6; d„ = C„ - Z„ = 36 +6 = 42; d„ = C^ - Z„ == 37.
40 4д 4Л
В нашей задаче не все d^ > 0, а это означает, что решение еще не оптимально и мы переходим к определению нового опорного плана.
4. Определение нового опорного плана, которому отвечает меньшее значение целевой функции. Для этого в решение вводится та переменная X.., которой отвечает наименьшее отрицательное значение d.. Вводя ее, одновременно изменяют величины других переменных, по меньшей мере в трех заполненных клетках, чтобы не нарушались итоговые величины в строках и столбцах таблицы - а., Ь.. Для этого строят многоугольник, в котором одна иэ вершин находится в свободной клетке, а остальные - в заполненных ресурсами (загруженных). Для данной вершины d.. < О и имеет наименьшее значение. При этом все углы многоугольника должны быть прямыми. Перемещение ресурсов производят в пределах клеток, лежащих в вершинах многоугольника (рис. 3.3). Если для свобод-
ной клетки поставить знак + (плюс), а в следующей вершине - (минус), затем снова + и т. д., поочередно изменяя знак, то в нее переносится меньшее из чисел, стоящих в клетках с отрицательными знаками. В результате она исключается из опорного плана как основная переменная. Одновременно необходимо установить равновесие по всему многоугольнику: Если использовать правило перераспределения ресурсов в пределах многоугольника, распределение будет выглядеть, как на рис. 3.4: При этом сумма ресурсов по всем строкам и столбцам осталась без изменений. Проводя соответствующие преобразования в исходном допустимом решении (исходном плане), получим новый опорный план - см. табл. 3.10.
Рис 3.3. Схема перераспределения ресурсов
Рис. 3.4. Схема перераспределенных ресурсов
Таблица 3.10
^ | Bi | B2 | Вз | 84 | |
A, | ^ | ^ | ^ | ^ | 14 |
A2 | ^« | ^ | ^56 | ^ | 20 |
Аз | ^ | ^° | ^0 | ^ | 26 |
A4 | ^ | ^^ | ^ | ^ | 41 |
bj | 30 | 22 | 15 | 34 |
В результате построения нового допустимого решения (начального плана) способом потенциалов величина критерия оптимизации (целевой функции) будет равна: Y = 14 х 24 + 19 х 18 + 1 х 56 + 23 x 19 + +3 x 10 +7x3+ 34 x 8 = 1494.
Нахождением нового опорного плана заканчивается первое приближение (первая итерация). Далее аналогичные этапы, начиная с первого, повторяются.
Решение задачи с помощью Mathcad
Введите в рабочем листе поясняющий текст. Для этого вначале разместите в месте ввода текста курсор (визир - красный крестик). Затем выберите (щелчком мыши или с помощью клавиатуры) пункт Insert (Вставка) главного меню Mathcad. В появившемся падающем меню щелкните по пункту Text Region (Текстовая область) или в месте расположения курсора нажмите клавишу с двойной кавычкой (команда для ввода текста). В обоих случаях появится шаблон, указывающий место и начало ввода, после чего можно приступить к этой операции. Текстовая область будет автоматически увеличиваться по мере ввода текста. По окончании его необходимо вывести курсор (маркер ввода) за рамки области.
Далее введите критерий оптимизации - целевую функцию. Для этого вначале разместите курсор (визир - красный крестик) в месте ввода математического выражения. Затем с помощью соответствующих клавиш начните ввод; в первую очередь - имени критерия оптимизации, с аргументами в скобках через запятые: Y (XII, Х12, Х13, Х21, Х22, Х23, Х31, Х32, ХЗЗ).
Затем нажмите комбинацию клавиш Shift+: для ввода знака присваивания :=. На месте правой метки поместите все выражение критерия оптимизации. Начальные приближения вводятся аналогично.
Для решения задачи используем блок функций Given ... Minimize, выполнив следующие операции: а введите, если необходимо, комментарии, воспользовавшись клавишей
с двойной кавычкой; а введите ключевое слово Given; а введите систему ограничений, используя при вводе знак равенства,
вызванный нажатием комбинации клавиш Ctrl+==; а введите граничные значения (рис. 3.5);
а введите вектор-столбец искомых параметров, используя диалоговое окно Insert Matrix (Вставить матрицу). Для этого щелкните по левой
верхней кнопке на панели инструментов Matrix (Матрица) (рис. 3.6) или нажмите комбинацию клавиш Ctrl+M. В появившемся диалоговом окне Insert Matrix в поле Rows (Строки) число строк (элементов вектора-столбца) должно быть равно 9, а в поле Columns (Столбцы) - 1; а введите знак присваивания, нажав комбинацию клавиш Shift+: (двоеточие);
а используя диалоговое окно Insert Function (Вставить функцию), введите функцию Minimize с искомыми параметрами, нажав для этого комбинацию клавиш Ctrl+E; а скопируйте и вставьте вектор-столбец искомых параметров и введите
знак «равно».
На рис. 3.5 показано начало процесса оптимизации распределения однородных ресурсов с помощью Mathcad. Это математическое описание конкретной транспортной задачи в нотации системы. Представлен критерий оптимизации, начальные приближения и граничные условия. В описании двух первых пунктов использован знак присваивания := (двоеточие и равно). Он вводится щелчком мыши по второй кнопке в первой строке панели Evaluation (Вычисление), если она была заранее выведена на рабочий лист. Знак присваивания := может быть введен и нажатием комбинации клавиш Shift+: (двоеточие).
Рис. 3.5. Оптимизация распределения однородных ресурсов с помощью Mathcad
г^ис. З. о. 1 1родолжение оптимизации распределения однородных ресурсов
Следует обратить внимание на представление системы ограничений в Mathcad. При ее написании используется жирный знак равенства, вызываемый щелчком по кнопке с аналогичным знаком - второй в первом столбце панели инструментов Evaluation (Вычисление).
На рис. 3.6 показано продолжение процесса оптимизации распределения однородных ресурсов с помощью Mathcad. Жирный знак «равно» - его еще называют булевым равенством - можно вывести нажатием комбинации клавиш Ctrl+= (равно).
Оптимальное распределение однородных ресурсов зафиксировано в векторе (XI 1Х12Х13...). Из полученного решения видно, что XI 1 = 4, Х12 = 2, Х13= 8, X21 - О, Х22 = 20, Х23 = О, Х31 = 26, Х32 - О, ХЗЗ = 0. Это означает, что источник 1 должен профинансировать в первом периоде 4 единицы, во втором и в третьем - 8 единиц. Источник 2: в первом периоде 0 единиц, во втором 20 и в третьем - 0 единиц. Источник 3: в первом периоде 26 единиц, во втором и в третьем финансирование отсутствует. Первая цифра в переменной Х определяет источник, а вторая - период финансирования. Такое распределение денежных средств из источников обеспечит минимальные суммарные затраты Y, которые составят 1402 х 10^ единиц.
В рассмотренных задачах сумма объемов ресурсов поставщиков равна сумме объемов ресурсов потребителей. Однако в некоторых случаях такое равенство отсутствует.
Если объем ресурсов всех поставщиков больше объема ресурсов всех по-гребителей, то вводят фиктивного потребителя В^ с объемом потребле-1ия равным m п
^1>,-1>. ^ ^ А.
Затраты на доставку единицы ресурса из пункта отправления до фик-гивного пункта потребления должны быть обязательно равны между со-^ой, и их принимают равными нулю:
' Г - С -=Г =0 Г ^1,п+1~^2,п+1 •" ^т, п+\ ^•
'• Если объем ресурсов потребителей больше объема ресурсов поставщиков, то вводят фиктивного поставщика А^ с объемом поставки равным
^ п m
I ^i-l^-E^-
'•••• J=l i=l
^ Затраты на доставку единицы ресурса из фиктивного пункта отправления до каждого пункта потребления должны быть обязательно равны меж-1у собой, и их принимают равными нулю: ^ r — Г — =С =0
^ ^/п+1,1 ~ '^w+l,2 ••• ^т^п ^•
1., По преобразованным таблицам расчет выполняется так же, как и для Ьбалансированной транспортной задачи.
