Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 24 стр.

Линейное программирование


точкой исходной задачи. Она, как и в предыдущем случае, вообще говоря, не
является оптимальной. Следовательно, необходимо продолжить поиск, не
уменьшая при этом полученное оптимальное значение β 0 =0 . По оценкам
α j <0 (если такие есть) определяется вектор для введения в базис на данной
итерации. Процесс продолжается до тех пор, пока не исчезнут такие j, что
α j <0, β j =0, соответствующий столбец Aj имеет элементы aij>0.
      Итак, сформулируем окончательный алгоритм решения произволь-
ной задачи линейного программирования.

1. Привести задачу к каноническому виду.
2. Проверить наличие единичного базиса среди столбцов матрицы ограниче-
   ний. Если единичный базис имеется, то перейти к п.5.
3. Ввести в задачу искусственные переменные так, чтобы среди столбцов
   полученной матрицы появился единичный базис в пространстве Rm , где m
   - число ограничений задачи.
4. Составить М - задачу: ввести искусственные переменные в целевую
   функцию с коэффициентами, равными - М.
5. Составить исходную таблицу для оформления решения задачи. Если дан-
   ный пункт выполняется после пункта 2, то фрагмент таблицы завершается
   одной оценочной строкой, если после пункта 4, то двумя строками для
   оценок ∆ j =α j +Mβ j (первая - для чисел α j , вторая - для β j ).
6. Вычислить оценки всех векторов-ограничений задачи по формулам
   ∆ j =∑ ci aij −c j При наличии искусственных векторов в базисе получим
        i∈I
   выражения вида α j +M βj . Поместить α j в первую оценочную строку,
    β j - во вторую (нижнюю).
7. При наличии двух оценочных строк проверить, если все β j ≥0, то перей-
   ти к п.11, иначе - к п.9 с числами β j . Если осталась одна оценочная стро-
   ка, то проверить условие ∆ j ≥0 . Если это условие выполняется, то пе-
   рейти к п.12.
8. Просмотреть векторы-столбцы Aj, для которых α j <0. Если среди них су-
   ществует такой, что все его координаты aij ≤ 0, то перейти к п.13, иначе -
   к п.9 с числами ∆ j =α j .
9. Определить направляющий элемент для выполнения итерации по мето-
   дуЖордана-Гаусса. Номер столбца k может быть выбран любым среди тех
   j, для которых ∆ j < 0. Номер строки l определяется следующим образом:
 xl            x
     =min i , где x i - базисные координаты проверяемой базисной точки,
alk     aik >0 aik
a lk - направляющий элемент.


                                    26