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

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

Методы линейного программирования применяют к практическим задачам, в которых:

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

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

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

Модель задачи линейного программирования может быть записана в одной из приведенных ниже форм:

1. Общая или произвольная форма записи задачи линейного программирования:

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

 – произвольные

2.  Симметричная или стандартная форма записи задачи линейного программирования:

3. Каноническая или основная форма записи задачи линейного программирования:

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

Так, при необходимости задачу минимизации можно заменить задачей максимизации, и наоборот.

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

преобразуются в ограничения-равенства путем прибавления (вычитания) к левым частям дополнительных (балансовых) неотрицательных переменных :

В случае необходимости ограничение-равенство

можно записать в виде системы неравенств:

Если в задаче линейного программирования какая-то переменная  не подчинена условию неотрицательности, ее заменяют разностью двух других неотрицательных переменных  и :

Способы решения задач линейного программирования подробно рассмотрены на соседних страницах сайта:

• графический метод
• симплексный метод
• транспортная задача