Глава II. Линейная алгебра в экономике

§ 1. Какие бывают задачи линейного программирования?

Задача линейного программирования (ЛП) является частным случаем задачи математического программирования. Ограничениями задачи ЛП являются линейные уравнения и линейные неравенства, т.е. уравнения вида

и неравенства вида

или

.

Линейно также должна быть целевая функция

Пример 1. Найти максимум функции

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

Определение 1. Задачей линейного программирования общего вида (общей формы) называется задача нахождения экстремума (т.е. максимума или минимума) линейной целевой функции

(1)

при ограничениях, являющихся линейными уравнениями (2) или линейными неравенствами (3)

(2)

(3)

Примечание. Неравенства в (3) могут иметь вид . Любое неравенство видаможно преобразовать в неравенство вида, умножая на – 1 обе части неравенства и меняя знак неравенства на противоположный.

Определение 2. Упорядоченный набор чисел , которые удовлетворяют всем уравнениям (2) и всем неравенствам (3), называетсядопустимым планом задачи линейного программирования (1), (2), (3).

Например, допустимыми планами задачи ЛП из примера 1 будут следующие векторы:

Вычислим значения целевой функции в этих точках:

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

План в этом случае называют оптимальным (наилучшим) планом.

Определение 3. Оптимальным планом задачи линейного программирования (1), (2), (3) с максимизируемой (минимизируемой) целевой функцией называется такой допустимый план, для которого будет выполняться следующие условие:

для всех допустимых планов выполняется неравенстводля задачи на максимум и неравенстводля задачи на минимум. Вернемся к примеру 1. Докажем, что план= (0; 1; 0) является оптимальным планом этой задачи. Пусть переменнаяимеет значение:. Посколькуи, то.

Из второго уравнения выразим

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

Для этого чтобы удовлетворить первому уравнению, следует взять

.

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

где .

Выразим через целевую функцию

Ясно, что максимального значения функция достигает при. При этом мы получаем оптимальный план

В этой задаче нам удалось очень просто найти оптимальный план, так как удалось вырезать через значение всех переменных.

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

Определение 4. Говорят, что задача ЛП имеет каноническую форму, если ограничения – неравенства (3) имеют вид: а остальные ограничения имеют вид уравнения (2).

Пример 2. Задача линейного программирования

имеет каноническую форму.

Определение 5. Говорят, что задача ЛП имеет стандартную форму, если все ограничения этой задачи записаны в форме неравенств.

Пример 3. Задача линейного программирования

имеет стандартную форму.

Приведем пример перехода от задачи общего вида к канонической форме.

Пример 4. Приведем к канонической форме задачу ЛП:

Необходимо два неравенства преобразовать в уравнения. Обозначим через разность между правой и левой частями первого неравенства:

Величина так как. Теперь первое ограничение можно записать в виде уравнения

Аналогично поступаем со вторым неравенством. Пусть

Тогда , и мы получаем уравнение

Величины иназываютбалансовыми переменными. Они не отрицательны. В неравенстве вида «» мы в левой части прибавили величинудля восстановления баланса (равенства) левой и правой частей этого ограничения. В неравенстве вида «» слева вычитается величинаПри этом восстанавливается баланс. В итоге получаем задачу ЛП в канонической форме:

(**)

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

Упражнение. Приведите к канонической форме задачу ЛП примера 3. Не встречалась ли ранее полученная задача?

Пример 5. Приведем к стандартной форме задачу линейного программирования:

Возьмем и. Можно выразить черезии другие переменные:

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

Выразим через ицелевую функцию

Получили задачу линейного программирования:

Эта задача имеет стандартную форму. Допустимому плану () этой задачи соответствует допустимый планисходной задачи. И наоборот, плануисходной задачи соответствует планстандартной задачи.

Если вернуться к обозначениям

то получится задача вида

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

Выводы:

1. Среди задач ЛП выделяются задачи канонической и стандартной форм. В задаче канонической формы должны быть неотрицательны все переменные, а ограничения имеют вид уравнений. В задаче стандартной формы все ограничения имеют вид неравенств.

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

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