Решение основной задачи

Найти максимум функции

lt;11Л2gt;

У=1

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

п

/ = 1..... от; (11.13)

#9632;М

П

X Д/у */lt;pound;/, / = /и + 1,...,р; (1114)

У-1

XjZOi ] = 1,...,/1.

Задача (11.12)—(11.15) называется основной. Предполагается, что pound; О,

/ = 1

Стратегия поиска

Для решения основной задачи симплекс-методом она должна быть приве­дена к канонической задаче путем введения в каждое ограничение по одной дополнительной переменной: в каждое ограничение-неравенство со знаком lt; вводится дополнительная переменная со знаком “+”(она становится базисной), а в каждое о1раничение-неравенство со знаком pound; вводится дополнительная переменная со знаком

Каноническая задача записывается следующим образом

/(*) = pound; с, -gt; шах, (11.16)

М

п

pound;»/./*/-*«+/”*/gt;.............................. / = 1 тgt; (1117)

gt;1

п

Уpound;аих J+^n+i_=blgt; lt; = « +1 Р\ (11.18)

Так как в общем случае в уравнениях (11.17) нет базисных переменных, то для того, чтобы можно было применить симплекс-метод, делается переход к М- задаче. В каждое из т уравнений (11.17) вводится искусственная переменная со знаком “ + ’’(она становится базисной), а к целевой функции добавляется сумма

искусственных переменных, умноженная на М ”. В результате получаем зада­

чу в расширенной форме:

п т

/(*) = Z cixi - М Z Хп+Р+1 -* •

;=1 -1

П

“ xn+i + xn+p+i = / = 1,..., /Я,

7=1

п

lLaijxj + xn+i = bi » / = /я + 1,...,р;

7=1

хх *0,...,хп+р+т ^0.

Замечания 11.3.

1. Если решается задача поиска минимума целевой функции (11.12), то при переходе к М- задаче перед числом 71/в (11.20) ставится знак “+ ”.

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