Методы оптимизации. Рейзлин В.И. - 28 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

Умножим второе ограничение на
1
, для обеспечения условия
неотрицательности свободных членов в системе ограничений:
5xx3
2xx2x4
1xxx2
31
321
321
.
Введем в первое неравенство дополнительную переменную 0x
4
со
знаком «плюс», во второе - 0x
5
и в третье - 0x
6
также со знаком «плюс». В
результате получим систему ограничений задачи в стандартной форме:
5xxx3
2xxx2x4
1xxxx2
631
5321
4321
.
При этих ограничениях нужно найти минимальное значение функции с
обратными коэффициентами:
321
x3xxZ
.
2.2 Понятие плана задачи линейного программирования
Для задачи ЛП, представленной в стандартной форме, введено понятие
плана.
Планом, или допустимым решением задачи линейного
программирования, называется вектор
n21
x,,x,x
X ,
удовлетворяющий условиям (2.2), (2.3) и (2.4).
План называется опорным, если векторы
i
A
m,,2,1i
, входящие в
разложение вида (1.5) с положительными коэффициентами
i
x (для
стандартной формы), являются линейно независимыми. Число
положительных компонент опорного плана не может превышать
m
.
Опорный план называется невырожденным, если он содержит
m
положительных компонент, в противном случае опорный план называется
вырожденным.
Оптимальным планом или оптимальным решением задачи линейного
программирования называется план, доставляющий наименьшее значение
линейной функции (2.1).
Множество всех планов задачи линейного программирования (если они
существуют) является выпуклым многогранником. Каждой угловой точке
многогранника решений соответствует опорный план. Каждый опорный

Страницы