Соловей Галина Николаевна

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

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

Математическая модель ЗЛП :

1.Максимум или минимум целевой функции(критерий оптимальности).

2.Система ограничений в форме линейных уравнений и неравенств.

3.Неотрицательность переменных.

Пример:

Фирма производит 2 модели А и В сборных полок, их производство ограничено наличием сырья(доски) и временем машинной обработки. Для одного изделия модели А требуется 3 метра кв. досок, модели В – 4. Фирма может получать до 1700 метров кв. досок. Для изделия А – 12 минут машинного времени, В – 30 мин. В неделю можно использовать 160 часов. Сколько изделий каждой модели следует выпускать в неделю макс прибыль, если А – 2$,B – 4$.

Ресурсы	А	В	Ограничения
Доски	3	4	1700
Время	0,2	0,5	160
Прибыль	2	4	Макс

Х1 – кол-во изделий А, Х2 – В.

(1)Zmax = 2X1+4X2

(2)3X1+4X2<=1700

0,2X1+0,5X2<=160

(3)X1,X2>=0

Решение, удовлетворяющее системе ограничения (2) и требованием (3) – допустимое, а (2),(3) + условия мин-макс – оптимизированное.

Общий вид задачи линейного программирования

Макс(мин)f(x)=C1X1+C2X2+…+CnXn (1)

A11X1+A12X2+…+A1nXn<=b1

A21X1+A22X2+…+A2nXn<=b2

Am1X1+Am2X2+…AmnXn<=bm

X1,x2…>=0

Свойства:

1.Допкстимое множество решений ЗЛП либо пустое, либо является выпуклым многогранником.

2.Если допустимое множество не пустое, а целевая функция ограничена сверху для максимизации , а снизу – для минимизации, то она имеет оптимальное решение.

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

При изготовлении изделий И₁ и И₂ используются токарные и фрезерные станки, а так же сталь и цветные металлы. По технологическим нормам на производство изделия И₁ требуется 300 и 200 единиц соответственно токарного и фрезерного оборудования, 10 и 20 единиц стали и цвет мет; для И₂ – 400, 100, 70, 50. Цех располагает 12400, 6800, 640, 840 . Прибыль от реализации И₁ – 6, И₂ -16.

Ресурсы	И1	И2	Ограничения
Токарный	300	400	12400
Фрезерный	200	100	6800
Сталь	10	70	640
Цвет мет	20	50	840
Прибыль	6	16	Макс

Х1 – кол-во И1, Х2 – кол-во И2.

300Х1+400Х2<=12400

200X1+100X2<=6800

10X1+70X2<=640

20X1+50X2<=840

Zmax=6X1+16X2

X1,X2>=0

3 формы записи

Формы записи задач линейного программирования

Модель задачи линейного программирования может быть записана в одной из приведенных ниже форм:

1.Общая форма записи – целевая фунуция записывается: max(min)z=

///

2.Симметричная – maxZ= , minZ=

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

Лекция 2

Графический метод решения ЗЛП

Если число неизвестных равно 2, то ее можно решить графическим методом. Найти решение Найти решение х=(х₁,х₂)

Макс(мин)Z=C₁X₁+C₂X₂ (1)

Sum(A_ijX_j)<=b_i (2)

X₁,X₂>=0

Каждое из неравенств 2 определяет на координатной плоскости полуплоскость, а система неравенств 2 и 3 в случае ее совместимости – пересечение плоскостей. Это будет выпуклое множество, которое может быть представлено как:

1.Выпуклый многоугольник.

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

3.Отрезок.

4.Луч.

5.Одна точка.

6.Пустое множество.

Геометрическая интерпретация целевой функции:

Z=C₁X₁+C₂X₂ (1)

При фиксированных значениях Z=Z₀ определяет линию. При изменении Z получим семейство параллельных прямых, называемых линиями уровня. Вектор С=(С₁ , С₂) перпендикулярен каждой из линий уровня. Вектор С показывает направления наибольшего возрастания(убывания) целевой функции.

Если построить на одном рисунке область допустимых решений вектор С и одну из линий уровня, например Z=0, то задача сводится к определению области допустимых решений точки направления вектора С, через которую проходит линия уровня Z макс(мин), соответствующая наибольшему(меньшему) значению функции Z. Если задача рерзрешима могкт представиться следующие случаи:

1.Задача имеет единств решение.

2.Задача имеет бесконечное множество решений(альтернативный оптимум).

3.Целевая функция не ограничена, область допустимых решений – единственная точка(рис. 1).

Х₁

Х₂

Max(min)Z=2X₁+3X₂

X2

1 3

2

X1

Проверяем каждую вершину.

Zmin()=2*(4/9)+3*(8/9)=32/9

Zmax=2*2+3*4=16

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

Построение начального опорного плана

Рассмотрим 3 случая.

Пусть система ограничений имеет вид

X_i+ _ijX_j=b_i , b_i=>0,(i=1,m)

X₀=(0,0,…,0,b_i)

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

Пример:

minZ=-5X₁+6X₃

2X₁-2 X₃+ X₄=2| X₄

2 X₁+ X₂- X₃=3 | X₂

X₁>=0

X₀=(0,3,0,2)

_ijX_j<=b_i, b_i>=0

X_n+i>=0

_ijX_j+X_n+1=b_i, b_i>=0

X₀=(0,…,0,b­­_i,...,b_m)

Пример 2:

minZ=10 X₁-7 X₂-5 X₃

6 X₁+15 X₂+6 X₃<=9

14 X₁+42 X₂+16 X₃<=21

2X₁+8 X₂+2 X₃<=4

тогда

6 X₁+15 X₂+6 X₃+ X₄=9

14 X₁+42 X₂+16 X₃+ X₅=21

2X₁+8 X₂+2 X₃+ X₆=4

X₀=(0,0,0,9,21,4)

_ijX_j>=b_i , b_i>=0

_ijX_j-X_n+i=b_i

M-задача

Max(min)Z= _jX_j-(+)M _i

minZ=-5 X₁+4X₂+3 X₃+6X₄

X₁+21X₂+ X₃+2X₄<=3

-X₁-14X₂-2X₃+3X₄>=2

-X₁-6X₂+X₃-X₄>=1

X₁+21X₂+ X₃+2X₄+ X₅=3

-X₁-14X₂-2X₃+3X₄- X₆+W₁=2

-X₁-6X₂+X₃-X₄- X₇ +W₂=1

X₀=(0,0,0,0,3,0,0,2,1)

Z(X₀)=3M

Пример:

_maxZ=5 X₁+7 X₂+6 X₃+11X₄

3X₁+4 X₂ -3 X₃ <=12|+ X₅

X₁ -4 X₄ <=22 | +X₆

X₂ + X₃ +3 X₄ <=6 |+ X₇

X₀ =(0,0,0,0,12,22,6)

Пример 2:

_maxZ= X₁ +2 X₂ +3 X₃ +4 X₄

4X₁+3X₂+7X₃ =9 |+W_i

X₁ +2 X₂ -5 X₄ >=21|- X₅ +W₂

4 X₂ +7 X₃ – X₄ >=7|- X₆ +W₃

X₀ =(0,0,0,0,0,0,9,21,7)

Z(X₀)=37M

Симплексные таблицы

_maxZ= 18X₁ +20 X₂ +32 X₃

18X₁+15X₂+12X₃ <=720

6X₁ +4 X₂ +8 X₄ <=384

5X₁ +3X₂ +12X₃ >=360

БП	СБ	А0	Х1	Х2	Х3	Х4	Х5	Х6
			18	20	32	0	0	0
Х4	0	720	18	15	12	1	0	0
Х5	0	384	6	4	8	0	1	0
Х6	0	360	5	3	12	0	0	1
	Сj­	0	-18	-20	-32	0	0	0

Рабочая часть таблицы начинается с 3 строки и 3 столбцы. В БП занесены базисные(предпочтительные) переменные; СБ содержит коэффициенты целевой функции, стоящие при базисных переменных; Ао содержит свободные члены Вi. Сверху, над рабочей частью таблицы указаны все переменные и коэффициенты целевой функции.

Хо=(0,0,0,720,384,360)

Z(Xo)=0