Методы решения задач линейного программирования (1006299), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Алгоритм перехода от табл. 3.1 к табл. 3.2 состоит в следую­щем:

1. все элементы разрешающего столбца s, кроме разрешаю­щего элемента, меняют знак на противоположный;

2. элементы разрешающей строки r делятся на ;

3. элементы разрешающего столбца s делятся на ;

4. остальные элементы вычисляются по формуле:

Если решается задача на максимум функции f(X), то в по­следней строке записываем выражение для «f= », на минимум f(X) — для «-f=».

2. Находим допустимое базисное решение.

Так как все , то в качестве допустимого базисного решения примем следующее: все небазисные пе-

После выбора разрешающих столбца s и строки r проводим шаг модифицированного жорданова исключения с разрешающим элементом a_rs, помечаемым в таблице символом «*». Данный шаг избавляет от отрицательного элемента в f-строке столбца s (- с_s при поиске максимума f(X) и c_s при минимуме). Эти ша­ги повторяем до тех пор, пока все элементы в f-строке в небазис­ных столбцах не станут неотрицательными. Тогда решение ЗЛП заканчиваем, и в качестве оптимального решения принимаем сле­дующее: все небазисные переменные (те х_i и y_j , которые стоят в небазисных столбцах в первой строке полученной таблицы на последней итерации) равны нулю, а все базисные переменные (все х_i и y_j из базисного столбца на последней итерации) равны свободным членам, находящимся в той же строке. Оптимальное значение функции при этом равно значению свободного члена в f-строке со знаком плюс при нахождении максимума или минус при поиске минимума.

Отметим, что если на некоторой итерации к в f-строке в небазисном столбце получен нулевой элемент, то это является признаком множества оптимальных решений данной ЗЛП. Тогда не­обходимо провести еще одну итерацию к + 1 (с выбором небазисного столбца с нулевым элементом в f-строке в качестве разреша­ющего столбца), чтобы найти вторую оптимальную точку с тем же значением функции в ней, что и в точке - на предыду­щей итерации к. На итерации к + 1 в f-строке в небазисном стол­бце тоже будет получен нулевой элемент. Оптимальным решением этой ЗЛП является все множество точек отрезка , параллельного линии уровня функции f(X)=c₀.

4. Конец алгоритма.

Симплекс-метод Данцига для решения ЗЛП общего вида

при т ограничениях типа « »:

Решается задача

3. Искусственная функция w нужна для нахождения на на­чальных итерациях базисных решений вплоть до нахождения пер­вого допустимого базисного решения, при котором функция w ста­новится равной нулю, как и все искусственные переменные (пол­учается первоначальный вид ограничений). Затем находится опти­мальное решение ЗЛП с оптимальным значением функции f. По­этому решение ЗЛП выполняем в два этапа:

3.1. Проводим итерации, начиная с нулевой (заключающиеся в выборе разрешающего элемента и осуществлении шага модифици­рованного жорданова исключения с этим элементом), по миними­зации функции w. Этот этап заканчиваем, когда w становится равной нулю (стоящему в строке — w в столбце свободных чле­нов), а все искусственные переменные — небазисными, т.е. тоже равными нулю. Следовательно, в этом случае в строке -w будут стоять все нули, за исключением столбцов, соответствующих искус­ственным переменным, там будут 1. Тогда вычеркиваем строку —w и столбцы, соответствующие искусственным переменным.

Отметим, что если не удается свести w к нулю, а все элементы в строке —w в небазисных столбцах больше или равны нулю, то это является признаком недопустимости решения рассматриваемой ЗЛП. Не существует области XD допустимых значений X и реше­ния данной ЗЛП. В этом случае переходим к п. 4.

3.2. Продолжаем итерации уже по оптимизации функции f(X). Завершаем, когда все элементы в этой строке в небазисных столбцах становятся больше нуля (или все больше нуля, кроме одного нулевого элемента, тогда проводим еще одну последнюю итерацию).

4. Конец алгоритма.

11

Характеристики

Список файлов ответов (шпаргалок)