Целевая функция (2) выражена через все переменные, но используя (6), мы можем все базисные переменные выразить через свободные и переписать (2) в виде

(2’) (7)

На заданном базисном решении целевая функция равна .

Попробуем улучшить данное решение путем изменения какой-либо свободной переменной, оставляя другие равными 0. Изменение целевой функции и базисных переменных можно наблюдать по формулам (8) и (9):

 

(8)

 

(9)

Ясно, что для улучшения плана годится только такая переменная x_{i ,} при которой коэффициент из формулы (9) меньше 0. Очевидно, если такой переменной нет, то данное базисное решение улучшить нельзя, и оно является оптимальным. Поэтому предположим, что g_I< 0. Если мы будем устремлять , то целевая функция неограниченно уменьшаться. Однако базисные переменные, изменяющиеся по формуле (8) могут выйти из естественных ограничений, что и ограничивает увеличение x_i.

Наблюдая за базисными переменными, мы можем ограничиться только теми, у которых a_ij< 0. Рассмотрим базисную переменную с номером k+j₀, где

.

Очевидно, именно она первой обратиться в нуль при увеличении x_i.. Тогда максимально возможное значение x_i равно

;

Теперь можно перейти к новому базисному решению, в котором и x_i меняются местами – переменная становится свободной, а x_i - базисной. Новое значение целевой функция станет равным

.

Для того, чтобы продолжить указанный процесс мы должны:

- выразить переменные x_i через новые свободные переменные. Для этого воспользуемся уравнением:

,

с помощью которого получим

(10)

- во всех остальных уравнениях системы (6) заменить x_i по формуле (10), тем самым мы получим новую систему вида (6), в которой все базисные переменные выражены через новые свободные.

- в (9) заменим x_i по формуле (10) и, приведя подобные члены, получим новое выражение вида (9).

 

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

 

З А Д А Н И Е

 

1. Изучить по конспекту лекций и предлагаемой литературе основные понятия и определения теории линейного программирования [1].

2. Ознакомиться по предлагаемой литературе с классификацией задач теории линейного программирования.

3. Ознакомиться с алгоритмом симплекс-метода решения ОЗЛП.

5. Составить и отладить программу на языке Паскаль, реализующую алгоритм симплекс-метода решения ОЗЛП.

6. Оформить отчет по выполненной лабораторной работе.

 

С О Д Е Р Ж А Н И Е О Т Ч Е Т А

 

Отчет должен содержать следующие обязательные части:

1. Алгоритм решения задачи.

2. Листинг текста программы на языке Паскаль, реализующей

алгоритмов симплекс-метода решения ОЗЛП.

3. Листинг протокола работы программы решения задачи, предложенной преподавателем.

 

К О Н Т Р О Л Ь Н Ы Е В О П Р О С Ы

 

1. Какие задачи планирования и управления относят к задачам

линейного математического программирования?

2. Приведите определения и постановки основных классов задач линейного программирования.

3. Изложите идею симплекс-метода решения ОЗЛП.

4. Каковы особенности построения исходного базисного решения.

 

СПИСОК ЛИТЕРАТУРЫ

 

1. Зайченко Ю.П. Исследование операций. - К.: Выща шк., 1988.-

552 стр.