Целевая функция-ф-ция экстремум значения ко-торой необходимо найти.
Мат.прог.-область математики,разрабатываю-щая теорию и численные методы решения много-мерных,экстримальных задач с ограничениями,т.е. задачи на эксремум ф-иимногих переменных с ограничениями на область изменения этих пере-менных.
Целевая функция-ф-ция экстремум значения ко-торой необходимо найти.
Экономические возможности формализуются в виде системы ограничений.
Мат.модель задачи вкл.
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, то выбр нач план оптимал. Пусть сущест такие оценки , которые прнима-
Мат.прог.-область математики,разрабатываю-щая теорию и численные методы решения много-мерных,экстримальных задач с ограничениями,т.е. задачи на эксремум ф-иимногих переменных с ограничениями на область изменения этих пере-менных.
Целевая функция-ф-ция экстремум значения ко-торой необходимо найти.