РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Цель работы
Ознакомиться с принципами составления оценочных характеристик для задач линейного программирования.
Научиться применять симплекс-метода для решения задач линейного программирования.
Изучить табличную форму применения симплекс-метода.
Объяснить различия получаемых результатов.
ТЕОРИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Обычная задача линейного программирования состоит из трех частей:
целевой функции (на максимум или минимум) – формула (1.1),
основных ограничений– формула (1.2),
ограничений не отрицательности переменных (есть или нет) - формула (1.3)
(1.1)
i = 1,… m (1.2)
(1.3)
Чтобы решить задачу линейного программирования, необходимо привести ее к
каноническому виду
,
когда целевая функция стремится к максимуму. Если целевая функция стремится к минимуму, то необходимо умножить ее на -1.
Основные ограничения имеют вид равенства (для приведения к равенствам в случае знака
надо в правую часть каждого такого k-го неравенства добавить искусственную переменную u
k
, а в случае знака
, искусственную переменную u
k
надо отнять от правой части основных ограничений).
Существуют ограничения не отрицательности переменных (если их нет для некоторой переменной х
k
, то их можно ввести путем замены всех вхождений этой переменной комбинацией
x
1
k - х
2
k = х
k
, где
х
1
k
и
х
2
k
). При этом для решения задачи линейного программирования необходимо иметь
базис
,
т.е. набор переменных
х
i
,
в количестве, равным числу основных ограничений, причем каждая из этих переменных должна входить лишь в одно основное ограничение с множителем
а
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 итераций симплекс-метода, то необходимо сделать вывод, что решение отсутствует в связи с неограниченностью функции цели.
При практическом решении задачи линейного программирования симплекс-методом удобно пользоваться таблицей вида (табл. 1.1):
Таблица 1.1
B
C
B
X
B
A
1
A
n
Q
Базисные
Целевые
Правые
компоненты
Коэффиц.
Части
Базиса
ограничен
D
D1
D
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
1. Вначале сведем задачу к каноническому виду
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
2. Составим таблицу симплекс-метода (табл. 1.2)
В данном случае базис образуют компоненты
x
4
, x
5
, x
6
.
B
C
B
X
B
A
1
A
2
A
3
A
4
A
5
A
6
Q
A
4
0
3
1
-3
0
1
0
0
-
A
5
0
3
2
-1
1
0
1
0
3
A
6
0
3
-1
2
-5
0
0
1
-
D
-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
D
9
5
2
0
0
3
0
После вычисления дельта-оценок можно сделать вывод.
Данная задача будет иметь единственное решение, т.к. все небазисные дельта-оценки положительны.
3. Решение задачи будет выглядеть следующим образом
X* = (0, 0, 3, 3 ,0, 3), L*(X*) = 9.
Реферат Характеристика задач решаемых с использованием методов линейного програмирования. Если в задачи линейного программирования существует бесчисленное множество решений то. Контрольная работа решения графическим способом задачи линейного программирования. Приведение системы ограничений задачи линейного программирования в базисную форму. Задача линейного программирования строчным симплекс методом подробно напишите. Постановка задачи линейного программирования приведение к каноническому виду. Если задача линейного программирования имеет бесчисленное множество решений. Основная задача линейного программирования приведение к стандартному виду. Если в задаче линейного програмирования существует множество решений то. Алгоритм решения задач линейного программирования графическим способом. Алгоритм решения транспортной задачи задачи линейного программирования. Алгоритм решения задач линейного программирования графическим методом. Алгоритм графического метода решения задач линейного программирования. Решение основной задачи линейного программирования табличным методом. Задачу линейного программирования приводят к каноническому виду для.
