Линейное программирование – область математики, развив. теорию и численные методы нахождения экстремума лин. функции многих переменных при мин. ограничениях, ур-ниях и неравенствах, связывающих эти переменные.

Задача о комплексном исп. сырья

На предприятии, изгот. сковородки и кастрюли, металл поступает партиями заготовок (по 100 кг). Используя разл. оборудование и последовательность обработки, сковородки и кастрюли можно получить 3 способами

	I	II	III
сковородки	75	39	97
кастрюли	34	86	16

Сколько металла (в центнерах) пустить на произв. по I (X1) II (X2) и III (X3) способу так, чтобы выполнить плановое задание (не менее 3000 сков. и 6500 кастрюль) при мин. расходе металла?

75X₁+39X₂+97X₃³3000

34X₁+86X₂+16X₃³6500

X₁,X₂,X₃³0

min (X₁+X₂+X₃)

Задача о диете

Сущ. некие питет. вещества (m штук) и n продуктов, содержащие эти вещества. Считаем, что нам известны a_i,j – содержание i-го вещества в единице j-го продукта. C_i,j – стоимость продукта. Известна суточная потребность (b_j) организма в веществах (a_i,j). Определить сколько какого продукта покупать (X_i,j), чтобы потребность в пит. веществах была удовлетворена, а общие расходы минимальны. (dj – ограничения по продукту)

Симплекс метод

Стандартный вид задачи

Если в (2) сотоит только из ³0 – задача в канонической форме. Если есть еще и "=", то – в смешанной.

Если в (3) –задача с двусторонним ограничением.

Задача на max и min практически идентичны:

Векторно-матричная форма:

max C[N]xX[N]

a[M,N]xX[N]=b[M] M – множество номеров строк 1..m

X[N] ³0 N - множество номеров столбцов 1..n

Пример:

0×X₁+5×X₂+X₃-X₄£3

1×X₁+1×X₂+X₃+X₄£2

X₂-X₃£10

X₁,X₂,X₃,X₄³0

max (X₁+2×X₂+X₃+3×X₄)

Т.к. все численные методв ЛП настроены на решение задач с равенствами, то приведем задачу к стандартной форме (в каждое из неравенств введем дополнительную переменную, сводящую неравенство к равенству.

0×X₁+5×X₂+X₃-X₄+X₅ =3

1×X₁+1×X₂+X₃+X₄ +X₆ =2

X₂-X₃ +X₇=10

X₁,…X₇³0

max (X₁+2×X₂+X₃+3×X₄)

В таком случае легко записать начальные допустимое базисное решение – вектор Х, удовлетворяющий условиям (2), (3) : Х₅=3 Х₆=2 Х₇=10 Х₁… Х₄=0 (Т.е. эти числа являются решением, хотя и неоптимальным).
Вектор Х, состоящий из чисел в количестве, равном числу ограничений, неравных нулю и остальных нулевых компонент называется базисным.
Допустимый базисный вектор Х, доставляющий максимум целевой функции (функции min или max), называется оптимальным решением.

Составим симплекс-таблицу

Cbase		1	2	1	3	0	0	0
Cbase		Х₁	Х₂	Х₃	Х₄	Х₅	Х₆	Х₇
0	Х₅=3	0	5	1	-1	1	0	0
0	Х₆=2	1	1	0	1	0	1	0
0	Х₇=10	0	1	-1	0	0	0	1

С_basic – базисные компоненты целевой функции.

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

Dj= - компоненты двойственного вектора

Метод искусственного базиса для решения задачи ЛП

Пусть требуется решить след. з-чу ЛП:

X₁+2×X₂+2×X₃-6×X₄=1

1×X₁+1×X₂+4×X₃–8×X₄=1

4×X₁+2×X₂+1×X₃–4×X₄=3

X₁,X₂,X₃,X₄³0

max (X₁–2×X₂+3X₃–10×X₄)

В каждое из ограничений вводим искусственную переменную, имеющую в максимизируемой целевой функции коэффициент –gz, где gz – большое число. Наличие отриц. коэф-тов гарантирует скорейший выход этих переменных из базиса, gz должно быть на порядок больше по абсолютной величине любого из встречающихся чисел задачи.

1×X₁+2×X₂+2×X₃-6×X₄+X₅ =1

1×X₁+1×X₂+4×X₃–8×X₄ +X₆ =1

4×X₁+2×X₂+1×X₃–4×X₄ +X₇=3

X₁,X₂,X₃,X₄³0

max (X₁–2×X₂+3X₃–10×X₄–100×X₅–100×X₆–100×X₇)

НДБР: Х_1-4=0, Х₅=1, Х₆=1, Х₇=3

С_basic	L=-500	1	-2	3	-10	-100	-100	-100
С_basic	L=-500	Х₁	Х₂	Х₃	Х₄	Х₅	Х₆	Х₇
-100	Х₅=1	1	1	2	-6	1	0	0	½
-100	Х₆=1	1	1	4	-8	0	1	0	¼
-100	Х₇=3	4	2	1	-4	0	0	1	¾
Dj=		-601	-398	-703	1810	0	0	0