Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

[pic] (2.4)

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

[pic] (2.5)

[pic], где [pic]

(2.6)

В канонической форме задачи линейного программирования необходимо, чтобы все компоненты искомого вектора Х были неотрицательными, а все остальные ограничения записывались в виде уравнений. Т.е. в задаче обязательно будут присутствовать условия вида (2.3) и 8 уравнений вида
(2.2), обусловленных неравенствами (2.5), (2.6).

Число ограничений задачи, приводящих к уравнениям (2.2) можно уменьшить, если перед приведением исходной задачи (2.4) - (2.6) к канонической форме мы преобразуем неравенства (2.6) к виду (2.3). Для этого перенесем свободные члены правых частей неравенств (2.6) в левые части.
Таким образом, от старых переменных [pic] перейдем к новым переменным[pic], где [pic]:

[pic], [pic].
Выразим теперь старые переменные через новые

[pic], [pic] (2.7) и подставим их в линейную форму (2.4) и в неравенства (2.5), (2.6). Получим

[pic]

[pic]

[pic], где [pic].
Раскрывая скобки и учитывая, что

[pic] (2.8), можем окончательно записать:

[pic] (2.9)

[pic] (2.10)

[pic], где [pic]

(2.11)

Путем несложных преобразований задачу (1.2.1), (1.2.2) свели к задаче
(2.9) - (2.11) с меньшим числом ограничений.

Для записи неравенств (2.10) в виде уравнений введем неотрицательные дополнительные переменные [pic], и задача (2.9) - (2.11) запишется в следующей эквивалентной форме:

[pic] (2.12)

[pic] (2.13)

[pic], где [pic]

Задача (2.12), (2.13) имеет каноническую форму.

3. Нахождение начального опорного плана с помощью L-задачи

Начальный опорный план задачи (2.1) - (2.3), записанной в канонической форме, достаточно легко может быть найден с помощью вспомогательной задачи
(L-задачи):

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





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата