Реферат: Решение задач линейного программирования

<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.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

3

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.
еще рефераты
Еще работы по математике