Решение задач линейного программирования (работа 3)
Министерство общего и профессионального образования
Российской Федерации
Воронежский Государственный Архитектурно – Строительный
Университет
Кафедра Экономики и управления строительством
ЛАБОРАТОРНАЯ РАБОТА
На тему: «Решение задач линейного программирования»
|
Выполнил: Студент 4 курса ФЗО ЭУССидоров В.В. Руководитель: Богданов Д. А. |
Воронеж – 2002 г.
ЛАБОРАТОРНАЯ РАБОТА № 11
РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Цель работы: изучение принципов составления оценочных характеристик для задач линейного программирования, получение навыков использования симплекс-метода для решения задач линейного программирования, усвоение различий получаемых результатов, изучение табличной формы применения симплекс-метода.
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
Стандартная задача линейного программирования состоит из трех частей:
целевой функции (на максимум или
минимум) - формула (1.1), основных oграничений
- формула (1.2), ограничений не отрицательности
переменных (есть, нет) - формула (1.3)
i
= 1,… m (1.2)
Алгоритм решения задач линейного
программирования требует приведения
их постановки в канонический
вид, когда
целевая функция стремится к максимуму
(если стремилась к минимуму, то функцию
надо умножить на -1, на станет стремиться
к максимуму), основные ограничения имеют
вид равенства (для приведения к равенствам
в случае знака
надо в правую часть каждогo такого k-го
неравенства добавить искусственную
переменную u>k>
,
а в случае знака
,
u>k>
надо отнять ее из правой части основных
ограничений), присутствуют ограничения
не отрицательности переменных (если их
нет для некоей переменной х>k>,
то их можно ввести путем замены всех
вхождений этой
переменной комбинацией x1>k>
- х2>k>
= х>k>,
где х1>k>
и х2>k>
).
При этом для решения задачи линейного
программирования необходимо иметь
базис,
т.е. набор переменных х>i>,
в количестве, равным числу
основных ограничений, причем чтобы
каждая из этих переменных присутствовала
лишь в одном основном oграничении и
имела свой множитель а>ij>
= 1. Если таких переменных
нет, то они искусственно добавляются в
основные ограничения и получают индексы
х>m+1>,
x>m+2>
и т.д. Считается при этом,
что они удовлетворяют условиям не
отрицательности переменных. Заметим,
что если базисные переменные (все)
образуются в результате приведения
задачи к каноническому виду, то целевая
функция задачи остается без изменений,
а если переменные добавляются искусственно
к основным
ограничениям, имеющим вид равенств, то
из целевой функции
вычитается их сумма, умноженная на М,
т.е.
(так называемый модифицированный
симплекс-метод).
Мы не будем
рассматривать задачи, относящиеся к
модифицированному симплекс-методу. Для
практической рабо-ты
по нахождению решения задачи линейного
программирования (по варианту простого
симплекс-метода)
будут
использоваться алгоритм итерационного
(многошагового) процесса нахождения
решения и два типа оперативных оце-нок,
позволяющих делать переходы от одного
шага к другому, а также показы-вающих,
когда итерационный процесс остановится
и результат будет найден.
Первая оценка - это дельта-оценка, для переменной х>j> она имеет вид:
(1.4)
З
десь
выражение i
B означает, что
в качестве коэффициентов целевой
функ-ции,
представленных в сумме выражения (1.4),
используются коэффициенты переменных,
входящих в базис на данном шаге
итерационного процесса. Пере-менными
а>ij>
являются множители матрицы коэффициентов
А
при основных ог-раничениях,
рассчитанные на данном шаге итерационного
процесса. Дельта-оценки рассчитываются
по всем переменным х>i>,
имеющимся в
задаче. Следует отметить; что дельта-оценки
базисных переменных равны нулю. После
нахож-дения
дельта-оценок из них выбирается наибольшая
по модулю отрицательная оценка, переменная
х>k>,
ей соответствующая,
будет вводиться в базис. Другой важной
оценкой является тетта-оценка,
имеющая вид:
(1.5)
Т.е. по номеру k, найденному по дельта-оценке, мы получаем выход на пере-менную х>k> и элементы столбца ХB делим на соответствующие (только положи
тельные) элементы столбца
матрицы А,
соответствующего
переменой x>k>.
Из полученных результатов выбираем
минимальный, он и будет тетта-оценкой,
а>i>-й
элемент столбца B,
лежащий в одной
строке с тетта-оценкой, будет выво-диться
из базиса, заменяясь элементом x>k>,
полученным по
дельта-оценке. Для осуществления такой
замены нужно в i-ой
строке k
- гo столбца
матрицы А сде-лать
единицу, а в остальных элементах k-го
столбца сделать
нули. Такое преоб-разование
и будет одним шагом итерационного
процесса. Для осуществления такого
преобразования используется метод
Гаусса. В
соответствии с ним i-я
строка всей матрицы А,
а также i-я
координата ХB
делятся на a>ik>
(получаем единицу в i-ой строке вводимого
в базис элемента). Затем вся i-я строка
(если i не единица), а также i-я
координата ХB
умножаются на
элемент (-а>1k>).
После этого производится поэлементное
суммирование чисел в соответствующих
столбцах 1-ой и i-ой строк, суммируются
также ХB>1>,
и (-а>1k>)*ХB>i>;.
Аналогичные действия производятся для
всех остальных строк кроме i-ой (базисной)
строки. В результате получается, что в
i-ой
строке k-го
элемента стоит
1, а во всех ос-тальных
его строках находится 0. Таким образом
осуществляется шаг итерационального
алгоритма, Шаги алгоритма симплекс-метода
продолжаются до тех пор, пока не будет
получен один из следующих результатов.
• Все
небазисные дельта-оценки больше нуля
— найдено решение задачи ли-
нейного программирования, оно представляет из себя вектор компонент х;, значения которых либо равны нулю, либо равны элементам столбца Х, та-в
кие компоненты стоят на базисных местах (скажем, если базис образуют пе-ременные х>2>, x>4>, х>5>, то ненулевые компоненты стоят в векторе решения зада-чи линейного программирования на 2-м, 4-м и 5-м местах).
• Имеются небазисные дельта-оценки, равные нулю, тогда делается вывод о том, что задача линейного программирования имеет бесчисленное множество решений (представляемое лучом или отрезком). Подробно рассматривать случаи такого типа, а также отличия между решениями в виде луча и отрезка мы не будем.
• Возможен вариант получения столбца отрицательных элементов на отрица-тельной рассчитанной дельта-оценке, в такой ситуации нельзя вычислить тетта-оценки. В этом случае делается вывод, что система ограничений задачи линейного программирования несовместна; следовательно, задача линейного программирования не имеет решения.
Решение задачи линейного программирования, если оно единственное, следует
записывать в виде Х* = (..., ..., ...) - вектора решения и значения целевой функ-ции в точке решения L*(Х*). В других случаях (решений много или они отсут-ствуют) следует словесно описать полученную ситуацию. Если решение задачи линейного программирования не будет получено в течение 10-12 итераций симплекс-метода, то следует написать, что решение отсутствует в связи с неог-рачниченностью функции цели.
Для практического решения задачи линейного программирования симплекс-методом удобно пользоваться таблицей вида (табл. 11.1):
Таблица 1.1
|
B |
CB |
XB |
A>1> |
… |
A>n> |
|
|
Базисные |
Целевые |
Правые |
||||
|
компоненты |
Коэффиц. |
Части |
||||
|
Базиса |
ограничен |
|||||
|
|
|
n |
Задание
Необходимо решить задачу линейного программирования.
L(x)
= x>1>
– 2x>2>
+ 3x>3>
x>1>
– 3x>2>
3
2x>1>
– x>2>
+ x>3>
3
-x>1>
+ 2x>2>
– 5x>3>
3
Все
x>i>
0 i = 1, …3
Для начала приведем задачу к каноническому виду:
L(x)
= x>1>
– 2x>2>
+ 3x>3>
x>1> – 3x>2> + x>4> = 3
2x>1> – x>2> + x>3> + x>5> = 3
-x>1> + 2x>2> – 5x>3> + x>6> = 3
Все
x>i>
0 i = 1, …6
Составляем таблицу симплекс-метода (табл. 1.2). Видно, что базис образуют компаненты x>4>, x>5>, x>6>:
B |
CB |
XB |
A>1> |
A>2> |
A>3> |
A>4> |
A>5> |
A>6> |
|
|
0 |
3 |
1 |
-3 |
0 |
1 |
0 |
0 |
- |
|
A>5> |
0 |
3 |
2 |
-1 |
1 |
0 |
1 |
0 |
3 |
|
|
0 |
3 |
-1 |
2 |
-5 |
0 |
0 |
1 |
- |
|
|
-1 |
2 |
-3 |
0 |
0 |
0 |
|||
|
A>4> |
0 |
3 |
1 |
-3 |
0 |
1 |
0 |
0 |
|
|
A>3> |
3 |
3 |
2 |
-1 |
1 |
0 |
1 |
0 |
|
|
A>6> |
0 |
3 |
-1 |
2 |
0 |
0 |
0 |
1 |
|
|
|
9 |
5 |
2 |
0 |
0 |
3 |
0 |
A>4>Таким образом, уже на втором шаге расчетов (вычислений дельта-оценок) получено, что все небазисные дельта оценки положительны, а это означает, что данная задача имеет единственное решение:
Решение задачи запишем в виде: