Курсовая работа: Использование среды MatLAB для решения линейной программы

Если к тому же учесть, что число положительных (базисных) компонент опорного плана должно оставаться равным m, то одну из первых m (ненулевых) компонент исходного плана обращаем в нуль выбором

 (2.12)

Подставляя (2.11) в (2.1), имеем

 (2.13)

Если обозначить

, (2.14)

, (2.15)

то (2.13) примет вид

 (16)

Из полученных соотношений напрашиваются следующие выводы.

Критерий 1 (критерий оптимальности). Если все Dk ³ 0, то выбранный план для задачи максимизации является оптимальным.

Критерий 2. Если обнаруживается некоторое Dk < 0 и хотя бы одно из значений Zjk >0, то переход к новому плану увеличит значение целевой функции.

Этот вывод с очевидностью следует из (2.16); в такой ситуации согласно (2.12) полагаем k-ю переменную равной Q и преобразуем значения остальных (базисных) переменных в соответствии с (2.11).

Критерий 3. Если обнаруживается некоторое Dk < 0, но все Zjk£0, то линейная форма задачи не ограничена по максимуму.

Этот вывод следует из того, что согласно (2.11) компоненты нового плана сохраняют неотрицательность при любом Q>0 (в том числе и при сколь угодно большом) и согласно (2.16) появляется возможность неограниченного изменения значения целевой функции.

Предположение о том, что базисными являются первые m компонент плана, не является принципиальным, и указание диапазона по j от 1 до m в (2.11)-(2.15) можно заменить на указание о принадлежности к базису “jÎБ“.

Если все опорные планы задачи являются невырожденными (число положительных компонент равно m), то Q отлично от нуля и переход к новому плану согласно (2.16) изменяет значение целевой функции, что гарантирует достижение экстремума за конечное число шагов. При наличии вырожденных планов возможно т. н. зацикливание (возврат к ранее рассмотренным планам), но на практике зацикливание никогда не возникало.

2.2 Прямой алгоритм симплексного метода [1]

Пусть исходная задача приведена к канонической форме и начальный базис образует единичную матрицу. Тогда базисные компоненты опорного плана совпадают с правыми частями ограничений и коэффициенты Zjk разложения вектора Xk по такому базису совпадают с компонентами этого вектора.

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

Страницы: 1, 2, 3, 4