Задача линейного программирования: нахождение оптимального плана

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

     В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений  по частям, соответствующим текущим  базисным векторам. Указанная способность  делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени  счёта. Хорош для ситуаций, когда число переменных n значительно превышает число ограничений m.

     В целом, метод отражает традиционные черты общего подхода к решению  задач линейного программирования, включающего в себя канонизацию  условий задачи, расчёт симплекс-разностей, проверку условий оптимальности, принятие решений о коррекции базиса и исключение Жордана-Гаусса.

     Особенности заключаются в наличии двух таблиц - основной и вспомогательной, порядке  их заполнения и некоторой специфичности  расчётных формул.

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

     1. если прямая задача является  задачей максимизации, то двойственная  будет задачей минимизации, и  наоборот;

     2. коэффициенты целевой функции  прямой задачи становятся свободными  членами ограничений двойственной  задачи;

     3. свободные члены ограничений  прямой задачи становятся коэффициентами  целевой функции двойственной  задачи;

     4. матрица ограничений двойственной  задачи получается путем транспортирования  матрицы ограничений прямой задачи;

     5. знаки неравенств в ограничениях  изменяются на противоположные;

     6. число ограничений прямой задачи  равно числу переменных двойственной  задачи, и наоборот.

     Отыскание решения задачи двойственным симплекс-методом  включает в себя следующие этапы:

     1. Находят псевдоплан задачи.

     2. Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану.

     3. Выбирают разрешающую строку  с помощью определения наибольшего  по абсолютной величине отрицательного  числа столбца вектора Р₀ и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+1)-и строки к соответствующим отрицательным элементам разрешающей строки.

     4. Находят новый псевдоплан и повторяют все действия начиная со второго этапа.

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

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

     Метод решения таких задач, предложенный Гомори, основан на симплексном методе и состоит в следующем. Симплексным  методом находится оптимальный  план задачи без учета условия  целочисленности. Если оптимальный план целочисленный, то вычисления заканчивают; если же оптимальный план содержит хотя бы одну дробную компоненту X_i, то накладывают дополнительное ограничение, учитывающее целочисленность компонент плана, и вычисления симплексным методом продолжают до тех пор, пока либо будет найден целочисленный оптимальный план, либо доказано, что задача не имеет целочисленных оптимальных планов.

     Особенно  широкое распространение линейное программирование получило в экономике, так как исследование зависимостей между величинами, встречающимися во многих экономических задачах, приводит к линейной функции с линейными  ограничениями, наложенными на неизвестные. Линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: рационального использования сырья и материалов; задачи оптимизации раскроя; оптимизации производственной программы предприятий; оптимального размещения и концентрации производства; составления оптимального плана перевозок, работы транспорта; управления производственными запасами; и многие другие, принадлежащие сфере оптимального планирования.

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

     Сущность  линейного программирования состоит  в нахождении точек наибольшего  или наименьшего значения некоторой  функции при определенном наборе ограничений, налагаемых на аргументы  и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных, которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции, называется оптимальным планом задачи.

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

     Линейное  программирование – наиболее разработанный  и широко применяемый раздел математического  программирования.  

1.4 Алгоритм симплекс  метода 

     Симплексный метод решения задач линейного  программирования – вычислительная процедура, основанная на принципе последовательного  улучшения решений – перехода от одной базисной точки  к другой, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум.

     Симплекс-метод  был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.

     Симплекс-метод является основным в линейном программировании. Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число шагов (за исключением т. н. вырожденной задачи, при которой возможно явление “зацикливания”, т. е. многократного возврата к одному и тому же положению). Название метод получил от термина “n-мерный симплекс”. Геометрическая интерпретация метода состоит в последовательном движении по вершинам симплекса.

     Процесс применения симплексного метода предполагает реализацию трех его основных элементов:

     1) способ определения какого-либо  первоначального допустимого базисного  решения задачи;

     2) правило перехода к лучшему  решению; 

     3) критерий проверки оптимальности  найденного решения. 

     Симплексный метод включает в себя ряд этапов и может быть сформулирован в  виде четкого алгоритма. Это позволяет  успешно программировать и реализовывать  его на ЭВМ. Задачи с небольшим  числом переменных и ограничений  могут быть решены симплексным методом  вручную.

     Алгоритм  симплекс-метода позволяет также  установить, является ли задача линейного  программирования разрешимой.

     Алгоритм:

     - Исходная модель задачи линейного  программирования приводится к  канонической форме и определяются базисные и небазисные переменные.

     - Заполняется симплексная таблица.  Пример симплексной таблице к  математической модели показан в таблице 1. В столбике с_i записываются коэффициенты взятые из целевой функции при базисных переменных. В строке с_j – коэффициенты взятые из целевой функции. В столбце «Базис» – базисные переменные. В столбце В – свободные числа (правые части ограничений). Под переменными х₁, х₂, …,х_n записываются коэффициенты взятые из ограничений при этих переменных. В нижней строке Z таблицы располагаются значение целевой функции, а в остальных кроме последней относительные оценки каждой переменной. Значение целевой функции вычисляется как сумма произведений с_j и В. Аналогично вычисляются все относительные оценки с минус коэффициент с_j.

     - Задача решается до тех пор пока:

     а) все относительные оценки неотрицательны в этом случае задача уже решена;

     б) среди относительных оценок соответствующих  исходным переменным есть 0, задача имеет  бесконечное множество решений;

     в) среди относительных оценок нет  отрицательных чисел, но в базисе есть искусственные переменные (задача не имеет решений);

     г) среди относительных оценок есть отрицательные (задача еще не решена, переход к следующей операции).

     - Переход к следующей итерации  начинается с выбора главного  столбца. Он соответствует наибольшему по модулю относительной оценки (выбираются только отрицательные оценки). Поиск главной строки выполняется следующим образом: числа столбца В делятся на числа главного столбца (0 и отрицательные числа в главном столбце пропускаются) результаты деления записываются в столбец Q. Главная строка соответствует минимальному Q. На пересечении главного столбца и главной строки находится главный элемент таблицы.

     - Пересчет таблицы. Переход к  новой итерации. Вместо переменной  главной строки и ее коэффициента  записывается переменная главного  столбца и ее коэффициент (переменная  входит в базис). Все числа главной  строки делятся на главный  элемент. Все остальные числа  главного столбца заполняются  0. Все остальные ячейки таблицы  вычисляются по правилу прямоугольника. Правило прямоугольника - из произведения  чисел главной диагонали вычитается  произведение побочной диагонали и результат делится на главный элемент. Диагональ проходящая через главный элемент называется главной диагональю.

- Вычисляется  значение целевой функции и  относительных оценок.

- Переход  к проверке оптимальности найденного  решения. Если не оптимально, то переход к следующей итерацие. 
 

     Таблица 1 – Пример симплексной таблицы к математической модели