12. Метод потенц-в в решении трансп-й задачи.

Необх-мо сделать оценку свобод.клеток. Сущ-ть метода потенциалов состоит в том, что д/кажд.строки и кажд.столбца таблицы опр-ют спец.числа, называемые потенциалами. С помощью них можно установить, нужно ли заполнять свобод.клетку таблицы или ее можно оставить незаполненной. Потенциалы строк и столбцов опр-ся по заполнен.клеткам, нах-щимся на их пересечении. Эл-т заполнен.клетки должен равняться сумме потенциалов строки и столбца, на пересеч-и ктр нах-ся эта заполнен.клетка. Д/начала вычислений I потенциал д/строки или столбца приним-ся условно = 0, а все остальные потенциалы опр-ся с помощью эл-тов заполнен.клеток. Обознач-я: V_j – потенциалы столбцов, U_i – строк, С_ij – эл-ты заполнения клеток. С_ij = U_i + V_j . После того, как потенциалы столбцов и строк опр-ны, выясняется, явл-ся ли план оптимальным или нет. С этой целью д/кажд.свобод.клетки вычисл-ся сумма потенциалов строк и столбцов, на пересеч-и ктр нах-ся эта клетка. Сравнение суммы потенциалов с величиной эл-та в свобод.клетках позволяет опр-ть, нужно ли заполнять эту клетку или ее нужно оставить свобод. При решении задачи на min (max) не заполн-ся те свобод.клетки, в ктр сумма потенциалов < (>) величины эл-та. Если хар-ка, знач-е ктр = С_ij – (U_i + V_j ) положит. (отриц.), то свобод.клетка не заполн-ся при решении задач на min (на max). Свобод.клетки, имеющие нулевое знач-е хар-ки, показывают на то, что их заполнение приведет к перераспред-ю поставок, но объем работ останется неизменным. После этого числа заносим в таблицу и опр-ем связь с неск-кими незаполнен.клетками. Эта связь выявл-ся путем построения замкнутых многоуг-ков, вершинами ктр явл-ся клетки таблицы. Углы в этих многоуг-ках должны быть прямыми. Одна вершина нах-ся в свобод.клетке, а все остальные – в заполнен. Многоуг-к имеет четное кол-во вершин. В этом цикле пересчета + помечены те клетки, поставка в ктр увелич., и «-» – уменьш-ся. Замечание: иногда д/произвол.означенного цикла вводится понятие оценка цикла – алгебраич.сумма коэф-тов, стоящих в вершинах цикла, взятых с соотв-щими знаками. Д/кажд.свобод.клетки базис.распред-я поставок сущ-ет и при том единствен.цикл пересчета. Причем, операция означивания цикла явл-ся корректной. Т.(о потенциалах): оценка свобод.клетки не измен-ся, если к коэф-там затрат некоторой строки (столбца) таблицы поставок прибавить некоторое число. Изменение коэф-тов затрат можно начинать с любого столбца (строки). Потенциал столбца (строки), избранного д/начала, может быть произвольным. Остальные соотв-но необх-мо пересчитывать.

13. Общий вид задач нелинейного программир-я. Графический метод решения задач нелинейного программир-я.

Во многих эк.моделях исследов-я операций завис-ти между постоянными и перемен.факторами лишь в I приближ-и можно считать лин., более детальное рассмотр-е позволяет обнаружить их нелин-ть. Как пр-ло, такие показ-ли, как прибыль, с/стои­м-ть, капитал.затраты на произв-во и др., в действи­т-ти зависят от объема произв-ва, расхода ресурсов и т.п. нелинейно. К класс.методам оптимизации относ-ся классы Нелин.задач и др. Задачу оптимизации можно сформулировать так: найти переменные х₁…х_n, удовлетворяющие сис-ме ур-й

, где i=1,…, m, и обращающие в max (min) целевую f-ю

. При этом переменные х₁…х_n не явл-ся дискретными. F-и

и f(х) явл-ся непрерывными и имеют, по

кр.мере, частные производные II порядка. #задача Нелин.прогр.: дан.предпр-е д/произв-ва какого-то продукта расходует 2ср-ва в кол-ве х₁ и х₂. Это факторы произв-ва (машины и труд), 2различных вида сырья… Факторы машины и труд взаимозаменяемы или в с/хоз-ве взаимоз.факторами считаются посевные площади и кол-во удобрений. Vпроизв-ва, выраженный в натурал.или стоим.ед-цах, явл-ся f-ей затрат произв-ва

. Эта завис-ть наз-ся произв-венной f-ей. Издержки зависят от расхода обоих факторов (х₁ и х₂) и от цен этих факторов (с₁ и с₂). Совокупные издержки выраж-ся формулой

. Требуется при дан.из­держках опр-ть такое кол-во факторов произв-ва, ктр max-ет V продукции Z. Мат.модель этой задачи имеет вид: опр-ть та­кие переменные х₁ и х₂, удовлетвор-щие усл-ям:

1) ; 2) ;

3) . Положим, что

дваж­ды диф-ма в т.

,

и в некоторой ее окрест-ти. Точка X*, в ктр все частные производные f-и

= 0, наз-ся стационарной точкой. Локал.экстр. Необх.усл-е экстремума. Если в точке х₀ f-я имеет экстремум, то

. Дост.усл-я экстремума: 1)если х₀ – точка max (min), то при переходе через нее меняет знак с + на – (с – на +). 2)если х₀ – точка max (min), то ( ). 3)если , то вопрос о сущ-и экстремума остается открытым. Дост.усл-е сущ-я экстремума: 1)если В²-АС<0, то сущ-ет экстремум, причем, если А<0, то х₀ – точка max, если А>0, то х₀ – точка min. 2)если В²-АС>0, то в точке х₀ экстремума нет. 3)если В²-АС=0, то вопрос о сущ-и экстремума остается откр. Глобал.экстр. F-я

имеет в точке Х₀ заданной обл-ти D глобал.max – наибольшее знач-е в обл-ти D (min – наим.знач.), если нерав-во

( ) соотв-но выполн-ся д/любой точки X  D. Т.(Вейерштрасса): Если обл-ть D замкнута и ограничена, то диф.f-я

достигает в этой обл-ти своих

наибольшего и наим.знач-й или в стац.точке, или в граничной точке обл-ти. Чтобы найти глобал.экстремум: 1)найти все стац.точки  обл-ти D, найти в них знач-я f-и. 2)найти знач-я –и в граничных точках обл-ти D. 3)сравнить эти знач-я и сделать вывод. Услов.экстр. Пусть необх-мо найти экстре-

мум f-и при усл-и, что переменные х₁…х_n удовлетв-ют ур-ям = 0 (*). Предполаг-ся, что f-и

и f(х) имеют непрерыв.част­.производные по всем пер-ным, тогда = 0 наз-ют ур-ем связи. Точка , удовлетворяющей ур-ю *, явл-ся точкой усл.max (min) f-и

, если ( ) имеют место д/всех точек X, корд-ты ктр удовлетворяют ур-ям связи.