Ф

- План производства 1 детали (объем производства)

- План производства 2 детали

ормализация задачи: пусть переменная

Т огда целевая функция будет иметь вид:

введем ограничения:

1. ограничение по фонду рабочего времени, планированное

Ра бочее время не должно иметь ограничение

2. по производственной мощности

3.по уровню запасов, планированное использование материалов

каждого вида не должно превышать 10000 кг

4.по обязательствам поставки первых деталей

5. по профсоюзному ограничению

6. условие не отрицательности

Решение:

С троим систему координат, при фиксированном времени.

7

6

5

4

(2)

3

2 С д

1 Д

1 2 3 4 5 6 7 8

Построение областей ограничения

С троим целевую функцию (произвольно)

Оптимальная точка определения плана производства достигается максимальным доходом.

Это точка Д (1500, 1250)

А налитический способ:

Резюме

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

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

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

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

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

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

г

10.1

де

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

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

10.2

10.3

в ыражение 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	0	0	0
			Х1	Х2	Х3	Х4	Х5
0	X3	24	2	3	1	0	0
0	X4	15	1	3	0	1	0
0	X5	8	0	2	0	0	1
Zj-Cj		Z0=0	-1	-2	0	0	0

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

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

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

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

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

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

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