Шпаргалки по "Основам эконометрики и математического моделирования"

2.Виды записи задачи ЛП. Способы преобразования.

ЗЛП в общей постановке имеет 3 формы: произвольную, симметричную и каноническую.

1. Произвольная форма ЗЛП имеет вид (4.2):

   Выражение    называется целевой функцией (или критерием) задачи. Величины (Х1, Х2, …, Хn) – переменные задачи. Система неравенств в задаче (4.2) определяет область допустимых значений (планов) задачи D, которая имеет форму выпуклого многогранника. Неравенства и равенства в задаче (4.2) называются ограничениями. Каждое неравенство определяет полупространство, а равенство – плоскость в пространстве переменных (Х1, Х2, …, Хn).

Решение задачи (4.2) называется оптимальным решением (или оптимальным планом) и обозначается как Х* = (Х*1, Х*2, …, Х*n). Оптимальные решения лежат на границе области D. Если область D ограничена, то задача ЛП имеет либо единственное, либо бесконечно много решений. Если решение единственно, то оно совпадает с одной из вершин многогранника D. Если градиент целевой функции c = (с1, с2, …, сn) коллинеарен градиенту одного из ограничений, то задача имеет бесконечно много решений, лежащих на данном ограничении. Если ограничения несовместны, или целевая функция неограниченна, то задача (4.2) не имеет решения. Если область области D не ограничена, то решение может существовать либо быть неограниченным. Всякая задача на минимум может быть сведена к задаче на максимум и наоборот, умножением целевой функции на   –1. Оптимальный план задачи при этом не изменится, а значение целевой функции изменит знак. После решения надо снова изменить знак целевой функции.

2. Симметричная форма ЗЛП на максимум имеет вид (4.3):

Симметричная  форма задачи на минимум имеет  вид (4.4):

Если все Bi ≥ 0, то задача (4.3) обычно имеет следующий экономический смысл: − Xj объемы производства j-го вида продукции, − Ci цены или прибыль единицы продукции, − Аij нормативы затрат i-го вида ресурса на производство единицы j-го вида продукции, − Bi имеющийся запас i-го вида ресурса. Надо определить план производства продукции Х* = (Х*1, Х*2, …, Х*n), который дает максимальную выручку или прибыль, при заданных ограничениях на имеющиеся ресурсы. Ограничения, на которых в оптимальном плане достигнуто равенство, соответствуют дефицитным ресурсам, остальные ресурсы называются недефицитными.

3. Каноническая форма ЗЛП представлена ниже (4.5 :

Из линейной алгебры  известно, что количество линейно  независимых уравнений не может быть больше числа неизвестных. Поэтому в (4.5) можно считать, что n ≥ m.

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

Опорным планом называется любой вектор Х = (Х1, Х2, …, Хn), удовлетворяющий условиям (4.5) и имеющий не более чем m ненулевых компонент. Если в канонической форме все bi ≥ 0, то задача (4.5) имеет опорный план, в котором базисные переменные равны bi, а остальные (свободные) переменные равны 0. Такой план называется начальным опорным планом.

Балансовой называется переменная, которая добавляется или вычитается из левой части неравенства для получения равенства. В задачах (4.3), (4.4) балансовые переменные будут базисными. Любая форма ЗЛП приводится к канонической форме с помощью следующих преобразований:

• замена переменной, которая принимает произвольные значения, на разность двух новых положительных переменных;

• введение балансовых переменных.

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

Пример 4.1. Пусть задача ЛП имеет вид (4.6):

Чтобы привести ее к канонической форме, сделаем подстановку а в неравенства введем балансовые переменные x4,x5 и искусственную переменную x6 . Тогда М-задача для (4.6) будет иметь вид (4.7):