Шпаргалка по "Высшей математике"

1) Задачи  использования ресурсов

Фирма выпускает сливочное и шоколадное мороженое. На его изготовление используется молоко и наполнители, расходы и  запасы которых даны в таблице.

Спрос на шоколадное мороженое не превышает 350 кг/сут

Спрос на сливочное мороженое не превышает  спрос на шоколадное

Рыночная  цена 1 кг сливочного мороженого – 160 р., шоколадного – 140 р.

Сколько мороженого каждого вида следует  выпустить, чтобы доход от его  реализации был максимальным

Составим  математическую модель задачи

x₁ – выпуск сливочного мороженого, кг/сут

x₂ – выпуск шоколадного мороженого, кг/сут

Найдем выручку при реализации мороженого:

(1) ЦФ – целевая функция

(2) система ограничений

(3) дополнительные ограничения  на неотрицательность

Общая задача использования ресурсов

При производстве нескольких видов продукции используется несколько видов сырья. Есть ограничения по запасам сырья, по спросу на готовую продукцию. Известна рыночная стоимость продукции. Найти план выпуска продукции, обеспечивающей максимальную прибыль

2) Задача  о составлении рациона питания

В рационе  используются продукты, содержащие несколько питательных веществ (витамины, калории). Известна потребность в этих веществах и цена продуктов. Составить рацион питания, обеспечивающий минимальные затраты на его приобретение

3) Задача  о загрузке оборудования

4) Задача  о раскрое материала 

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

( I )

n – количество видов продукции

( II )

m₁ – число таких неравенств

( III )

Функция L(x), для которой ищут максимум или минимум, называется целевой

n – число переменных ЦФ

m – число ограничений системы

Каноническая  форма записи ЗЛП

Стандартная форма ЗЛП

1)

2)

Определение: Допустимым решением ЗЛП называют вектор , удовлетворяющий системе ограничений II и дополнительному условию III.

Множество допустимых решений образуют область  допустимых решений

Оптимальным решением ЗЛП называют такое допустимое решение, при котором ЦФ достигает  оптимального значения (максимума/минимума) 

ЗЛП имеет  смысл в случае, если система ограничений  имеет бесчисленное множество решений. 

Теорема Кронекера - Капелли

Система линейных уравнений (СЛУ) совместна  тогда и только тогда, когда ранг расширенной матрицы равен рангу  основной

r(A_B)=r(A)=r

A=[a_ij]  A_B=[a_ij | b_i]

r<n 

Теорема о множестве решений

Если  общий ранг матрицы r меньше числа неизвестных, то система имеет бесчисленное множество решений

Если  r=n, то решение одно

Будем считать, что число уравнений  в системе m равно r.

Базисными переменными называют m переменных, если определитель матрицы коэффициентов при них отличен от нуля

Остальные (n-m) переменные называют свободными

Базисным  решением СЛУ называют решение, в  котором все свободные переменные равны нулю 

Симплекс  – многомерный  многогранник. Решение лежит в одной из вершин симплекса (берут одну из вершин в качестве нач. решения. Если оно опти  мально, задача решена; если нет, то надо провести обследование других вершин).  Чтобы с помощью симплекс-метода решить задачу, нужно привести ее к каноническому виду (общая задача лин. прогр-ния): ¦ = å СiXi®max

åАij Xj = Bi;  ( i = 1,…,m);  (j = 1,…,n); ( Xj >=0) . Для того, чтобы привести задачу к канонич. виду, нужно из неравенств сделать равенства ( для этого при знаке <= прибавляют, а при знаке >= вычитают дополнит. переменную). Общая задача лин. прог-ния не имеет решения, если *сис-ма уравнений ограничений несовместна; *она совместна и имеет 1 решение; *цел. ф-ция не ограничена в ОДР. Если кол-во ур-ний ограничений равно кол-ву управляющих переменных, то будет 1 решение. Кол-во неравенств ограничений должно быть меньше кол-ва управляющих переменных (m<n). Необходимо представить сис-му в виде (стандартном)

Алгоритм  решения задачи симплекс-методом: 1. Получение нач. плана (выбирается m переменных (базисных), обладающих след. св-вами: входят с коэфф-том  1  только в одно ур-ние и с коэф-том  0  во все остальные ур-ния). Остальные переменные наз. свободными. Полагаем их равными нулю, тогда базисные будут равны своб. членам ур-ний ограничений. Если все Bi ур-ний ограничений >=0 (неотрицательны), 

Критерий  оптимальностиЕсли в индексной строке допустимой симплексной таблицы         то соответствующее допустимое базисное решение    является оптимальным решением.

Доказательство.

На базисном решении  

целевая функция имеет значение   

Рассмотрим любое  допустимое решение  

Тогда   

поскольку

Для любого допустимого  решения х' получили неравенство                                             

 что означает оптимальность решения  х.

Критерий  доказан

Критерий неограниченности целевой функции.

Пусть существует    для которого столбец

Тогда целевая функция L неограничена сниузу на допустимом множестве.

Доказательство.

Рассмотрим для t>0 вектор  

, где   

Для любого t>0 вектор    допустим, так как     

и выполняются ограничения-равенства А   =b. Но значение целевой функции    

неограниченно убывает  при   так как         

Значит L(x) не ограничена снизу на допустимом множестве.

Критерий  доказан

Если  все коэф-ты в последней  строке при своб. переменных неотрицательны, то получ. решение  оптимально. Получ. решение  единственно, если все  эти коэф-ты положительны. Если среди неотрицат. коэф-тов встречается  хотя бы  1 нулевой, то задача имеет бесконечное множество решений. Если в последней строке присутствует хотя бы 1 отрицат. элемент при своб. переменных, а в соответствующем этому коэф-ту столбце нет ни одного положит. элемента, то задача нерешаема, т.к. цел. ф-ция не ограничена. Если хотя бы 1 из коэф-тов, стоящих при своб. переменных отрицат.,а в соответствующем этому коэф-ту столбце есть хотя бы 1 положит. элемент, то получ. решение может быть улучшено. 4. Получение нового решения (выбор переменной, вводимой в базисную. Для этого просматриваем ¦-строку симплекс-таблицы и выбираем макс. по модулю отрицат. элемент. Соответствующий этому эл-ту столбец наз. разрешающим; выбор переменной, выводимой из базисной. Для это го находят отношение для разрешающего столбца: B1/ A1p; B2 / A2p; … и выбирают мин.

(если  Ар нулевой или  отрицат., то частное  бесконечно). Так  мы нашли разрешающую  строку. Элемент,  лежащий на пересечении  разреш. строки и  разреш. столбца,  наз. разрешающим. Затем строим  макет новой таблицы, вводим в базисную новую переменную. Все коэф-ты разрешающей строки делим на разреш. элемент и пишем значения в новую таблицу. В новой таблице в столбце, соответствующем разреш. столбцу предыдущей таблицы, вместо коэф-тов записываются нули. Вместо разреш. коэф-та записывают 1. Остальные эл-ты для новой таблицы вычисляются с помощью симплекс-преобразования. Правило треугольника: для получения элемента новой симплекс-таблицы, надо от эл-та предыдущей с-таблицы, стоящего на том же месте, отнять след. выражение: произведение эл-та разрешающей строки, стоящего в одном столбце с данным  эл-том,  на элемент данной строки, стоящий в одном столбце с разреш. эл-том, деленое на разреш. элемент.  Затем проверяем получ. решение на оптимальность. В задачах на минимум в строке ¦

появляются  положит. коэф-ты при  своб. переменных и наша задача здесь – превратить их в отрицательные. Если ур-ние задано в канонич. виде, кол-во ур-ний ограничений = кол-ву базисных переменных. Заметим, что если при поиске очередного решения цел. ф-ция начинает увеличиваться (в задаче на мин.), то оптимальным считается предыдущее решение.

Исходная  задача

Фирма выпускает n видов продукции (виды продукции - ), использую m видов сырья ( ), запас которых ограничен по количеству . Известны расходы сырья (a_ij – количесть сырья S_i, необходимого для производства единицы продукции P_j). Известна цена C_j единицы продукции P_j

x_j – количество выпускаемой продукции P_j

Установить  такой план выпуска продукции, при  котором выручка была бы максимальной

исходная задача (Задача I)

Пусть фирма прекращает производство, а имеющиеся ресурсы продает. Найтицены на ресурсы (y₁, y₂, …, y_m), чтобы:

• стоимость всех ресурсов была минимальной (интересы покупателей)
• стоимость всех ресурсов должна быть не меньше выручки, которую фирма получит при реализации готовой продукции (интерес продавца)

Рассмотрим  производство единицы продукции  вида P₁, который продается по цене c₁. На производство должно быть затрачено сырье a₁₁, a₂₁, …, a_m1. Расчетная стоимость затраченных ресурсов: a₁₁y₁+a₂₁y₂+…+a_m1y_m≥c₁ на производство продукции P₁

двойственная задача (Задача II)

Цены  ресурсов называют учетными (неявными, теневыми). Эти цены условны, они определяются решением ЗЛП; цены не рыночные. Цены – рыночные цены, которые задачей не вычисляются.

Алгоритм  составления двойственной задачи.

1) Во  всех ограничениях З-I свободные члены должны находиться в правой части, а члены с неизвестными – в левой

2) Ограничения  неравенства З-I должны быть записаны так, чтобы знаки неравенств у них были одного направления, причем если ЦФ исследуется на максимум, то должен быть знак ≤, а если на минимум, то – ≥.

3) Каждому  неравенству системы ограничений  З-I поставить в соответствие переменную

4) Составить  ЦФ Z(y), коэффициентами которой являются свободные члены системы ограничений З-I

5) Сформулировать  задачу для ЦФ, противоположную  исходной ( )

6) Составить  систему ограничений З-II

1.  Коэффициенты системы ограничений  образуют транспонированную матрицу  коэффициентов системы ограничений  З-I

      2. Свободные члены системы ограничений  З-II являются коэффициентами ЦФ З-I

      3. Знаки неравенств поменять на  противоположные

7) Записать  условие неотрицательности переменных  З-II

Двойственные  задачи такого вида называются симметричными

Теорема 1. Если одна из пары двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их ЦФ равны

- оптимальное решение З-I

- оптимальное решение З-II

Если  ЦФ одной из задач неограниченна, то другая задача не имеет решения, так как ее система ограничений (СО) несовместна

З-I и З-II решают симплексным методом, при этом СО нужно записать в канонической форме, в виде уравнений. Для этого в З-I вводят дополнительную неотрицательную переменную

Существует  соответствие между переменными З-I и З-II

Теорема 2. Компоненты оптимального решения  двойственной задачи равны значениям  коэффициентов ЦФ при соответствующих  переменных исходной задачи

ЗЛП

Для изготовления продукции P₁ и P₂ используют ресурсы S₁, S₂, S₃, S₄ согласно таблице

Необходимо  составить такой план производства продукции, при котором выручка  от ее реализации будет максимальной

З-I    З-II

Перепишем З-I и З-II в каноническом виде

З-I    З-II

Для З-II запишем сиплексную таблицу, соответствующую оптимальному решению

18 –  запас

– количество S₁, необходимое для оптимального выпуска продукции

– остаток ресурса при оптимальном  производстве

Дополнительные  переменные З-I равны остаткам соответствующих ресурсов при оптимальном производстве

2 –  рыночная цена P₁

– теневая стоимость ресурсов, идущих на производство P₁

Дополнительные  переменные З-II при оптимальном производстве равны превышению теневой стоимости ресурсов, которые идут на производство соответствующей единицы продукции, над рыночной ценой единицы этой продукции

Эти дополнительные переменные – мера убыточности продукции. Если они положительны в оптимальном  решении, то соответствующую продукцию  выпускать не следует.

Теорема 3. Теневые цены равны значениям  частных производных по соответствующим свободным членам З-I

Определение: ресурсы, которые израсходованы  полностью, называются дефицитными

дефицитные ресурсы S₁, S₂

Цена  дефицитных ресурсов ненулевая

Недефицитные  ресурсы имеют остаток. Их теневые  цены нулевые

Изменим запас дефицитного ресурса S₁b₁=18 на Δb₁, тогда теневая стоимость на ресурсы равна

Найдем, в каких пределах можно менять значение Δb₁, чтобы теневые стоимости оставались прежними, при этом значение ЦФ изменилось

Выразим базисные переменные оптимального решения  и через свободные

(1)

(2)

Если (1) и (2) подставить в  , то получим (после преобразований)

При Δb₁=0 получается элементы L-строки в оптимальном решении. Коэффициенты – «скобки» - являются элементами L-строки. Необходимо, чтобы все они были неотрицательными

Таким образом, запас первого сырья  можно менять в пределах от 18-5=13 до 18+2,5=22,5

При этом теневые цены ресурсов остаются прежними ,

Если  взять дополнительно ресурса  S₁ до Δb₁=2,5, то ЦФ:

Норма заменяемости ресурсов

Рассмотрим 2 теневые цены

теневая цена ресурса 

теневая цена ресурса 

- норма заменяемости ресурсов  на . Сколько единиц ресурса i необходимо иметь дополнительно, чтобы компенсировать уменьшение ресурса j на 1 так, чтобы значение ЦФ не изменилось (прибыль осталась прежней)

По теореме 3 запишем изменение ЦФ при изменении  запасов ресурсов

Если  , то уменьшение ресурса S_j на 1 никаким увеличением ресурса S_i компенсироваться не будет

Если  , то ресурс S_j избыточен и его уменьшение на 1 компенсировать не следует

В некоторых  задачах по производству и распределению продукции переменные должны быть целыми числами.

Общая формулировка задачи ЦП

1) Решаем ЗЛП  симплекс-методом:

     - если решение целочисленное, то  задача решена

- если решение  нецелочисленное, то система ограничения дополняется условием, которое отсекает по ОДР нецелочисленное оптимальное решение так, чтобы все целочисленные решения остались в новой ОДР

- решается задача  с дополнительным условием:

     - если оптимальное решение целочисленное,  то это решение оптимальное

- если нецелочисленное,  то вводится еще одно условие  ограничения или будет установлено,  что задача не имеет целочисленного  решения 

2) Установление  наличия целочисленного решения

Если в симплекс-таблице, соответствующей оптимальному решению ЗЛП есть нецелочисленный свободный член, а в его строчке все коэффициенты целые числа, то целочисленного решения нет.

3) Составим дополнительное  условие -ограничение

Целой частью числа  α называется наибольшее целое число  не превосходящего числа α

[α] – целая  часть

Дробная часть  числа α   {α}=α - [α]

Пример: α=1,2 [1,2]=1

                          {1,2}=1,2-1=0,2

             α= -1,2  [-1,2]=-2

                             {-1,2}=-1,2-(-2)=0,8

Дополнительное  условие – ограничение Гомори

Если среди компонентов оптимального решения есть несколько дробных, то находим компонент с наибольшей дробной частью, по соответствующей строке симплекс-таблицы составляем ограничение, введя дополнительную переменную x_n+1

i – номер строки с наибольшей дробной частью свободного члена

x_m+1, x_m+2, …, x_n – свободные переменные

m – число базисных переменных

- свободный член в оптимальной  таблице

4) Полученное  ограничение записать в симплекс-таблицу  в дополнительную строку, добавив дополнительный столбец новой переменной x_n+1

Симплекс-таблица  не содержит опорного решения

5) Получить опорное  решение

Среди элементов  L-строки выбрать наименьший. Соответствующий ему столбец – разрешающий. Разрешающая строка – дополнительная строка. Если при симплексном преобразовании получено оптимальное решение, то задача решена

Если нет, то вводим еще одно дополнительное ограничение

Экономико-математическая модель – математическое описание исследуемого экономического процесса или объекта.

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

Это позволяет  эффективно и дешево исследовать  экономический результат.

Этапы построения математической модели:

I. Определение целей,

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

II. Определение параметров модели,

т.е. заранее  известных фиксированных факторов, на значение которого исследователь не влияет (рыночная цена, запасы сырья, тарифы перевозок и т.д.)

III. Формирование  управляющих переменных,

изменяя значение которых можно приближаться к  поставленной цели.

Значения таких  переменных являются решением задач (например, в ЗЛП – это количество выпускаемой продукции, в ТЗ – это объемы перевозок и т.д.)

IV. Определение ОДР,

т.е. тех ограничений, которым должны удовлетворять управляющие  переменные

V. Выявление факторов, которые могут изменяться случайно или другим непредсказуемым образом

VI. Выражение цели через управляющие переменные, параметры модели и неопределенные факторы, т.е. записать целевую функцию

α – параметры  модели L – целевая функция

x – управляющие переменные

X – ОДР

ε – случайные  величины или непредсказуемая неопределенность

при

2.1. Закрытая модель  транспортной задачи 

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

  Доказательство. Пуст ь = M > 0 .

  Тогда величины x_ij = a_ib_j /M (i = 1,2,3, ... m; j = 1,2,3, ..., n) являются планом, так как они удовлетворяют системе ограничений

  ( 2 ) и ( 3 ) .

  Действительно, подставляя значения в (2) и (3) , находим

   = a_i ,

    = b_j .

  Выберем из значений C_ij наибольшее C¢ = max C_ij и заменим в линейной функции ( 1 ) все коэффициенты на C¢ тогда, учитывая ( 2 ) , получим

   ,

  Выберем из значений C_ij наименьшее C¢¢=min C_ij и заменим в линейной функции все коэффициенты на C¢¢ ; тогда, учитывая ( 2 ) имеем

  Объединяя два последних неравенства в  одно двойное , окончательно получаем

  C¢¢M ? Z ? C¢ M,

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

 
2.2. Открытая модель  транспортной задачи 

   
2.2. Открытая модель транспортной задачи 

  Транспортная  задача, в которой суммарные запасы и потребности не совпадают, т. е. не выполняется условие  , называется открытой. Для открытой модели может быть два случая:

1. суммарные запасы превышают суммарные потребности  ;
2. суммарные потребности превышают суммарные запасы  .

  Линейная  функция одинакова в обоих  случаях, изменяется только вид системы  ограничений.

  Найти минимальное  значение линейной функции

    при ограничениях

   , i = 1, 2, ..., m, (случай а)

   , j = 1, 2, ..., n;

   , i = 1, 2, ..., m, (случай б)

   , j = 1, 2, ..., n,

  x_ij ³ 0 (i = 1, 2, ..., m; j = 1, 2, ..., n).

  Открытая  модель решается приведением к закрытой модели.

  В случае (а), когда суммарные запасы превышают  суммарные потребности, вводится фиктивный  потребитель B_n+1, потребности которого b_n+1 =  . В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик A_m+1, запасы которого a_m+1 =  .

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

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

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

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

·Метод сев-зап. угла: 1-оцениваем верхнюю левую клетку, 2-выбираем мин. из значений спроса и предложения, 3-выбираем мин. и записываем в клетку данные.

·Метод миним. элемента: грузы распределяются в первую очередь в те клетки, в к-ых находится мин. тариф. Далее поставки распределяются в незанятые клетки с наименьшими тарифами с учетом оставшихся запасов у поставщиков и удовлетворения спроса потребителей. Процесс распределения продолжаетсся до тех пор, пока все грузы от поставщиков будут вывезены, а потребители удовлетворены.  При распределении может оказаться, что кол-во занятых клеток меньше, чем m+n-1. В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки наз. условно занятыми.

Найденное исходное опорное решение проверяется  на оптимальность методом потенциалов. В распределительную таблицу добавляют строку  v_j и столбец u_i. Числа u_i и v_j наз. потенциалами.

1-Для заполненных клеток составляют  с-му ур-ний-   u_i+v_j=c_ij,

где i-номер  строки, j-номер столбца,  c_ij- тариф, u-покупатели, v-поставщики.  Затем один из потенциалов допустим u₁=0, тогда можно найти и все остальные.

2-Для каждой свободной клетки сост. сумма потенциалов.

D_ij= u_i+ v_j - c_ij   Если  D_ij £ 0, то опорное решение является оптимальным. Если хотя бы одна из оценок D_ij > 0, то найденный план не оптимален и его можно улучшить, перейдя к новому опорному решеннию.

3- Необходимо перераспределить грузы, перемещая их из занятых клеток в свободные.

4-Для клетки D_ij > 0 строим цикл (фигуру, в 3-х вершинах к-ой нах. заполненные клетки, а в одной незаполненная).  В своб. вершине цикла ставили плюс, а в остальных вершинах “+” и “-” через один.

5-Выбираем наим. значение с минусом. Затем это значение вычитаем из клеток, стоящих со знаком “-” и прибавляют к клеткам  со знаком “+”. В результате получим новое опорное решение. Найденное решение проверяем на оптимальность, и т.д. до тех пор, пока не получим оптимальное решение.

Имеется n работ и n кандидатов для их выполнения. C_ij-это затраты i кандидата на j работы каждый кандидат может быть назначен на 1 работу. Каждая работа может быть выполнена 1-им кандидатом. Найти такое назначение кандидатов на работы, при кот общие затраты на выполнение работ были бы минимальны. Затраты– этолибо некоторые денежные суммы, либо время на выполнение работы. Составим математическуюиодель задачи о назначениях. Назначения на работы будем определять с помощью переменных X_ij.  X_ij={1, если работник i назначен на работуj; 0, если работник не назначен на работу j}

Ограничения по назначению:

работа j может быть распределена 1-му работнику;

каждый  работник назначается на одну работу.Xij=0/1.

Таким образом, задача о назначениях–задачацелочисленного линейного программирования, поэтому решаем ее методом  Гомори.

Венгерский  метод решения задач о назначении.

Этим  методом решаются задачи, если задача исследуется на минимум. Он состоит из следующих шагов:

1. Преобразование строк и столбцов матрицы[eij];

2. Определениее назначения;

3.Модефикация преобразованной матрицы.

Алгоритм:

1.Вычесть  от всех элементов каждой строки наименьший ее элемент. Тоже самое сделать для столбцов.

2.Поиск  оптимального решения: 

· Находим  строку или столбец с наименьшим числом нулей.

· Отмечаем  1 из нулей этой строки или столбца и зачеркиваем все остальные нули этой строки или столбца  и того столбца или строки, в которых находится отмеченный ноль. Аналогичные операции проводим для всех строк или столбцов.Если число отмеченных нулей равно n,то получено оптимальное значение. Если же отмеченных нулей меньше, чем n,то переходим к шагу 3.

3.Модификация  преобразованной  матрицы.

1) Проводим  миниальное число прямых через некоторые столбцы и строки так, чтобы все нули оказались вычеркнутыми.

2) Среди  невычеркнутых находим наименьший,вычитаем его из невычеркнутых элементов.

3) К  дважды вычеркнутым элементам прибавляемем наименьший.

4) Переходим  к шагу №2.

4. Если решение оптимальное,то оптимальному нулю соответствуетединица, а остальные соответственнонули

I. Если  исходная задача о значениях является задачей целевой функции на максимум,то задачу сводят к исследованию целевой функции на минимум.Среди элементов матрицы найти наибольшийий. Вычитаем из этого числа последовательно все элементы матрицы и результаты записываем в новую матрицу.Для новой матрицы решаем задачу минимизации.Ее решение являетсярешением исходной задачи на максимум.

g_i(х₁, х₂, …, х_n)=b_iI=1,m₁

g_i(х₁, х₂, …, х_n)>=b_iI=m₁+1,m₂

g_i(х₁, х₂, …, х_n)<=b_iI=m₂+1,m

и доставляющий экстремум (наибольшее и наименьшее значение) цел. функции L=f(х₁, х₂, …, х_n), где х₁-переменные, j=1,n;  L, f, g_i, - заданные функции от n переменных, b_i – фиксированные значения. Нелин. программирование применяется при прогнозировании промышленного произв-ства, управлении товарными ресурсами, планировании обслуживания и ремонта оборудования и т.д. Для задачи нелин. программирования в отличии от линейных задач нет единого метода решения. В зависимости от вида цел. функции и системы ограничений разработаны специальные методы решения, к к-ым относится метод множителей Лагранжа, квадратичное и выпуклое программирование, градиентные методы, приближенные методы решения, графические методы.

Графические методы:  1) Область  допускаемых  решений. 2) Линия уровня целевой функции  являются параллельные  прямые с угловым коэффициентом. 3) нахождение глобального экстремума. 

L= f(х₁, х₂, …, х_n)®max(min) при ограничениях

g_i(х₁, х₂, …, х_n)=0 I=1,m₁

Предположим, что функция f(х₁, х₂, …, х_n) и g_i(х₁, х₂, …, х_n) непрерывны вместе со своими первыми частными производными. Ограничения заданы в виде уравнений, поэтому для решения задачи воспользуемся методом отыскания условного экстремума функций нескольких переменных. Для решения задач составляется функция Лагранжа.

F(х₁, х₂, …, х_n, l_1,l₂,…,l_m)= f(х₁, х₂, …, х_n)+Sl_ig_i(х₁, х₂, …, х_n)

Где l - множитель Лагранжа.

Затем определяются частные  производные:

j=1,n,  ¶F/¶l_I, I=1,m.

Приравнивая к нулю частные производные, получим систему:

¶F/¶l_I= g_i(х₁, х₂, …, х_n).

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

Определение: Задача называется ЗДЛП, потому что  ЦФ – дробно-рациональная функция

В случае двух переменных ЗДЛП может быть решена графически

1) ОДР

2) Определить линии уровня ЦФ (L=const)

3) Определить  направление вращения графика  линии уровня ЦФ при увеличении  L (производная)

4) Определить точки экстремума ЦФ