Оптимизация задач при линейном программировании

Задачами линейного программирования называются оптимиза -ционные задачи, в которых ограничения в виде равенств или неравенств и целевая функция (оптимизируемая) - линейны. Методы линейного программирования широко используются для решения различных военных, экономических, промышленных и организационных задач. Линейное программирование представляет собой наиболее часто используемый метод оптимизации (74% общего числа методов оптимизации).

В основном в таких задачах требуется ответить на вопрос: как распорядиться ограниченными ресурсами, чтобы добиться наибольшего эффекта.

В стандартной или канонической форме с m ограничениями и n переменными она имеет следующий вид:

Максимизировать или минимизировать

z=c₁x₁+c₂x₂+…+c_nx_n

при ограничениях

a₁₁x₁+a₁₂x₂+…a_1nx_n=b₁,

………………………

………………………

a_m1x₁+a_m2x₂+…+a_mnx_n=b_m,

x₁≥0, х₂≥0,…х_n≥0,

b₁≥0, b₂≥0,…b_m≥0.

И в других формах записи:

a) , j (1,2…n),

, i (1,2…m),

x_j ≥0, b_i ≥0, m<n,

б) Z=CX, AХ=B, X≥0, B≥0,

где А – матрица размерности m n; B – вектор столбец размерности m 1, а C – вектор строка размерности 1 n, Х – вектор (столбец) переменных (другое их название соответственно: матрица коэффициентов, вектор ресурсов, вектор оценок задачи, вектор переменных).

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

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

Преобразование неравенств. Ограничения в виде неравенств преобразуются в равенства при помощи избыточных (остаточных) переменных. Например, неравенство вида

х₁+2х₂+3х₃+4х₄+х₅≤25

можно преобразовать в равенство при помощи остаточной переменной х₅:

х₁+2х₂+3х₃+4х₄+х₅=25.

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

Преобразование неограниченных по знаку переменных. Поскольку переменные задач линейного программирования в стандартной форме предполагаются неотрицательными, неограниченные по знаку следует заменять разностью двух неотрицательных переменных. Например, если x_j – неограниченная по знаку переменная, то используется следующая замена переменных (при n – компонентном векторе переменных): x_j=x_n+1–x_n+2, где x_n+1, x_n+2 – неотрицательные дополнительные переменные. Знак x_j зависит от числовых значений дополнительных переменных.

Пример приведения задачи линейного программирования к стандартной форме: минимизировать z=x₁-2x₂+3x₃ при ограничениях:

x₁+x₂+x₃≤7,

x₁-x₂+x₃≥2,

3x₁-x₂-2x₃= –5,

x₁,x₂>0,

где х₃ переменная, не ограниченная по знаку.

Решение:

1. Заменим х₃ на х₄-х₅, где х₄,х₅>0.

2. Умножим обе части третьего уравнения на (-1).

3. Введем дополнительные (остаточные) переменные х₆ и х₇ в первые два ограничения.

4. Целевая функция при этом не меняется, так в нее х₆ и х₇ входят с нулевыми коэффициентами.

Рассматриваемая задача равносильна следующей задаче линейного программирования в стандартной форме:

минимизировать z=x₁-2x₂+3x₄-3x₅,

при ограничениях x₁+x₂+x₄-x₅+x₆=7,

x₁-x₂+x₄-x₅-x₇=2,

-3x₁+x₂+2x₄-2x₅=5,

x₁,x₂,x₃,x₄,x₅,x₆,x₇≥0.

В матричных обозначениях: минимизировать Z=CХ при ограничениях АX=B, Х≥0.

Определения, касающиеся этой задачи:

1. Допустимое решение - неотрицательный вектор Х, для которого выполняется ограничение АХ=В.

2. Допустимая область – совокупность всех допустимых решений. Если допустимая область пуста, то система называется противоречивой (несовместной).

3. Оптимальное решение задачи соответствует оптимальному значению целевой функции.

4. Не единственность оптимального решения - наличие нескольких допустимых решений при оптимальном значении целевой функции.

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

6. Неограниченный оптимум – отсутствие конечного оптимума.

Каждое из неравенств, образующее математическую модель линейного программирования, определяет некоторое полупространство n-мерного пространства (n – число переменных), а все вместе – некоторую область Ω в нем, являющуюся пересечением конечного числа полупространств. Полупространства - выпуклые множества, их пересечение тоже выпукло, т.е. оно является выпуклым «многогранником». Число вершин его ограничено.

Теоретические разработки по линейному программированию указывают, что число решений (базисных) задач линейного программирования равно числу вершин «многогранника». При большой размерности n перебрать все возможные решения затруднительно, поэтому отыскание оптимального решения надо начинать с одного определенного базисного решения.

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

Алгоритм симплекс метода при оптимизации задачи линейного программирования:

1. Нахождение начального допустимого базисного решения.

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

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

Демонстрировать этот алгоритм лучше всего на конкретном примере. Минимизировать функцию z=x₄-x₅→min, если уже известен начальный допустимый базис:

x₁=1-x₄+2x₅,

x₂=2+2x₄-x₅,

x₃=3-3x₄-x₅,

x₁,x₂,x₃,x₄,x₅≥0.

Соответствующий ему опорный план будет (1,2,3,0,0), а целевая функция z=0. Исходная целевая функция свидетельствует о возможности снижения за счет увеличения небазисного переменного x₅. Увеличение х₅ не может перевести х₁ и х₂ в отрицательные значения (это видно из первого равенства), а из двух последующих следует, что возможно увеличение х₅ до 2. Тогда при сохранении х₄=0, х₃ оказывается равным 1 (положительному числу), а х₂=0, х₁=5. Новый опорный план –(5;0;1;0;2), а . Для перестройки исходной системы ограничений необходимо выразить новые базисные переменные через х₂, х₄ (небазисные):

x₅=2+2x₄-x₂ (из второго ограничения),

x₁=1-x₄+2(2+2x₄-x₂) (из первого ограничения),

x₃=3-3x₄-(2+2x₄-x₂) (из третьего),

z=x₄-(2+2x₄-x₂).

Теперь задача приводится к виду:

x₁=5+3x₄-2x₂,

x₃=1-5x₄+x₂,

x₅=2+2x₄-x₂,

x_i≥0, (i=1,2,3,4,5),

z=-2-x₄+x₂→min.

Исследование целевой функции на возможность ее снижения указывает, что это можно сделать только за счет увеличения x₄ при сохранении х₂=0. При этом первое и третье ограничения ничуть не препятствуют этому, а второе допускает увеличение x₄ до 1/5. При этом x₄=1/5, х₂=0, а из второго ограничения следует, х₃=0, из первого x₁=28/5, а из третьего – х₅=12/5. Новый опорный план (28/5;0;0;1/5;12/5), ограничения, соответствующие ему, через небазисные х₂, х₃:

Подстановка этого значения в два других ограничения дает:

Целевая функция при этом опорном плане:

z=-2-( )+х₂,

или

z=- .

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

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

Минимизировать целевую функцию

z=x₂-3x₃+2x₅

при ограничениях x₁+3x₂-x₃+2x₅=7

-2x₂+4x₃+x₄=12

-4x₂+3x₃+8x₅+x₆=10,

x_i≥0, (i=1,…,6).

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

x₁=7-3x₂+x₃-2x₅,

x₄=12+2x₂-4x₃,

x₆=10+4x₂-3x₃-8x₅,

x_i≥0 (i=1,…,6).

Исходный опорный план (7,0,0,12,0,10), а целевая функция

z -x₂+3x₃–2x₅=0.

Симплекс – таблица исходной системы при новой записи целевой функции:

В строке целевой функции (z) нет положительных элементов. Значит, полученное решение будет оптимальным: (0;4;5;0;0;11), а целевая функция равна (-11).

И еще одна оптимизация с иным ответом: минимизировать целевую функцию: z=2x₁-3x₄+x₅+2x₆

при ограничениях

x₁+x₂-3x₄+2x₆=5,

2x₂-3x₃+x₄+x₅=4,

-3x₁-x₂+2x₃-x₅=-3,

x_i≥0 (i=1,…,6).

Умножив на (-1) третье ограничение, получим систему в стандартной форме и запишем коэффициенты ограничений целевой функции (с обратными знаками), а также свободные члены в первый шаг симплекс-таблицы.

Проведем соответствующие преобразования.

В столбце с положительным коэффициентом целевой функции z (это +2) нет положительных элементов. Значит, функция не ограничена по минимальному значению.

В общем случае решение задач линейного программирования зависит от знаков z – строки симплекс-таблицы (при записи этих коэффициентов в нее в виде z-L=0):

1. При всех неположительных коэффициентах z-строки задача решена, оптимизация достигнута.

2. При наличии положительных коэффициентов в z-строке:

○ задача не имеет решения, если над каждым положительным коэффициентом z-строки находится только отрицательные или нулевые элементы;

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

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

Опыт решения большого числа практических задач показывает, что число итераций (шагов) при решении задач линейного программирования в стандартной форме с m ограничениями и n переменными лежит в пределах m…3m, при среднем значении 2m. Время, требуемое для решения, приблизительно пропорционально кубу числа ограничений (m³).

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