Целевая функция-ф-ция экстремум значения ко-торой необходимо найти.

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

Целевая функция-ф-ция экстремум значения ко-торой необходимо найти.

Экономические возможности формализуются в виде системы ограничений.

Мат.модель задачи вкл.

1.неизвестные величиных=(х1,х2,...,хn) которые называют планом задачи.

Целевую функцию.

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

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

То мат. модель задачи имеет вид:

х=(х1,х2,..,хn)

F(х1,х2,..,хn)max(min)

ji(х1,х2,..,хn) { >,<,=} bi, i=1, n

xj>0, j=1,n

если план(неизвест величины) удовлетворяют сис

Теме ограничений задачи, то его наз.допустимым.

допустимый план доставляющий ф-ии цели экст-

ремальное значение назыв. оптимальн планом х*.

Эксрем.значение ф-ии –значение ф-ии цели для оп

тимального плана f*=f(x*).

Ести ф-ииf(х1,х2,..,хn)и gi(х1,х2,..,хn) линейны, то такая задача является задачей линейного прог.

Мат. модель задачи имеет вид

х=(х1,х2,..,хn)

Z=C1x1+C2x2+…+Cnxnmax(min) C1,C2,…,Cn- постоянные(числа)

a11x1+a12x2+…+a1nxn { >,<,=} b1

a21x1+a22x2+…+a2nxn { >,<,=} b2

……………………………………….

am1x1+am2x2+…+amnxn { >,<,=} bm

xj>0,j=1,n

3.пример 1 Для пр-ва 2-х видов продукции P1 и P2использ 3 вида сырья S1,S2,S3. Запасы сырья соотв равны 40,60,50 ед. Затраты на изг ед сырья P1соотв равны 2,8,5 ед. На P2соотв 5,3,6 ед. При-

быль от реализ продукции каждого вида соотвра-вны 100 и 200 ден ед. Необходимо сост мат модель плана выпуска продукции, при котором прибыль от реализ изделия будет максимальной.

Обозн через х1 и х2 кол-во про-циисоотв видов P1 и P2.

Делаем таблицу. обратная сторона.

Таким образом мат модель имеет вид.

х=(х1, х2)

Z=100х1+200х2 max

2x1+5x2<40

8x1+3x2<60

5x1+6x2<50

xj>0, j=1,2или x1>0,x2>0

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

Общая форма записи задач ЛП -это задача maxили minф-ии с линейными ограничениями в виде

Как равенств, так и неравенств.

х=(х1,х2,..,хn)

Z=C1x1+C2x2+…+Cnxnmax(min)

a11x1+a12x2+…+a1nxn { >,<,=} b1

a21x1+a22x2+…+a2nxn { >,<,=} b2

……………………………………….

am1x1+am2x2+…+amnxn { >,<,=} bm

xj>0,j=1,n

Каноническая форма записи задач ЛП-это зада-чаmaxили minф-ии с линейным ограничением в виде равенсва(решение или на maxили на min)

х=(х1,х2,..,хn)

Z=C1x1+C2x2+…+Cnxnmax(min)

a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2

………………………………

am1x1+am2x2+…+amnxn=bm

xj=0, j=1,n

Симметричная форма записи задач ЛП-это зада

ча maxс огранич вида <или minс огран вида >

х=(х1,х2,..,хn)

Z=C1x1+C2x2+…+Cnxnmax

a11x1+a12x2+…+a1nxn<b1

a21x1+a22x2+…+a2nxn<b2

………………………………

am1x1+am2x2+…+amnxn<bm

xj>0,j=1,n

х=(х1,х2,..,хn)

Z=C1x1+C2x2+…+Cnxnmin

a11x1+a12x2+…+a1nxn>b1

a21x1+a22x2+…+a2nxn>b2

………………………………

am1x1+am2x2+…+amnxn=bm

xj>0,j=1,n

Замечание 1.

Если задана задача на min, т.е. Z= cjxjmin, то умножив целевую ф-ию на (-1) получим задачу на max (-Z= cjxjmax) Причем min = -max

Замечание 2.

При переходе от неравенства к равенству необхо-

мо ввести дополнительные переменные, которые вкл. в целевую ф-ию с нулевыми коофициентамии если неравенство вида <, то дополн переменную добавляют к левой части неравенства, а если > то дополнперем вычитают слевой части неравенст

3.пример 2.На животн ферме каждое животное до- лжно ежедневно получать не менее 7 ед. питател в-ваS1, 9 ед. в-ваS2 и 14 ед. в-ваS3.Для составл рациона использ 2 вида корма.1 вид содержит со-отвественно 2,8,5 ед. питат в-в.2 в 1кг содержит со

Отв 5,5,4 ед. питат в-в.Стомость корма 1 равна 14 денед.,корма 2 соств 26 денед.Необходимососта-вить нужной питат,причем затраты должны бытьmin.

Обозначим через х1 и х2 кол-во приобретаемых кормов вида 1 и 2.

Делаем таблицу. обратная сторона.

Таким образом мат модель имеет вид.

х=(х1, х2)

Z=14х1+26х2 min

2x1+5x2>7

8x1+5x2>9

5x1+4x2>14

xj>0, j=1,2 или x1>0,x2>0

4.пример 3. Привести задачу с примера 2 к кано-нической формуле.

Введем дополн переменные х3,х4,х5,тогда мат модель примет вид.

х=(х1, х2,х3,х4,х5)

Z=14х1+26х2 min

2x1+5x2-х3 =7

8x1+5x2 -х4 =9

5x1+4x2 -х5=14

xj>0, j=1,5

Алгоритм графического метода.

С учетом системы ограничений строим область допустимых решений.

Строим вектор С с координатами С1 и С2,кото-рые показ найскорейшеевозрастан целевой ф-ии

3.проводим произвольную линию уровня Z0=0 перпендикулярно вектору С.

При решении задач на maxперемещаем линию уровня в направлении вектора С так, чтобы она касалась области допустимых решений в ее край-

Нем положении.

В случае задач на min линию уровня перемеща-ют в направлении вектора –С.

5.определяем оптимальный план х*=(х1*,х2*) и экстримальное значении ф-ии (Z*).

Рассмотрим задачу

х=(х1,х2)

Z=C1x1+C2x2max(min)

a11x1+a12x2 < b1

a21x1+a22x2 < b2

…………………

am1x1+am2x2 <bmградиент-С=(С1,С2)

x1>0, x2>0 строим вектор градиент, который будет С

Решить задачу граф. методом.

х=(х1, х2)

Z=12х1+15х2 max

6x1+6x2<36 (1)

4x1+2x2<20 (2)

4x1+8x2<40 (3)

x1>0,x2>0

Решение

(1) 6x1+6x2=36 (2) 4x1+2x2=20

Х1 1 2 3 4 6 х1 1 2 3 4 5 0

Х2 5 4 3 2 0 х2 8 6 4 2 0 10

3) 4x1+8x2=40

Х1 0 4 2

Х2 5 3 4

Чтобы найти точку выпис формула

6x1+6x2=36 х1=2, х2=4

4x1+8x2=40

x*=(2,4)

maxZ=Z(x*)=12*2+15*4=84

Он вкл 3 этапа.

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

2.проверка плана на оптимальность

3.переход к не худшему опорному плану

1.постр нач опор плана

Пусть задана задача

х=(х1,х2,..,хn)

Z=C1x1+C2x2+…+Cnxnmax(min)

a11x1+a12x2+…+a1nxn<b1

a21x1+a22x2+…+a2nxn<b2

………………………………

am1x1+am2x2+…+amnxn<bm

xj>0, j=1,n

приведем задачу к канонической форме Введем дополнительные переменные xn+1,xn+2,…,xn+m

х=(х1,х2,..,хn,xn+1,xn+2,…,xn+m)

Z=C1x1+C2x2+…+Cnxn+0xn+1+0xn+2+…+0xn+m

a11x1+a12x2+…+a1nxn+xn+1=b1

a21x1+a22x2+…+a2nxn +xn+2=b2

………………………………+…..

am1x1+am2x2+…+amnxn +xn+m=bm

xj>0, j=1,n+m

10.Если ограничения содержат одну из перемен-ных с кооф=1,а в остальных огран эта перемен имеет кооф=0,то огранназывогран в предпочти-

Тельном виде

Членам системы ограничений.

Строим симплтабл

Пусть исх задача на мах

Если все оценки 0, то выбр нач план оптимал. Пусть сущест такие оценки, которые прнима-

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

Целевая функция-ф-ция экстремум значения ко-торой необходимо найти.