Исследование операций и методы оптимизации

Так как у1=0, у3=0, то решение находится в точке, в которой выполняются равенства: х1-х2+2=0 и

4 -х1 = 0.

На рисунке 11 показана последовательность перехода от вершины к вершине в соответствии с работой алгоритма сим- плекс-метода. Цифрами обозначены соответствующие симплекс-

таблицы. Рис. 11

2.7. Алгоритм получения первого базисного решения с использованием симплекс – процедуры

(метод искусственного базиса)

Выше было показано, что алгоритмы симплекс-метода требуют, чтобы исходная система ограничений-равенств была приведена к базису, т.е. какиенибудь базисные переменные должны быть выражены через свободные. Оказывается, что первый базис можно так же получить, используя алгоритм сим- плекс-метода. Для этого для каждого ограничения-равенства вводится искусственная переменная zi (i=1,m). Каждое ограничение-равенство

βi - (gi1 x1 + ... + gin xn) = 0

формально записывается так:

zi =βi - (gi1 x1 + ... + gin xn), i=1,m ,

т.е. переменные zi тождественно равны нулю. Последнее равенство определяет так называемый искусственный базис.

Вводим в рассмотрение дополнительную целевую функцию

Lo = z1 + z2 + ... + zm → min ,

для чего суммируем коэффициенты при переменных xj всех равенств zi и получаем ОЗЛП, готовую для решения симплекс-методом.

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

Пример. Пусть исходную задачу ЛП мы привели к форме ОЗЛП и получили систему ограничений-равенств

29

Таблица 9

Таблица 9 соответствует оптимальному решению вспомогательной задачи (2.10) и дает выражение базисных переменных x1, x2 относительно свободной переменной x3, а именно:

x2 = 2/3 + 2/3x3;

x1 = 8/3 - 4/3x3.

Теперь можно приступать к выполнению симплекс-алгоритма, записав вместо строки Lo целевую функцию задачи, выраженную через свободные переменные. Чтобы такая запись получалась автоматически можно в таблицу 7 кроме строки Lo записать строку целевой функции исходной ОЗЛП и выполнять описанный выше алгоритм, помня, что генеральный элемент не может быть ни в строке Lo, ни в строке ЦФ.

2.8. Вырожденная задача ЛП

При использовании симплекс-метода некоторые свободные члены могут быть равны нулю. Это значит, что в вершине, которой соответствует CТ, равны нулю не k переменных, а больше (равна нулю и базисная). В этом случае при выборе генерального элемента отношение bi/aij будет минимальным именно для этой строки. Ясно, что соответствующую свободную переменную увеличить никак нельзя и целевая функция при переходе в новую вершину не меняется, т.к. мы остаемся фактически в этой же вершине, хотя формально перешли в новую.

Такая задача называется вырожденной задачей. Вырождение отрицательно сказывается на эффективности вычисления. Признаком вырожденности является равенство 0 некоторых свободных членов. В этом случае может произойти 2 отрицательных явления:

1.«Пробуксовка». Переходим в новую вершину, где равна нулю другая совокупность переменных, а на самом деле остаемся в той же точке. Значение ЦФ не меняется.

31

2.«Зацикливание» алгоритма. Через некоторое количество операций мы

можем прийти к первоначальной таблице, следовательно, если алгоритм не менять, то зацикливаемся.

Существует несколько способов борьбы с зацикливанием:

•Использование степени свободы алгоритма. Например, если в алгоритме сказано: «берем первый по порядку…» - то, если обнаруживается зацикливание, можно взять «второй по порядку». Аналогично, если сказано «берем любой…».

•«Зашумление» коэффициентов задачи ЛП. Прибавляем матрицу малых случайных величин к матрице А. Получаем А + ξ, где А – матрица коэффициентов; ξ – матрица очень малых случайных величин. Тогда матрица коэффициентов СТ не будет содержать одинаковых чисел и после вычислений появление нулей будет маловероятным. Подробнее этот сложный вопрос освещен в специальной литературе.

2.9. Двойственная задача ЛП

Важным вопросом анализа полученного решения ЛП является анализ чувствительности решения к параметрам модели (коэффициентам целевой функции, свободным членам ограничений, коэффициентам аij). Теория этого вопроса тесно связана с так называемой двойственной задачей ЛП. Двойственная задача ЛП получается из прямой и она имеет физический смысл, когда прямая задача – задача об использовании ресурсов. Имеются ресурсы m типов в количестве b1, … bm. Для изготовления одного изделия j – го типа расходуется aij сырья i-го типа. Каждое j – е изделие продается по цене сj. Ставится задача максимизации стоимости проданных изделий.

j−1

xj ≥ 0, j

Можно рассмотреть эту проблему по-другому. Пусть некоторые величины ∆i – стоимости единицы i – го ресурса. Нужно определить эти стоимости так, чтобы выполнялись неравенства, выражающие то, что стоимость затраченного ресурса на j – е изделие была бы не меньше стоимости изделия и при этом общие затраты на ресурсы были минимальны.

i=1

32

i=1

Задача (2.13), (2.14) называется двойственной по отношению к задаче (2.11), (2.12) Она получается из прямой (2.11), (2.12) так: коэффициенты целевой функции двойственной задачи – это правые части прямой задачи и наоборот; а коэффициенты aij – суммируются по другому индексу (матрица коэффициентов двойственной задачи это транспонированная матрица прямой задачи). Направление оптимизации целевой функции меняется на противоположное.

Основное свойство задачи ЛП: оптимальные значения целевой функции прямой и двойственной задачи ЛП совпадают:

Оптимальное решение задачи ЛП находится в седловой точке:

max L по хj = min L* по ∆i.

Существует и двойственный симплекс–метод решения задачи ЛП, который в ряде случаев эффективнее прямого [1, 10].

Экономический смысл двойственной задачи: какова цена единицы каждого ресурса ∆i, чтобы при заданных количествах ресурсов bi и стоимости единицы продукции сj обеспечить минимум общей стоимости затрат.

∆i называется двойственной оценкой или теневой ценой. Если решение прямой задачи найдено, то ∆i – есть коэффициенты, стоящие в строке L в последней оптимальной CТ.

Если ∆i > 0, то она показывает, насколько увеличивается значение целевой функции прямой задачи, если соответствующие запасы сырья i – го типа увеличиваются на единицу.

Соответствующая дополнительная переменная yi при этом равна нулю. Это означает, что i – е ограничение выполняется точно (как равенство) и весь ресурс bi тратится полностью.

При малом изменении коэффициентов модели оптимальное решение задачи ЛП не меняется, такое свойство называется устойчивостью. На рисунке 12 показано, что для ЦФ1 решением является точка А, для ЦФ3 *(при малом изменении коэффициентов cj) также точка А, а для ЦФ2 решением уже будет точка В.

33

Существуют специальные программы, которые позволяют проанализировать пределы изменения коэффициентов cj , при которых оптимальное решение не изменяется, а значение целевой функции меняется. Аналогично проводится анализ по правым частям bi.

Современные алгоритмы ЛП способны с использованием современных компьютеров решать задачи ЛП очень большой размерности. Многие из них учитывают архитектуру компьютера.

Наиболее широко известны блочные методы ЛП. При большой размерности матрица А будет содержать много нулей. В этом случае задачу можно решать по блокам. Вот почему параметрами сложности решаемой задачи ЛП являются: число переменных, число ограничений и число ненулевых коэффициентов ограничений. Число итераций симплексметода, за которое находится решение в большей степени зависит от числа ограничений. Современные программы ЛП имеют удобный интерфейс, позволяющий моделировать и решать небольшие задачи в удобной «математической» или табличной форме. Для решения задач ЛП большой размерности используются режимы работы с крупными базами исходных данных. Например, программа LINDO, а также приложение «Поиск решения» (SOLVER) про-

граммы Microsoft EXCEL.

34

где ai' и b'i - остатки запаса и заявки после предыдущей итерации. Этот

способ обеспечивает линейную независимость столбцов. Свойство допустимого плана: сумма перевозок по строке равна запасу, а по столбцу – заявке. План называется невырожденным, если отличных от нуля перевозок ровно m+n -1. В вышеприведенном примере m + n – 1 = 4 +4 – 1 = 7=7, т.е. план невырожденный.

Выполненные действия показаны в таблице 10 Определим стоимость плана:

L=4×5+5×4+1×4+2×2+3×1+5×3+5×2=76.

Часто бывают такие транспортные задачи, где количество ненулевых перевозок (базисных клеток) меньше, чем m + n – 1.

Пример:

Чтобы автоматически определять место для дополнения плана будем избавляться от вырожденности в процессе заполнения плана в соответствии с выражением (3.4). Вырожденность появляется тогда, когда в формуле (3.4) будет ai\=bj\ . В этом случае будем считать, что в строке ai\=ai\ + (0).

Метод минимального элемента В методе СЗУ мы не использовали стоимость перевозок. Существуют

методы, которые позволяют получить первый план сразу близким к оптимальному (т.е. с достаточно малой общей стоимостью перевозок).

Метод минимального элемента состоит в том, что порядок заполнения плана соответствует возрастанию стоимости. Но при этом запас исчерпывается полностью, т.е. перевозка ставится в соответствии с формулой (3.4) в клетке с минимальной стоимостью в строке, если не исчерпали запас, или в столбце, если не выполнили заявку.

Метод не обязательно гарантирует лучшее решение, чем метод С ЗУ, но, как правило, дает лучшие результаты.

Способ борьбы с вырождением такой же, как и в предыдущем методе. Пример: Начинаем с самого дешевого маршрута (А1В4), далее в столбце

В4 ищем самый дешевый (А4В4), затем в строке А4 минимальная стоимость 2 в маршруте (А4В2) и т.д.

37