Требования, предъявляемые к экон. задачам, решаемым м-дами матем. программ-ия

Методами ЛП можно решать экономические проблемы которые удовлетворяют следующим условиям: 1. Все эк, технол, соц и др требования, опр оптим решение проблемы, должны допускать их матем формулировку в виде лин уравнений и неравенств; 2. Система линейных соотношений, харак. все условия данной системы, должна иметь множ-во допустимых решений, т.е. экономическая проблема должна допускать альтер решения; 3. Осн цель, которую нужно достичь в рез-те реш-я проблемы, д.б. четко выражена экон-ки и сформулирована в виде линейного соотношения.

- все треб-я и усл. дан-й задачи м.б. выразить матем-ки в виде урав-й и нер-в;

-дан-я экон. задача д. допускать многовариантность реш-я;

- наличие четкой матем-ой формулировки целей задачи с возм-ю получ-я однозначного ответа;

-перем-ые д.б. не «-»

 

Различные формы ЗЛП. Алгоритм.

1) общая: - с-ма огр-й неоднородна (≥, ≤); -не на все перем-е наложено усл-е неотриц-ти; -цел.функ может стремиться к мах и min.

2)каноническая (СМ): - с-ма орг-й однородна и представлена урав-ми; -на все перем-е наложено усл. неотриц-ти; - цел.функ →max

3)стандартная (для графич. реш-я осн. ЗЛП, при усл-и что число перем-х =2): -с-ма огр-й однородна и представлена нер-ми, причем число нер-в д. совпадать с рангом с-мы; - на все перем-е наложено усл. неотриц-ти; - цел.функ →max, min.

Алгоритм СМ (симплекс м/да).

Канонич. форма мод. осн. ЗЛП хар-ся след. 3 призн.: 1. 1родн. с-ма огран-й в виде с-мы ур-ний, 2. на все переем. налож. усл-я неотриц-сти, 3.цел. функ. стрем. к максим.

Д/того, чт. преобраз-ть с-му нер-в в с-му ур-й, ввод-ся доп. переем., наз-мые балансовыми со зн. «+» в нер-вах типа ≤ и со зн. «-«в нер-вах типа ≥.

Широко исп-мый на практ. м-д реш-я ЗЛП – СМ. Он осн-н на переходе от 1 опорн. реш-я к др. (промежут.), при кот. знач-е целев. функ. улучш-ся, т.е. при реш-ии на макс-м знач-е увел-ся, при реш-ии на мин-м – уменьш-ся. В случ. если зад. им. оптим. план, т.е. им. хотя бы 1 реш-е, то с-ма совместна, несовместна – если не им. реш-я.

При реш-ии зад. СМ выдел. след. стадии:1. приведение злп к канон.форме и единич. базису и нах-ние первонач. вар-та допуст.плана(1-ого опорного реш-я); 2. проверка найд-ого вар-та плана на оптим-ть. Если получ-й пл. оптим-й, то реш-е найдено, если нет- пл. следует улучшить; 3. послед-ое улучш-е пл. до нах-ия оптим-ого или до выявл-я того, что злп не им.реш-я.

1-ая симплекс.табл. – выраж-е 1-ого аккорд-ого пл. Коэф-ы в Z строке показ-т как изм-ся знач-я ЦФ при единич. изм-ии соот-щей св.п.Z строка – оценочная. В 1-ом столбце табл. перечис-ся бп. Во 2-ом запис-ся оц-ки бп (из цел. строки).В 3-ем указ-т св.члены.В осталь. стол-х запис-т коэф-ы при св.п по соот-щим ур-ням. Над рабочей частью табл. перечис-ся св.п. Сверху над св.п помещают оц-ки св.п (из цел. строки). Над столб-м св.членов запис-ся св.чл ЦФ, если есть, с противоп-м знаком. Оц-ки Z строки рассч-ся: а_0j= ∑ С_i*а_ij – C_j, где j=1…n, a_ij – коэф. j-го столбца, С_i- коэф. при бп в урав-ии Z, C_j – коэф. при св.п в урав-и Z

Ключевая теорема СМ

Если после очередного шага: 1. найдется хотя бы 1 «-» оц-ка, а в столбце, где она нах-ся есть хотя бы 1 «+». эл-т, то опорное реш-е м. улуч-ть, выполнив след. итерацию; 2. найд-ся хотя бы 1 «-» оц-ка, столбец которой не содер-т «+». эл-тов, то Z не огран-на в обл. допустимых знач. (Zmax); 3. все оц-ки окажутся не «-», то дистигнуто оптим. реш-е.

Согласно этой теореме: 1)просматрив-ся оц-ки Ζстроки, если они неотр-ны, то получено оптим. реш-е при реш-ии зад. на макс., если все оц-ки ≤0, то получено опт. реш-е при реш. зад. на мин. 2)если оптим. реш. не получ., то выбир-ся разрешающ. столб. по наиб. абсолют. вел-не «-«ой Ζстр. при реш. на макс. и по наиб. «+»ой оц. при реш. на мин. 3)сост-ся симплекс. отн-я – отн-я своб. членов к «+»ым коэф-там разреш. столб. Мин-ое из этих отн-й опр-т разреш. строку. Коэф., нах-ся на пересеч-и разреш. стр. и разр. столб., наз-ся разр. эл-том, если в разр. столб. нет ни 1 «+»го эл-та, то зад. не им. реш-я по прич. неогран-сти цел. функ. 4)осущ-ся перех. к нов. табл. Базис. переем. замен-ся на своб., соответ. разреш. столб. 5)бывш. разр. эл-т замен-ся обрат. по вел-не. 6)все эл-ты бывш. разреш. столб. дел. на разреш. эл-т и мен-т знак на противопол. 7)все остальн. эл-ты бывш. разреш. стр. дел-ся на разр. эл-т. 8)все остальн. эл-ты табл. пересчит-ся по прав. прямоуг-ка: аij = исход. эл-т – (коэф. разр. стр.* коэф. разр. столб./ разр. эл-т). 9) осущ-ся проверка Ζстр. 10) если ош-к нет, алгоритм повтор. снач.