Решение задач линейного программирования — страница 3

  • Просмотров 3495
  • Скачиваний 463
  • Размер файла 155
    Кб

суммируются также ХB1, и (-а1k)*ХBi;. Аналогичные действия производятся для всех остальных строк кроме i-ой (базисной) строки. В результате получается, что в i-ой строке k-го элемента стоит 1, а во всех ос-тальных его строках находится 0. Таким образом осуществляется шаг итерационального алгоритма, Шаги алгоритма симплекс-метода продолжаются до тех пор, пока не будет получен один из следующих результатов. • Все небазисные дельта-оценки

больше нуля — найдено решение задачи ли- нейного программирования, оно представляет из себя вектор компонент х;, значения которых либо равны нулю, либо равны элементам столбца Х, та-в кие компоненты стоят на базисных местах (скажем, если базис образуют пе-ременные х2, x4, х5, то ненулевые компоненты стоят в векторе решения зада-чи линейного программирования на 2-м, 4-м и 5-м местах). • Имеются небазисные дельта-оценки, равные нулю,

тогда делается вывод о том, что задача линейного программирования имеет бесчисленное множество решений (представляемое лучом или отрезком). Подробно рассматривать случаи такого типа, а также отличия между решениями в виде луча и отрезка мы не будем. • Возможен вариант получения столбца отрицательных элементов на отрица-тельной рассчитанной дельта-оценке, в такой ситуации нельзя вычислить тетта-оценки. В этом случае делается

вывод, что система ограничений задачи линейного программирования несовместна; следовательно, задача линейного программирования не имеет решения. Решение задачи линейного программирования, если оно единственное, следует записывать в виде Х* = (..., ..., ...) - вектора решения и значения целевой функ-ции в точке решения L*(Х*). В других случаях (решений много или они отсут-ствуют) следует словесно описать полученную ситуацию. Если

решение задачи линейного программирования не будет получено в течение 10-12 итераций симплекс-метода, то следует написать, что решение отсутствует в связи с неог-рачниченностью функции цели. Для практического решения задачи линейного программирования симплекс-методом удобно пользоваться таблицей вида (табл. 11.1): Таблица 1.1 B CB XB A1 … An Q Базисные Целевые Правые компоненты Коэффиц. Части Базиса ограничен D D1 Dn Задание Необходимо

решить задачу линейного программирования. L(x) = x1 – 2x2 + 3x3 x1 – 3x2 3 2x1 – x2 + x3 3 -x1 + 2x2 – 5x3 3 Все xi 0 i = 1, …3 1.      Для начала приведем задачу к каноническому виду: L(x) = x1 – 2x2 + 3x3 x1 – 3x2 + x4 = 3 2x1 – x2 + x3 + x5 = 3 -x1 + 2x2 – 5x3 + x6 = 3 Все xi 0 i = 1, …6 2.      Составляем таблицу симплекс-метода (табл. 1.2). Видно, что базис образуют компаненты x4, x5, x6: B CB XB A1 A2 A3 A4 A5 A6 Q A4 0 3 1 -3 0 1 0 0 - A5 0 3 2 -1 1 0 1 0 3 A6 0 3 -1 2 -5 0 0 1 - D -1 2 -3 0 0 0 A4 0 3 1 -3 0 1 0 0 A3 3 3 2 -1 1 0 1 0 A6 0 3 -1 2 0 0 0 1 D