7 Общая постановка задачи линейного программирования формы записи злп

Задача линейного программирования (ЗЛП) в общем виде имеет три формы:

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

1. Произвольная форма задачи ЛП имеет вид:

(2)

Выражение называется целевой функцией задачи. Величины (Х₁,Х₂,…,Х_N) – переменные задачи. Система неравенств в задаче (2) определяет область допустимых значений (планов) задачи D, которая имеет форму выпуклого многогранника. Неравенства и равенства в задаче (2) называются ограничениями. Каждое неравенство определяет полупространство, а равенство – плоскость в пространстве переменных.

Решение задачи (2) называется оптимальным решением (или оптимальным планом) и обозначается как Х*=(Х*₁,Х*₂,…,Х*_N).

Если область D ограничена, то задача ЛП всегда имеет либо единственное, либо бесконечно много решений. Если решение единственно, то оно совпадает с одной из вершин многогранника D. Если градиент целевой функции c=(с1,с2,…,сn) коллинеарен градиенту одного из ограничений, то задача имеет бесконечно много решений, лежащих на данном ограничении.

Если ограничения несовместны, или целевая функция неограниченна в неограниченной области D, то задача (2) не имеет решения. Всякая задача на минимум может быть сведена к задаче на максимум и наоборот, умножением целевой функции на –1. Оптимальный план задачи при этом не изменится, а значение целевой функции изменит знак. После решения надо снова изменить знак значения целевой функции.

2. Симметричная форма ЗЛП имеет два вида.

Симметричная форма задачи на максимум:

(3)

Задача (3) обычно имеет следующий экономический смысл: это объемы производства го вида продукции, цены или прибыль на единицу продукции, затраты го вида ресурса на производство го вида продукции, имеющийся запас го вида ресурса. Задача (3) ставится на определение такого плана производства продукции, который дает максимальную выручку или прибыль, при заданных ограничениях на имеющиеся ресурсы.

3. Каноническая форма задачи ЛП.

(5)

Определение. Если в ограничениях (5) есть переменные, отсутствующие в других ограничениях и с коэффициентами равными единице, то они называются базисными, остальные переменные называются свободными.

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

? примеры задач ЛП

• задача об использовании ресурсов.

Для изготовления р1 ир2, используется ресурсы S1, S2. Запасы ресурсов число единиц затраченных на изготовление единицы продукции

Вид ресурсов	запас	Количество единиц затраченных на изготовление единицы продукции
		Р1	Р2
S1	18	1	3
S2	16	2	1
S3	5	-	1
S4	21	3	-

Надо составить такой план производства продукции при котором прибыль от её реализации max.

X1 – количество продукции р1 запланир 1 выпуск

Х2 - количество продукции р2 запланир 1 выпуск

S1: x1+3x2<=18

S2: 2x1+x2<=16

S3: x2<=5

S4: 3x1<=21

F(x1,x2)= 2x1+3x2 стремится к max

• задача о составлении рациона

Есть 2 вида корма содержащие витамины, содержащие числа единиц питательного вещества в 1 кг. Каждого вида корма и необход min питательных веществ

Питательные вещества	Необход min	Количество единиц затраченных на изготовление единицы продукции
		I	II
S1	9	3	1
S2	8	1	2
S3	12	1	6

Надо составить дневной рацион имеющий min стоимость в котором содержащие каждого вида min веществ было бы не менее установленного предела

Ч_ij – количественного j норма использ для приготовленного рациона.

S1: 3x1+x2>=9

S2: x1+2x2>=8

S3: x1+6x2>=12

F(x1,x2)= 4x1+6x2 стремится к min

• задача о раскрое

Надо составить оптимальный план раскроя некоторых видов заготовок из стандартных форм т е указать сколько листов материала кроить по каждому из вариантов раскроя для получения количества заготовок каждого типа при min отходах. Пусть m - различных видов заготовок и рациональных вариантов раскроя листа. При этом количество заготовок I типа получаемого из первого листа при использовании j варианта = a_ij количество отходов c_j. Пусть x_j>=0, количество листов раскраевымых по варианту j. x – план раскроя. Каждую заготовку I надо выпускать в количестве не менее заданного

• задача об оптимизации мощностей

Предприятие имеет план производства по времени и по номенклатуре: требуется за некоторое время выпустить n единиц продукции р. Она производится на станках S. Для каждого станка известна его производительность a_ij – число единиц продукции p_j, которое можно произвести на станке S_i , затраты b_ij – количество продукции p_j, на станке S_i в единицу времени. Надо составить план работы станков, чтобы затраты на производство продукции были min.

9-10 Симплекс метод решения ЗЛП

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

(1)

Если все bi>=0, то в задаче (1) есть начальный опорный план (X1=b1,X2=b2,…,Xm=bm, Xm+1=0,…,Xn=0).

Симплекс алгоритм решения ЗЛП носит итеративный характер и состоит в построении и последовательном преобразовании симплексной таблицы.

Алгоритм состоит из двух этапов – построение начального опорного плана, если его нет и построение оптимального плана.

Построение начального опорного плана (шаги 1-6):

1. Если все bi>=0, то начальный опорный план (b1,b2,…,bm) построен, переходят к построению оптимального плана. Иначе, выбирают строку, содержащую наибольший по абсолютной величине отрицательный элемент в столбце плана. По наибольшему по абсолютной величине отрицательному коэффициенту этой строки в столбцах свободных переменных выбирают разрешающий столбец – r.

Если в строке, где bi<0 в столбцах свободных переменных нет отрицательных коэффициентов, то система ограничений несовместна и задача не имеет решения.

2. Вычисляют симплексные отношения – отношений элементов планового столбца к ненулевым элементам разрешающего столбца.

3. По наименьшему неотрицательному симплексному отношению выбирают разрешающую строку – s.

(3)

4. На пересечении разрешающей s-строки и разрешающего r-столбца берут разрешающий R–элемент. Меняют местами базисную и свободную переменные, стоящие в разрешающих столбце и строке.

5. Выполняют симплексные преобразования элементов симплексной таблицы методом прямоугольника.

6. Переходят к шагу 1.

Построение оптимального плана (шаги 7–8):

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

Иначе, если в F–строке есть отрицательные элементы, то по наибольшему по абсолютной величине отрицательному элементу F–строки выбирают разрешающий столбец. Если отрицательных элементов несколько, то выбирают наибольший по абсолютной величине элемент.

(Признак отсутствия решения. Если в F–строке есть отрицательный элемент, в столбце которого нет положительных элементов, то целевая функция неограниченна, т.е. решения ЗЛП не существует).

Пересчет симплексной таблицы методом прямоугольника выполняется по следующей схеме:

1. Разрешающий элемент заменяется обратной величиной, остальные элементы разрешающей строки делятся на разрешающий элемент, остальные элементы разрешающего столбца делятся на разрешающий элемент и меняют знак.

2. Все прочие элементы таблицы пересчитываются по схеме прямоугольника.

C ___________ D

B __________ R

Новое значение элемента С, вычисляемое по правилу прямоугольника равно

(4)

где R – разрешающий элемент, B стоит на пересечении столбца элемента С и строки элемента R; D стоит на пересечении столбца элемента R и строки элемента С.

Будем считать, что переменные с номерами 1,2,…,m являются базисными. Симплексная таблица алгоритма тогда имеет вид.

БП	СБ	План (БП)	C1	С2	С3	…	Сm	Сm+1	…	Cn
			Х1	Х2	Х3	…	Хm	Хm+1	…	Хn
X1	C1	b1	1	0	0	…	0	a1, m+1	…	a1, n	b1/a1,r
X2	C2	b2	0	1	0	…	0	a2, m+1	…	a2, n	b2/a2,r
…	…	…	…	…	…	….	…		….	…	…
Xm	Cm	bm	0	0	0	…	1	am, m+1	…	am, n	bm/am,r
zi-ci		(СБ, БП)	0	0	0		0	Dm+1	…	Dn

где Di = (СБ, Ai) – Сi , Ai =( a_{1, i ,} a_{2, i , …,} a_{m, i} )^T .– столбец соответствующий Сi,

(CБ, Ai) – скалярное произведение столбцов CБ и Ai.

Последняя строка таблицы называется индексной. В столбец БП записываются базисные переменные.

Числа Di называются индексными оценками.

Экономический смысл Di – это разность между затратами и ценой реализации.

Числа в столбце это симплексные отношения, они определяются по формулам:

(12)