Реферат: Решение задач линейного программирования
<p/>Министерство общего и профессионального образованияРоссийской Федерации
Воронежский Государственный Архитектурно – Строительный
Университет
Кафедра Экономики и управления строительством
ЛАБОРАТОРНАЯ РАБОТАНа тему:«Решение задач линейного программирования»
Выполнил:
Студент 4 курса
ФЗО ЭУССидоров В.В.
Руководитель:
Богданов Д. А.
Воронеж – 2002 г.
ЛАБОРАТОРНАЯ РАБОТА№ 11РЕШЕНИЕ ЗАДАЧЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Цель работы:изучение принципов составленияоценочных характеристик для задач линейного программирования, получение навыковиспользования симплекс-метода для решения задач линейного программирования,усвоение различий получаемых результатов, изучение табличной формы применения симплекс-метода.
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
Стандартная задача линейного программирования состоит изтрех частей:
целевой функции (на максимум или минимум) — формула (1.1),основных oграничений /> - формула (1.2),ограничений не отрицательности переменных (есть, нет) — формула (1.3)
/>
(1.1)
/> i = 1,… m (1.2)
/> (1.3)
Алгоритм решения задач линейного программированиятребует приведения их постановки в канонический вид, когдацелевая функция стремится к максимуму (если стремилась к минимуму, то функциюнадо умножить на -1, на станет стремиться к максимуму), основные ограниченияимеют вид равенства (для приведения к равенствам в случае знака /> надо в правую часть каждогoтакого k-го неравенства добавить искусственную переменную uk/>, а в случае знака />, uk/> надо отнять ее из правой частиосновных ограничений), присутствуют ограничения не отрицательности переменных(если их нет для некоей переменной хk, то их можно ввести путемзамены всех вхождений этой
переменной комбинацией x1k— х2k= хk, где х1k /> и х2k />). При этом для решения задачилинейного программирования необходимо иметь базис, т.е. наборпеременных хi, в количестве, равным числу основных ограничений, причем чтобы каждая изэтих переменных присутствовала лишь в одном основном oграничении и имела своймножитель аij= 1. Если таких переменных нет, то они искусственно добавляются в основныеограничения и получают индексы хm+1, xm+2 и т.д. Считается при этом, чтоони удовлетворяют условиям не отрицательности переменных. Заметим, что еслибазисные переменные (все) образуются в результате приведения задачи кканоническому виду, то целевая функция задачи остается без изменений, а еслипеременные добавляются искусственно к основным ограничениям, имеющим видравенств, то из целевой функции вычитается их сумма, умноженная на М, т.е./> (так называемый модифицированныйсимплекс-метод). Мы не будем рассматривать задачи, относящиеся кмодифицированному симплекс-методу. Для практической рабо-ты по нахождению решения задачи линейного программирования (поварианту простого симплекс-метода)будут использоваться алгоритмитерационного (многошагового) процесса нахождения решения и два типаоперативных оце-нок, позволяющих делатьпереходы от одного шага к другому, а также показы-вающих,когда итерационный процесс остановится и результат будет найден.
Первая оценка — это дельта-оценка, дляпеременной хjона имеет вид:
/> (1.4)
/>
Здесьвыражение i /> B означает,что в качестве коэффициентов целевой функ-ции,представленных в сумме выражения (1.4), используются коэффициенты переменных,входящих в базис на данном шаге итерационного процесса. Пере-менными аij являются множители матрицыкоэффициентов А при основных ог-раничениях,рассчитанные на данном шаге итерационного процесса. Дельта-оценкирассчитываются по всем переменным хi, имеющимся в задаче.Следует отметить; что дельта-оценки базисных переменных равны нулю. После нахож-дения дельта-оценок из них выбирается наибольшаяпо модулю отрицательная оценка, переменная хk, ейсоответствующая, будет вводиться в базис. Другой важной оценкой является тетта-оценка,имеющая вид:
/> (1.5)
Т.е. пономеру 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.1B
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:
BCB
XB
A1
A2
A3
A4
A5
A6
Q
/>A43
1
-3
1
-
A5
3
2
-1
1
1
3
/>A6
3
-1
2
-5
1
-
D
-1
2
-3
A4
3
1
-3
1
A3
3
3
2
-1
1
1
A6
3
-1
2
1
D
9
5
2
3
Таким образом, уже на второмшаге расчетов (вычислений дельта-оценок) получено, что все небазисные дельтаоценки положительны, а это означает, что данная задача имеет единственноерешение:
3. Решение задачи запишем ввиде:
X* = (0, 0, 3, 3 ,0, 3), L*(X*) = 9.