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

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

Министерство общего и профессионального образования

Российской Федерации

Воронежский Государственный Архитектурно – Строительный

Университет

Кафедра Экономики и управления строительством

ЛАБОРАТОРНАЯ РАБОТА

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

Выполнил:

Студент 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 , то их можно ввести путем замены всех вхождений этой

переменной комбинацией x1 k - х 2 k = х k , где х 1 k и х 2 k ). При этом для решения задачи линейного программирования необходимо иметь базис , т.е. набор переменных х 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-ой строк, суммируются также ХB 1 , и (1k )B i ;. Аналогичные действия производятся для всех остальных строк кроме 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 D n

Задание

Необходимо решить задачу линейного программирования.

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 9 5 2 0 0 3 0

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

3. Решение задачи запишем в виде :

X* = (0, 0, 3, 3 ,0, 3), L*(X*) = 9.