Моделирование потоков работ методами линейного программирования

Многие оптимизационные задачи планирования, например задачи о потоках в сетях, могут быть сведены к моделям ли­нейного программирования (ЛП). В свою очередь, любая задача ЛП может быть приведена к канонической модели минимиза­ции линейной целевой функции с линейными ограничениями типа равенств. Если решение существует, то оно называется базисным. Геометрически базисные допустимые решения соот­ветствуют вершинам (крайним точкам) выпуклого многогран­ника, который ограничивает множество допустимых решений.

При поиске оптимального решения задачи линейного про­граммирования достаточно ограничиться перебором базисных допустимых решений. Число базисных решений может быть до­статочно велико для их перечисления прямым перебором за ре­альное время. Для решения ряда прикладных задач линейного программирования разработаны специальные решения, учиты­вающие особенности постановок задач данного типа и указанное свойство множества допустимых решений. Решение линейной распределительной задачи симплекс-методом

Симплекс-метод является наиболее рас­пространенным общим методом линейного программирования. Метод реализует направленный перебор допустимых базисных решений по соответствующим им крайним точкам выпуклого многогранника допустимых решений. На каждом шаге значе­ние целевой функции строго убывает. Переход между крайними точками осуществляется по ребрам выпуклого многогранника допустимых решений в соответствии с простыми линейно-алгеб­раическими преобразованиями системы ограничений. Посколь­ку число крайних точек конечно, а целевая функция линейна, то перебирая крайние точки в направлении убывания целевой функции, симплекс-метод за конечное число шагов сходится к глобальному минимуму.

Основная задача линейного программирования (ЛП) имеет следующий вид (2.6)—(2.7):

Для решения задачи (2.8)-(2.9) используются алгоритмы последовательного преобразования симплекс-таблиц, в которых последовательно реализуются этапы получения опорного и оп­тимального решений.

Рассмотрим эту задачу на конкретном примере.

Пусть имеются заявки 3-х типов — А, В pi С, которые прохо­дят обслуживание на приборах 4-х типов. Известно время про­хождения заявки каждого типа на каждом приборе. Известен

фонд времени каждого прибора, известна прибыль от обслужи­вания заявки каждого типа. Необходимо определить оптималь­ное количество обслуживаемых заявок каждого типа. Исходные данные задачи занесены в табл. 2.6.

Введя дополнительные переменные, получим основную зада­чу ЛИ для решения. Перепишем условие задачи в виде, необхо­димом для формирования симплекс-таблиц:

Здесь базисные переменные х,..., xj имеют смысл неисполь­зованного ресурса. Заполняем симплекс-таблицу 2.7. Задача

решается в 2 этапа:

• получение опорного пла­на;

• получение оптимального плана.

Если столбец свободных чле­нов bj положительный, то имеем опорный план. Если в послед­ней строке (для критерия F) нет отрицательных элементов, то имеем оптимальный план. В данном конкретном случае име­ем опорный план.

Построение оптимального плана.

Находим любой из отрицательных элементов в последней строке, например (—12). Столбец, в котором расположен этот элемент, называется разрешающим столбцом. Для разрешающе­го столбца найдем отношение каждой строки, за исключением последней, к элементу столбца. Среди этих отношений находим минимальное положительное число. Строка, в которой располо­жен этот элемент, называется разрешающей строкой. Элемент Srk (т — номер строки, к — номер столбца) на пересечении разрешающей строки и разрешающего столбца называется раз­решающим элементом.

В результате преобразований количество отрицательных эле­ментов в строке уменьшается, а значение F увеличивается, что говорит об улучшении плана. Преобразования таблиц повторя­ются до тех пор, пока в последней строке все элементы не станут по ложите льными.

Последующие этапы отражены в соответствующих симплекс

Выпишем оптимальное решение из последней.

Таким образом, заявки 3-го типа при оптимальном плане не обслуживаются. Кроме того, остаются неиспользованными 112 единиц ресурса прибора второго типа и 156 единиц ресурса прибора четвертого типа.

Решение задачи о назначении

Пусть имеется п работ (задач) и п кандидатов на их выполнение (персонала, процессоров, мест, машин). Пусть Cjj (i,j = 1,2....................................... п) — затра­ты (стоимость, время), связанные с назначением кандидата г на работу j. Введём переменные Xjj (i,j = 1,2,..., п) такие, что Xjj = 1, если кандидат i назначен на работу j, и xj = 0
в противном случае. Задача заключается в таком назначении (распределении), при котором суммарные затраты на выполне­ние всех работ минимальны.

Задача может быть сформулирована как задача ЛП

j=

кандидат назначается только на одну работу и каждая работа выполняется только одним кандидатом. Решение данной экстре­мальной задачи путем прямого перебора практически затрудни­тельно при больших значениях п.

Есть специальный метод решения этой задачи, называемый венгерским методом. Рассмотрим конкретный пример. Пусть имеется 4 кандидата и 4 работы. Исходные данные задачи неVIIIчшил затрат cj (i,j = 1,2,...,4) содержатся в табл. 2.11.

Метод основывается на том факте, что оптимальность решения не нару­шается при увеличении или уменьше­нии элементов строки (столбца) табли­цы на одну и ту же величину. Отсюда следуют все основные преобразования исходной таблицы.

Алгоритм решения задачи разби­вается на несколько этапов.

1. Получение нулей во всех строках и столбцах матрицы.

Для этого находим минимальный элемент каждой строки и вычитаем его из всех элементов соответствующей строки. Ана­логично поступаем для каждого столбца в том случае, если он не содержит нуля после работы со строками.

2. Поиск оптимального решения.

В строке, имеющей меньшее количество нулей, отмечаем точкой один из нулей и зачёркиваем все остальные нули, нахо­дящиеся в строке и столбце, связанные с данным отмеченным нулем. Данная операция проводится последовательно для всех строк. Если каждая строка содержит отмеченный ноль (т. е. чис­ло нулей, отмеченных точкой, равно п), то имеем оптимальное решение. В этом случае полагаем, что для элементов матрицы с

отмеченными нулями хц = 1, а для других хц = 0. В противном случае переходим к следующему этапу.

3. Этап разметки строк и столбцов.

3.1. Отмечаем точкой строку, не содержащую ни одного отмеченного нуля.

3.2. Отмечаем столбец, содержащий перечёркнутый нуль в отмеченной строке.

3.3. Отмечаем строку, содержащую отмеченный нуль хотя бы в одном из отмеченных точкой столбцов.

Эта процедура разметки строк и столбцов выполняется до тех пор, пока есть что отмечать.

4. Перестановка отмеченных нулей.

Зачеркнём каждую неотмеченную строку и каждый отмечен­ный столбец. В не перечёркнутых клетках находим минималь­ный элемент. Вычтем этот элемент из элементов неперечёркну­тых столбцов и добавим этот минимальный элемент ко всем элементам перечёркнутых строк. Возвращаемся к этапу 2.

Результаты 1-го и 2-го (заключительного) этапов отражены в таблицах 2.12, 2.13.

Таблица 2Л2                            Таблица 2ЛЗ

В данном случае получаем решение (отмеченные нули вы­делены полужирным шрифтом и подчёркнуты), для которого с =17.