Воронеж – 2002 г.
ЛАБОРАТОРНАЯ РАБОТА № 11
РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Цель работы:изучение принципов составления оценочных характеристик для задач линейного программирования, получение навыков использования симплекс-метода для решения задач линейного программирования, усвоение различий получаемых результатов, изучение табличной формы применения симплекс-метода.
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
Стандартная задача линейного программирования состоит из трех частей:
целевой функции (на максимум или минимум) - формула (1.1), основных oграничений
(1.1)
Алгоритм решения задач линейного программирования требует приведения их постановки в канонический вид, когда целевая функция стремится к максимуму (если стремилась к минимуму, то функцию надо умножить на -1, на станет стремиться к максимуму), основные ограничения имеют вид равенства (для приведения к равенствам в случае знака
переменной комбинацией x1k- х2k = хk, где х1k
Первая оценка - это дельта-оценка, для переменной хjона имеет вид:
Т.е. по номеру k, найденному по дельта-оценке, мы получаем выход на пере-менную хkи элементы столбца ХB делим на соответствующие (только положи
тельные) элементы столбца матрицы А, соответствующего переменой xk. Из полученных результатов выбираем минимальный, он и будет тетта-оценкой, аi-й элемент столбца B, лежащий в одной строке с тетта-оценкой, будет выво-диться из базиса, заменяясь элементом xk, полученным по дельта-оценке. Для осуществления такой замены нужно в i-ой строке k - гo столбца матрицы А сде-лать единицу, а в остальных элементах k-гостолбца сделать нули. Такое преоб-разование и будет одним шагом итерационного процесса. Для осуществления такого преобразования используется метод Гаусса. В соответствии с ним i-я строка всей матрицы А, а также i-я координата ХB делятся на aik (получаем единицу в i-ой строке вводимого в базис элемента). Затем вся i-я строка (если i не единица), а также i-я координата ХBумножаются на элемент (-а1k). После этого производится поэлементное суммирование чисел в соответствующих столбцах 1-ой и i-ой строк, суммируются также Х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
2x1 – x2 + x3
-x1 + 2x2 – 5x3
Все xi
1. Для начала приведем задачу к каноническому виду:
L(x) = x1 – 2x2 + 3x3
x1 – 3x2 + x4 = 3