Материал: Учебное пособие Немирко Манило

1.ОПТИМИЗАЦИЯ ПРИНЯТИЯ РЕШЕНИЙ

ВАСУ ЗДРАВООХРАНЕНИЯ МЕТОДОМ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.1.Формулировка задачи линейного программирования

Любая задача линейного программирования (ЛП) может быть сведена к его основной задаче, формулируемой математически следующим образом. Имеется ряд переменных x1, x2, , xn . Требуется найти такие неотрицатель-

ные значения этих переменных, которые бы удовлетворяли системе линейных уравнений:

где a11, a12, , amn; c1, c2, , cn – заданные постоянные коэффициенты. Очевидно, случай, когда линейную функцию нужно обратить не в ми-

нимум, а в максимум, легко сводится к предыдущему, если изменить знак функции и рассмотреть вместо нее функцию

L′= −L = −c1x1 −c2x2 − −cn xn.

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

x1 ≥ 0, x2 ≥ 0, , xn ≥ 0 ,

удовлетворяющую уравнениям (1.1).

Оптимальным решением называется то из допустимых решений, при котором линейная функция (1.2) обращается в минимум.

Основная задача ЛП необязательно должна иметь решение. Может оказаться, что уравнения (1.1) противоречат друг другу; может оказаться, что они имеют решение, но не в области неотрицательных значений x1, x2, , xn . Тогда основная задача ЛП не имеет допустимых решений.

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

6

Рассмотрим вопрос о существовании допустимых решений основной задачи ЛП. Для его решения можно исключить из рассмотрения линейную функцию L , которую требуется минимизировать, – наличие допустимых решений определяется только уравнениями (1.1). Остановимся на некоторых положениях линейной алгебры, рассматривающих этот вопрос.

Матрицей системы линейных уравнений (1.1) называется таблица, со-

Расширенной матрицей системы линейных уравнений называется та же матрица, дополненная столбцом свободных членов:

am1 am2 amn bm

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

В линейной алгебре доказывается, что для совместности системы линейных уравнений (1.1) необходимо и достаточно, чтобы ранг матрицы системы был равен рангу ее расширенной матрицы. Этот общий ранг r называется рангом системы: он представляет собой число линейно независимых уравнений среди наложенных ограничений.

Очевидно, ранг системы r не может быть больше числа уравнений m :

r ≤ m.

Очевидно также, что ранг системы не может быть больше общего числа переменных n :

r ≤ n .

Ранг матрицы системы определяется как наибольший порядок определителя, составленного из элементов матрицы; так как число ее строк равно m , то r ≤ m ; так как число ее столбцов равно n , то r ≤ n .

7

Структура задачи линейного программирования существенно зависит от ранга системы ограничений (1.1). Рассмотрим прежде всего случай, когда r = n , т. е. когда число линейно независимых уравнений, входящих в систему (1.1), равно числу переменных n . Если отбросить уравнения, являющиеся линейными комбинациями других, система уравнений-ограничений основной задачи ЛП принимает вид

не равен нулю. В этом случае система (1.3) имеет единственное решение. Чтобы найти величину xi , достаточно в определителе ∆ заменить i -й столбец столбцом свободных членов и разделить его на ∆.

Итак, при r = n система уравнений-ограничений основной задачи ЛП имеет единственное решение x1, x2, , xn . Если в этом решении хотя бы одна из величин x1, x2, , xn отрицательна, это означает, что полученное решение недопустимо и, значит, основная задача ЛП не имеет решения.

Если все величины x1, x2, , xn неотрицательны, то найденное решение является допустимым. Оно же является и оптимальным (потому что других нет).

Очевидно, что этот тривиальный случай не представляет интереса. Поэтому будем рассматривать только случай, когда r < n , т. е. когда число независимых уравнений, которым должны удовлетворять переменные x1, x2, , xn , меньше числа самих переменных. Тогда, если система сов-

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

8

Вообще, если ранг системы уравнений основной задачи ЛП (т. е. число линейно независимых уравнений, входящих в систему ограничений) равен r , то всегда можно выразить какие-то r базисных переменных через n −r остальных (свободных) и, придавая свободным переменным любые значения, получить бесчисленное множество решений системы.

При записи ограничений основной задачи ЛП в виде системы линейно независимых уравнений ранг системы r будет равен числу уравнений m .

Итак, если число уравнений основной задачи ЛП r = m меньше, чем число переменных n , то система линейных уравнений имеет бесчисленное множество решений, т. е. совокупностей значений x1, x2, , xn , удовлетво-

ряющих уравнениям-ограничениям (1.1). Если среди этих решений нет ни одного, для которого все x1, x2, , xn неотрицательны, это значит, что ос-

новная задача ЛП не имеет допустимого решения.

Если же существуют какие-то решения системы (1.1), для которых все x1, x2, , xn неотрицательны, то каждое из них допустимо. Возникает задача – найти среди допустимых решений оптимальное, т. е. такое решение x1, x2, , xn , для которого линейная функция (1.2) обращается в минимум.

Существует общий, часто применяемый симплекс-метод решения основной задачи ЛП, направленный на отыскание оптимального решения, но для частных задач (например, транспортных) существуют более простые методики [7]. Если число переменных n на 2 больше числа независимых уравнений m , которым они должны удовлетворять, т. е. если n −m = 2 , то можно решить задачу ЛП геометрическим способом.

На практике ограничения в задаче ЛП часто задаются не уравнениями, а неравенствами. Рассмотрим, как можно перейти от задачи с ограниченияминеравенствами к основной задаче ЛП.

Пусть имеется задача ЛП с n переменными x1, x2, , xn , в которой

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

9

Будем считать, что все эти неравенства линейно независимы (т. е. никакое из них нельзя представить в виде линейной комбинации других). Требуется найти такую совокупность неотрицательных значений x1, x2, , xn , ко-

торая удовлетворяла бы неравенствам (1.4), и, кроме того, обращала бы в минимум линейную функцию

L = c1x1 +c2x2 + +cn xn .

От задачи, поставленной таким образом, легко перейти к основной задаче ЛП. Введем обозначения:

где y1, y2, , ym – некоторые новые переменные, которые принято называть добавочными. Согласно условиям (1.4), эти добавочные переменные так же, как и x1, x2, , xn , должны быть неотрицательными.

Таким образом, возникает задача линейного программирования в следующей постановке: найти такие неотрицательные значения n +m переменных x1, x2, , xn ; y1, y2, , ym , чтобы они удовлетворяли системе уравнений (1.5) и одновременно обращали в минимум линейную функцию этих переменных

L = c1x1 +c2x2 + +cn xn .

Как видно, перед нами в чистом виде основная задача ЛП. Уравнения (1.5) заданы в форме, уже разрешенной относительно базисных переменных y1, y2, , ym , которые выражены через свободные переменные

x1, x2, , xn . Общее число переменных равно n +m , из них n исходных

(свободных) и m добавочных. Функция L выражена только через свободные переменные (коэффициенты при добавочных переменных в ней равны нулю).

Таким образом, задача ЛП с ограничениями-неравенствами сведена к основной задаче ЛП, но с большим числом переменных, чем первоначально было в задаче.

Всегда возможен и обратный переход – от основной задачи ЛП к задаче с ограничениями-неравенствами. Если в первом случае число переменных увеличивается, то во втором оно будет уменьшаться.

10