наилучших решений в задачах планирования производства.
Классическая постановка задачи линейного программирования.
Дано: система математически- линейных зависимых уравнений с неизвестными
называемая система ограничений задачи линейного программирования, имеющая вид:
|
требуется найти неотрицательное значение перемен ой Х, которое удовлетворяет условно минимум или максимум целевой функции:
это выражение 9.2 принято называть линейной формой, которая часто отображается в виде:
|
выражение 10.1 – 10.3 можно отобразить в более компактной форме, в виде матрицы, тогда линейная форма будет иметь вид:
AX=B 10.4
L=CX 10.5
При B>0, X>0, L—max(min)
Выражение 10.4 матрица А имеет размерность n*m, x*c
Матрица В - m - мерный вектор столбец
Матрица Х - n - мерная вектор строка
Матрица С – n - мерная вектор строка
Если из n вычисть m и полученное значение с этим индексом, предположить их равным 0, то мы получим базисное решение. Базисное решение в линейном программировании называется допустимым, если базисные переменные не отрицательны по значению.
|
|
Решением системы уравнения 10.4 в условиях полной информатизации может быть получена различными способами. Наиболее простым способом 9.1-9.4 является симплексный метод. Основой всех методов получения решения уравнения ЛП в том числе и симплексный, является итерационный процедуры. Основной итерационной процедуры является введение наряду с базисными переменными независимых и ограниченных переменных (свободных). Из которых в условиях ограничения получаются отправные решения доставляющие целевой функции начальные значения, затем путем замены свободных переменных на базисные, составляются улучшенные значения целевой функции.
Если целевая функция L(x) стремится к max в задачи максимизации, то в ее индексной строке не должно быть не одного отрицательного числа и в этом случаи значение L(x) будет оптимальным, т.е. иметь максимум.
Если L(x) стремится к min, т.е. решается задача минимизации, то в ее индексной строке не должны быть положительные числа именно это значение будет оптимальным.
Рассмотрим изложенное выше положение на примере решения задачи №1, в лекции 8,
в которой имеет место следущая формализованная запись в канонической форме:
|
Для решения уравнения 10.6 симплексным методом необходимо перевести целевую функцию:
|
Для решения введем дополнительные переменные в каждое уравнение соответственно, тогда система 9.6 будет иметь вид:
все переменные должны быть введены и в целевую функцию, тогда
|
|
|
- А, - В, -С
Дополнительные переменные прибыли не дают, поэтому в целевой функции они будут равны нулю, с учетом этого целевая функция будет иметь вид:
Каждая из дополнительных или базисных переменных входит только в одно уравнение. Все они входят с коэффициентом +1. Свободные переменные на первом итерационном шаге приравниваются к нулю:
Для получения второго решения в симплексном методе составляется отправная таблица, имеющая вид:
С/б | Х/б | В | |||||
Х1 | Х2 | Х3 | Х4 | Х5 | |||
X3 | |||||||
0 | X4 | ||||||
X5 | |||||||
Zj-Cj | Z0=0 | -1 | -2 |
Примечание: здесь и далее элипс – обозначает генеральный элемент
В отправной таблице введены следующие обозначения:
С/б - коэффициенты при базисных переменных целевой функции
Х/Б – базисные переменные
В – столбец свободных членов
|
|
|
Нижние строки определяют разницу между
Алгоритм определения оптимального решения:
исходя из выше изложенной теории данные, полученные в симплексной таблице или в таблице вообще при максимизации целевой функции, решение будет оптимальным, если в индексной строке не будет отрицательных чисел
при минимизации целевой функции, решение будет оптимальным, если в индексной строке не будет положительных чисел (это так называемая двойственная задача линейного программирования)