Лекция 14. Линейное программирование и симплексный метод выбора

наилучших решений в задачах планирования производства.

Классическая постановка задачи линейного программирования.

Дано: система математически- линейных зависимых уравнений с неизвестными

называемая система ограничений задачи линейного программирования, имеющая вид:

10.1

где

требуется найти неотрицательное значение перемен ой Х, которое удовлетворяет условно минимум или максимум целевой функции:

это выражение 9.2 принято называть линейной формой, которая часто отображается в виде:

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

Для решения уравнения 10.6 симплексным методом необходимо перевести целевую функцию:

10.7

Для решения введем дополнительные переменные в каждое уравнение соответственно, тогда система 9.6 будет иметь вид:

все переменные должны быть введены и в целевую функцию, тогда

- сколько станков будет использоваться в цехах

В выражении 9.7 переменная X имеет физический смысл не используемых станков в цехе А, а выражение

- А, - В, -С

Дополнительные переменные прибыли не дают, поэтому в целевой функции они будут равны нулю, с учетом этого целевая функция будет иметь вид:

Каждая из дополнительных или базисных переменных входит только в одно уравнение. Все они входят с коэффициентом +1. Свободные переменные на первом итерационном шаге приравниваются к нулю:

Для получения второго решения в симплексном методе составляется отправная таблица, имеющая вид:

С/б	Х/б	В
Х1	Х2	Х3	Х4	Х5
	X3
0	X4
	X5
Zj-Cj	Z0=0	-1	-2

Примечание: здесь и далее элипс – обозначает генеральный элемент

В отправной таблице введены следующие обозначения:

С/б - коэффициенты при базисных переменных целевой функции

Х/Б – базисные переменные

В – столбец свободных членов

	Определяется как сумма по парных произведений коэффициентов С/б на столбец В

	- Коэффициент целевой функции при переменных

Называется индексной строкой Текущее решение

Нижние строки определяют разницу между

Алгоритм определения оптимального решения:

исходя из выше изложенной теории данные, полученные в симплексной таблице или в таблице вообще при максимизации целевой функции, решение будет оптимальным, если в индексной строке не будет отрицательных чисел

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