Реферат: Некоторые задачи оптимизации в экономике

--PAGE_BREAK--Итак, доказано, что множество всех допустимых решений ЗЛП является выпуклым, которое будем называть многогранником решений.
Ответ на вопрос, в какой точке многогранника решений возможно оптимальное решение ЗЛП, даёт следующая теорема.
 Теорема 3. Если ЗЛП имеет оптимальное решение, то линейная функция Fпринимает максимальное (минимальное) значение в одной из угловых точек многогранника решений. Если линейная функция принимает максимальное значение более чем в одной угловой точке, то она принимает его в произвольной точке, являющейся выпуклой линейной комбинацией этих точек.
<lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1047" type="#_x0000_t75" o:divferrelative=«f» fillcolor=«silver»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><shapetype id="_x0000_t9" coordsize=«21600,21600» o:spt=«9» adj=«5400» path=«m@0,l,10800@0,21600@1,21600,21600,10800@1,xe»><path gradientshapeok=«t» o:connecttype=«rect» textboxrect=«1800,1800,19800,19800;3600,3600,18000,18000;6300,6300,15300,15300»><img width=«207» height=«195» src=«dopb73478.zip» v:shapes="_x0000_s1046 _x0000_s1047 _x0000_s1048 _x0000_s1049 _x0000_s1050 _x0000_s1051 _x0000_s1052 _x0000_s1053 _x0000_s1054 _x0000_s1055 _x0000_s1056 _x0000_s1057 _x0000_s1058">□ Будем полагать, что многогранник решений является ограниченным. Обозначим его угловые точки через Х1, Х2, …, Хn, а  оптимальное решение через Х*. Тогда F(Х*) ≥F(X), для всех точек многогранника решений. Если Х* угловая, то первая часть теоремы доказана. Предположим, что Х* не является угловой точкой, тогда Х*, на основании теоремы 1, можно представить как выпуклую линейную комбинацию угловых точек многогранника решений, т.е. Х*=α1x1+α2x2+…+αрxр, αj≥0, (j=1,…,n), <shape id="_x0000_i1071" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image039.wmz» o:><img width=«61» height=«47» src=«dopb73471.zip» v:shapes="_x0000_i1071">. Т.к.
F(Х*)=F(α1x1+α2x2+…+αрxр)=α1F(x1)+α2F(x2)+…+αрF(xр).            (3.4)
В этом выражении среди значений F(Xj)(j=1,2,…,p) выберем максимальное. Обозначим его через М, т.е. М=maxF(Xj). Тогда
α1F(x1)+ α2F(x2) +…+ αрF(xр)≤ α1М+ α2М +…+ αрМ = М(α1+α2+…+αр) =М.
Значит F(Х*)≤М. Пусть М=F(Xk), т.е. соответствует угловой точке Xk(1≤к≤р).
Тогда F(Х*) ≤ F(Xk). Но по предположению Х* — оптимальное решение, поэтому F(Х*)≥F(Xk)=М, следовательно, F(Х*)=М=F(Xk), где Xk — угловая точка. Итак, существует угловая точка Xk, в которой линейная функция принимает максимальное значение.
Для доказательства второй части теоремы допустим, что F(Х) принимает максимальное значение более чем в одной угловой точке, например в точках Х1, Х2, … Хq, где 1≤ q≤ р; тогда F(Х1)=F(Х2)=…=F(Хn)=M.
Пусть Х выпуклая линейная комбинация этих угловых точек, т.е. Х= α1Х1+α2Х2+ …+αqХq, αj≥0, (j=1,…,q), <shape id="_x0000_i1072" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image054.wmz» o:><img width=«61» height=«48» src=«dopb73479.zip» v:shapes="_x0000_i1072">. В этом случае, учитывая, что функция F(Х) – линейная, получим F(Х)=F(α1Х1+α2Х2+…+αqХq)=α1F(Х1)+ +α2F(Х2)+…+αqF(Хq)=α1M+α2M+…+αqM=M<shape id="_x0000_i1073" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image056.wmz» o:><img width=«40» height=«48» src=«dopb73480.zip» v:shapes="_x0000_i1073">=M, т.е. линейная функция F принимает максимальное значение в произвольной точке Х, являющейся выпуклой линейной комбинацией угловых точек Х1, Х2, … Хq ■   
 Замечание. Требование ограниченности многогранника решений в теореме является существенным, т.к. в случае неограниченной многогранной области не каждую точку можно представить выпуклой линейной комбинацией её угловых точек.
Доказанная теорема является фундаментальной, т.к. она указывает принципиальный путь решения ЗЛП.
Рассмотрим геометрический метод решения ЗЛП в случае функции двух переменных.
Было доказано, что оптимальное решение ЗЛП находится, по крайней мере, в одной из угловых точек многогранника решений.
Рассмотрим задачу в стандартной форме с двумя переменными.
F=c1x1+c2x2+с→min(max),
<img width=«14» height=«86» src=«dopb73481.zip» v:shapes="_x0000_s1059">При ограничениях    а11х1+ а12х2 ≤b1,
                                    а21х1+ а22х2 ≤b2,
                                     ………………
                                     an1х1+ аn2х2≤bn ,
при условии, что x1≥0  ,x2≥0 .
Пусть геометрическим изображением системы ограничений является многоугольник ABCDE. Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c1x1+c2x2+с0принимает максимальное (или минимальное) значение. Рассмотрим линии уровня функции F или
<lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1061" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><shapetype id="_x0000_t56" coordsize=«21600,21600» o:spt=«56» path=«m10800,l,8259,4200,21600r13200,l21600,8259xe»><path gradientshapeok=«t» o:connecttype=«custom» o:connectlocs=«10800,0;0,8259;4200,21600;10800,21600;17400,21600;21600,8259» o:connectangles=«270,180,90,90,90,0» textboxrect=«4200,5077,17400,21600»><img width=«217» height=«195» src=«dopb73482.zip» v:shapes="_x0000_s1060 _x0000_s1061 _x0000_s1062 _x0000_s1063 _x0000_s1064 _x0000_s1065 _x0000_s1066 _x0000_s1067 _x0000_s1068 _x0000_s1069 _x0000_s1070 _x0000_s1071 _x0000_s1072 _x0000_s1073 _x0000_s1074 _x0000_s1075 _x0000_s1076 _x0000_s1077">c1x1+c2x2=С                                             ( 3.5).
Это уравнение прямой. Линии уровня функции F параллельны, т.к. их угловые коэффициенты определяются только соотношением между коэффициентами c1 и c2 и, следовательно, равны. Т.о., линии уровня функции F – это своеобразные «параллели», расположенные обычно под углом к осям координат.
Важное свойство линий уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении в другую сторону – только убывает. При фиксированном С рассмотрим линейную функцию. Чем больше значение С, тем больше значение линейной функции. Определив направление возрастания линейной функции, найдём точку, принадлежащую многоугольнику, в которой функция принимает максимальное или минимальное значение.
Геометрическим изображением системы ограничений может служить и многоугольная область. Рассмотрим следующую задачу.
1.В суточный рацион включают два продукта питания П1 и П2, причём продукта П1 должно войти в дневной рацион не более 200 ед. Стоимость питательных веществ в 1 ед. продукта, минимальные нормы потребления указаны в таблице. Определить оптимальный рацион питания, стоимость которого будет наименьшей.
 Решение.
Обозначим х1 – количество продукта питания П1,
                    х2 – количество продукта питания П2.
 F=2 х1 +4 х2 →min. (суммарная стоимость) При ограничениях
<img width=«15» height=«60» src=«dopb73483.zip» v:shapes="_x0000_s1078">  х1 ≤ 200,
  0,2 х1 +0,2 х2 ≥120,
 0,4 х1 +0,2 х2 ≥160.
<lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1080" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><img width=«233» height=«209» src=«dopb73484.zip» v:shapes="_x0000_s1079 _x0000_s1080 _x0000_s1081 _x0000_s1082 _x0000_s1083 _x0000_s1084 _x0000_s1085 _x0000_s1086 _x0000_s1087 _x0000_s1088 _x0000_s1089 _x0000_s1090 _x0000_s1091 _x0000_s1092 _x0000_s1093 _x0000_s1094 _x0000_s1095 _x0000_s1096 _x0000_s1097 _x0000_s1098 _x0000_s1099 _x0000_s1100 _x0000_s1101 _x0000_s1102 _x0000_s1103 _x0000_s1104">Графическим решением системы ограничений  является множество точек плоскости, называемое областью допустимых решений (ОДР). Линии уровня 2х1+4х2=0 <shape id="_x0000_i1074" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image062.wmz» o:><img width=«23» height=«16» src=«dopb73485.zip» v:shapes="_x0000_i1074">х2=-<shape id="_x0000_i1075" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image064.wmz» o:><img width=«16» height=«41» src=«dopb73486.zip» v:shapes="_x0000_i1075">х1.
Получаем, что минимальное значение, при заданных ограничениях на переменные, достигается в точке А(200;400). F(A)=2000.
Ответ: наименьшая стоимость 2000 будет при рационе 200 ед. продукта П1 и 400 ед. продукта П2.
Не всегда бывает единственное оптимальное решение. Рассмотрим другую задачу.
2. F=4x1+4x2 →max. При ограничениях
<img width=«14» height=«86» src=«dopb73487.zip» v:shapes="_x0000_s1105">   2x1+x2≥7,
   x1-2x2≥-5,
   x1+x2≤14,
  2x1-x2≤18.
Решив, систему ограничений найдём ОДР. Линия уровня будет иметь вид 4x1+4x2=0 <shape id="_x0000_i1076" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image062.wmz» o:><img width=«23» height=«16» src=«dopb73485.zip» v:shapes="_x0000_i1076">x2=-x1.
<lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1107" type="#_x0000_t75" o:divferrelative=«f» filled=«t»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><img width=«265» height=«186» src=«dopb73488.zip» v:shapes="_x0000_s1106 _x0000_s1107 _x0000_s1108 _x0000_s1109 _x0000_s1110 _x0000_s1111 _x0000_s1112 _x0000_s1113 _x0000_s1114 _x0000_s1115 _x0000_s1116 _x0000_s1117 _x0000_s1118 _x0000_s1119 _x0000_s1120 _x0000_s1121 _x0000_s1122 _x0000_s1123 _x0000_s1124 _x0000_s1125 _x0000_s1126 _x0000_s1127 _x0000_s1128 _x0000_s1129 _x0000_s1130 _x0000_s1131">В данной задаче линия уровня с максимальным уровнем совпадает с граничной линией многоугольника решений. Найдём точку пересечения линии II с линией III:
<shape id="_x0000_i1077" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image069.wmz» o:><img width=«115» height=«41» src=«dopb73489.zip» v:shapes="_x0000_i1077">
х1=<shape id="_x0000_i1078" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image071.wmz» o:><img width=«23» height=«41» src=«dopb73490.zip» v:shapes="_x0000_i1078">.
Найдём точку пересечения линии III с линией IV: 14- х1=2 х1-18. Отсюда х1= <shape id="_x0000_i1079" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image073.wmz» o:><img width=«23» height=«41» src=«dopb73491.zip» v:shapes="_x0000_i1079"> . Следовательно, х1=c, x2=14-c, c<shape id="_x0000_i1080" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image075.wmz» o:><img width=«13» height=«13» src=«dopb73492.zip» v:shapes="_x0000_i1080">[<shape id="_x0000_i1081" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image077.wmz» o:><img width=«23» height=«41» src=«dopb73490.zip» v:shapes="_x0000_i1081">;<shape id="_x0000_i1082" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image073.wmz» o:><img width=«23» height=«41» src=«dopb73491.zip» v:shapes="_x0000_i1082">]. Пусть х1=9 <shape id="_x0000_i1083" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image075.wmz» o:><img width=«13» height=«13» src=«dopb73492.zip» v:shapes="_x0000_i1083">[<shape id="_x0000_i1084" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image077.wmz» o:><img width=«23» height=«41» src=«dopb73490.zip» v:shapes="_x0000_i1084">;<shape id="_x0000_i1085" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image073.wmz» o:><img width=«23» height=«41» src=«dopb73491.zip» v:shapes="_x0000_i1085">], х2=5.
F=4·9+4·5=56.
Ответ: Fmax=56 при множестве оптимальных решений х1=c, x2=14-c, где c<shape id="_x0000_i1086" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image075.wmz» o:><img width=«13» height=«13» src=«dopb73492.zip» v:shapes="_x0000_i1086">[<shape id="_x0000_i1087" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image077.wmz» o:><img width=«23» height=«41» src=«dopb73490.zip» v:shapes="_x0000_i1087">;<shape id="_x0000_i1088" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image073.wmz» o:><img width=«23» height=«41» src=«dopb73491.zip» v:shapes="_x0000_i1088">].
Рассмотренный геометрический метод решения ЗЛП обладает рядом достоинств. Он прост, нагляден, позволяет быстро и легко получить ответ.
Однако есть и недостатки. Возникают «технические» погрешности, которые неизбежно возникают при приближенном построении графиков. Второй недостаток геометрического метода заключается в том, что многие величины, имеющие чёткий экономический смысл (например, такие, как остатки ресурсов производства), не выявляются при геометрическом решении задач. Его можно применять только в том случае, когда число переменных в стандартной задаче равно двум. Поэтому необходимы аналитические методы, позволяющие решать ЗЛП с любым числом переменных и выявить экономический смысл, входящих в них величин.
Одним их таких методов является симплексный метод.  
В данном пункте была рассмотрена теорема, из которой следует, что если ЗЛП имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений. Поэтому решение ЗЛП может быть следующим: перебрать конечное число всех угловых точек многогранника решений и выбрать среди них ту, на которой функция цели принимает оптимальное решение. Однако, практическое осуществление такого перебора связано с трудностями, т.к. число решений может быть чрезвычайно велико.
<lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1133" type="#_x0000_t75" o:divferrelative=«f» filled=«t»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><img width=«198» height=«185» src=«dopb73493.zip» v:shapes="_x0000_s1132 _x0000_s1133 _x0000_s1134 _x0000_s1135 _x0000_s1136 _x0000_s1137 _x0000_s1138 _x0000_s1139 _x0000_s1140 _x0000_s1141 _x0000_s1142 _x0000_s1143 _x0000_s1144 _x0000_s1145 _x0000_s1146 _x0000_s1147 _x0000_s1148 _x0000_s1149 _x0000_s1150 _x0000_s1151 _x0000_s1152 _x0000_s1153 _x0000_s1154 _x0000_s1155 _x0000_s1156 _x0000_s1157 _x0000_s1158 _x0000_s1159 _x0000_s1160 _x0000_s1161">Пусть ОДР изображается многоугольником ABCDEGH. Предположим,
что его угловая точка соответствует исходному допустимому решению. При беспорядочном наборе пришлось бы перебирать все 7 угловых точек многогранника. Однако, из чертежа видно, что после вершины А выгодно перейти к соседней вершине В, а затем – к оптимальной точке С. Вместо семи перебрали 3 вершины, последовательно улучшая линейную функцию.
Идея последовательного улучшения решения легла в основу универсального метода решения ЗЛП – симплексного метода. Для использования симплексного метода ЗЛП должна быть приведена к каноническому виду. Для реализации симплексного метода необходимо освоить 3 основных элемента:
·        способ определения какого – либо первоначального допустимого решения
·       правило перехода к лучшему решению
·        критерий проверки оптимальности найденного решения.
Алгоритм конкретной реализации этих элементов рассмотрим на примере.
Практические расчёты при решении реальных задач симплексным методом выполняются в настоящее время с помощью компьютера, однако, если расчёты выполняются без ЭВМ, то удобно использовать симплексные таблицы.
Алгоритм составления симплексных таблиц:
1.     Система ограничений приводится к каноническому виду.
Для нахождения первоначального базисного решения переменные разбиваются на основные и неосновные. Т.к. определитель, составленный из коэффициентов при дополнительных переменных отличен от нуля, то эти переменные можно взять в качестве основных. При выборе основных переменных не обязательно составлять определитель, достаточно воспользоваться следующим правилом: в качестве основных переменных следует выбрать такие, каждая из которых входит только в одно из уравнений системы ограничений, при этом нет таких уравнений системы, в которые не входит ни одна из этих переменных.
2.     Составляют таблицу, где в последней строке указываются коэффициенты функции с противоположным знаком. В левом столбце таблицы записывают основные переменные, в первой строке – все переменные, в последнем столбце свободные члены системы.
3.     Проверяют выполнение критерия оптимальности – наличие в последней  строке отрицательных коэффициентов. Если таких нет, то решение оптимально, достигнут, например, максимум функции (в правом нижнем углу таблицы), основные переменные при этом принимают значение bi, а неосновные переменные равны нулю, т.е. получается оптимальное базисное решение.
4.     Если критерий оптимальности не выполнен, то наибольший по модулю отрицательный коэффициент в последней строке определяет разрешающий столбец S. Составляют оценочные ограничения по следующим правилам:
·        ∞, если bi и аisимеют разные знаки;
·        ∞, если bi=0 и аis<0;
·        ∞, если аis=0;
·         0, если bi=0 и аis>0;
·        <shape id="_x0000_i1089" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image079.wmz» o:><img width=«29» height=«51» src=«dopb73494.zip» v:shapes="_x0000_i1089">, если bi и аisимеют одинаковые знаки.
Определяют min <shape id="_x0000_i1090" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image079.wmz» o:><img width=«29» height=«51» src=«dopb73494.zip» v:shapes="_x0000_i1090">. Если конечного минимума нет, то задача не имеет конечного оптимума. Далее выбирают строку с номером q, на которой он достигается (любую, если их несколько), и называют её разрешающей строкой. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент аqs.
5.     Переходим к следующей таблице по правилам:
а) в левом столбце записывают новый базис: вместо основной переменной хq  — переменную хs, а геометрически произойдёт переход к соседней  вершине многоугольника, где значение линейной функции «лучше». Значение линейной функции увеличится, т.к. переменная, входящая в выражение функции, станет основной, т.е. будет принимать не нулевое, а положительное значение;
b)    новую строку с номером q получают из старой делением на разрешающий элемент аqs;
c)     все остальные элементы вычисляют по правилу многоугольника:
<shape id="_x0000_i1091" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image081.wmz» o:><img width=«117» height=«53» src=«dopb73495.zip» v:shapes="_x0000_i1091">; <shape id="_x0000_i1092" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image083.wmz» o:><img width=«100» height=«53» src=«dopb73496.zip» v:shapes="_x0000_i1092">
Далее переходим к пункту 3 алгоритма.
Замечание: при отыскании минимума функции Z, полагаем, что F=-Z и учитываем, что Zmin=-Fmax.
Решим задачу симплексным методом.
Для производства трёх изделий А, В и С используются три вида ресурсов. Каждый из них используется в объёме, не превышающем 180, 210 и 236 кг. Нормы затрат каждого из видов ресурсов на одно изделие и цена единицы изделий приведены в таблице.
 Определить план выпуска изделий, обеспечивающий получение оптимального дохода.
Решение. х1 — количество выпускаемых изделий А
                 х2 — количество выпускаемых изделий В
                 х3 — количество выпускаемых изделий С.
<img width=«15» height=«74» src=«dopb73497.zip» v:shapes="_x0000_s1162">Тогда целевая функция будет иметь вид: F=10x1+14x2+12 х3 →max
при ограничениях:          4x1+2x2+х3≤180
                                         3x1+x2+3х3≤210
                                         x1+2x2+5х3≤236
Приведём систему к каноническому виду:
<img width=«15» height=«67» src=«dopb73498.zip» v:shapes="_x0000_s1163">4x1+2x2+х3+х4=180
    продолжение
--PAGE_BREAK--                                         3x1+x2+3х3+х5=210
                                       x1+2x2+5х3+х6=236.
Составляем таблицу
Определим ведущий элемент: min<shape id="_x0000_i1093" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image087.wmz» o:><img width=«115» height=«45» src=«dopb73499.zip» v:shapes="_x0000_i1093">. Далее выполняем действия, следуя алгоритму.
min<shape id="_x0000_i1094" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image089.wmz» o:><img width=«131» height=«45» src=«dopb73500.zip» v:shapes="_x0000_i1094">
Ответ: Чтобы получить оптимальный доход, нужно выпускать 83 ед. изделия В, 14 ед. изделия С, а изделие А не выпускать. Оптимальный доход составит 1330 у.е. По решению задачи видим, что у предприятия остаются свободными 85 кг. второго вида ресурсов, 1 и 3 вид полностью расходуются            [5]
3) Двойственная задача.
Каждой задаче линейного программирования соответствует другая задача, называемая двойственной или сопряжённой по отношению к исходной. Теория двойственности полезна для проведения качественных исследований ЗЛП. В главе I пункте 2) рассмотрена <shape id="_x0000_i1095" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image091.wmz» o:><img width=«12» height=«23» src=«dopb73501.zip» v:shapes="_x0000_i1095">задача об использовании ресурсов. Предположим, что некоторая организация решила закупить ресурсы и необходимо установить оптимальные цены на эти ресурсы y1,y2,y3. Очевидно, что
покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z в количествах 180, 210, 236 по ценам соответственно y1,y2,y3были минимальными, т.е. Z= 180y1+210y2+236y3→min. С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не мене той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. На изготовление единицы продукции А расходуется 4кг. ресурса 1, 3кг. ресурса 2, 1кг. ресурса 3 по цене соответственно y1,y2,y3. Поэтому, для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении единицы продукции, должны быть не менее её цены 10у.е., т.е. 4 y1+3 y2+ y3≥10.
Аналогично можно составить ограничения в виде неравенств по каждому виду продукции. Экономико-математическая модель исходной задачи и полученной двойственной задачи приведены в таблице.             
Задача I (исходная)
Задача II (двойственная)
F= 10x1+14x2+12x3→max
 При ограничениях:
<img width=«14» height=«59» src=«dopb73502.zip» v:shapes="_x0000_s1164">      4х1+2х2+х3≤180
      3х1+х2+3х3≤210
      х1+2х2+5х3≤236
и условие неотрицательности переменных x1≥0, x2≥0,  х3≥0.
Для производства трёх изделий А, В, С используются три вида сырья. каждый из них используется в объёме, не превышающем 180, 210 и 236кг. Определить план выпуска изделий, обеспечивающий получение оптимального дохода при условии, что потребление ресурсов по каждому виду продукции не превзойдёт имеющихся запасов.
Z= 180y1+210y2+236y3→min
При ограничениях:
<img width=«14» height=«59» src=«dopb73503.zip» v:shapes="_x0000_s1165">     4y1+3y2+y3≥10
   <img width=«14» height=«86» src=«dopb73504.zip» v:shapes="_x0000_s1166"><img width=«14» height=«86» src=«dopb73504.zip» v:shapes="_x0000_s1167"><img width=«14» height=«86» src=«dopb73504.zip» v:shapes="_x0000_s1168"><img width=«14» height=«86» src=«dopb73504.zip» v:shapes="_x0000_s1169"><img width=«14» height=«86» src=«dopb73504.zip» v:shapes="_x0000_s1170"><img width=«14» height=«86» src=«dopb73504.zip» v:shapes="_x0000_s1171">  2y1+y2+2y3≥14
     y1+3y2+5y3≥12
и условие неотрицательности переменных y1≥0, у2≥0,  у3≥0.
Найти такой набор цен ресурсов, при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли от реализации этой продукции.
 Обе задачи, представленные в таблице обладают следующими свойствами:
1.     В одной задаче ищут максимум линейной функции,  в другой минимум.
2.       Коэффициенты при переменных в линейной функции одной задачи являются свободными членами системы ограничений в другой.
3.     Каждая из задач задана в стандартной форме, причём в задаче максимизации – все неравенства вида «≤», а в задаче минимизации – все неравенства вида «≥».
4.     Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу.
Для задачи I А=<shape id="_x0000_i1096" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image096.wmz» o:><img width=«143» height=«99» src=«dopb73505.zip» v:shapes="_x0000_i1096">, для задачи II А<shape id="_x0000_i1097" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image098.wmz» o:><img width=«7» height=«20» src=«dopb73506.zip» v:shapes="_x0000_i1097">=<shape id="_x0000_i1098" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image100.wmz» o:><img width=«139» height=«99» src=«dopb73507.zip» v:shapes="_x0000_i1098">
5.     Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.
6.     Условия неотрицательности переменных имеются в обеих задачах.
Две задачи I и II  линейного программирования, обладающие указанными свойствами, называются симметричными взаимодвойственными задачами.
Исходя из определения, можно предложить следующий алгоритм составления двойственной задачи.
1.                      Приводят все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задач ищут максимум линейной функции, то все неравенства системы ограничений приводят к виду «≤», а если минимум – к виду «≥».
2.                      Составляют расширенную матрицу системы А1, в которую включают матрицу коэффициентов при переменных, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.
3.                      Находят матрицу А<shape id="_x0000_i1099" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image102.wmz» o:><img width=«16» height=«24» src=«dopb73508.zip» v:shapes="_x0000_i1099">, транспонированную к матрице А1.
4.                      Формулируют двойственную задачу на основании полученной матрицы А<shape id="_x0000_i1100" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image104.wmz» o:><img width=«16» height=«24» src=«dopb73508.zip» v:shapes="_x0000_i1100">и условия неотрицательности переменных.
Связь между оптимальными решениями двойственных задач устанавливается с помощью теорем двойственности. Вначале рассмотрим вспомогательное утверждение.
Основное неравенство теории двойственности. Пусть имеется пара двойственных задач I и II. Покажем, что для любых допустимых решений Х= (x1,x2, …, хn) и У=(y1,y2,…,ym)исходной и двойственной задачи справедливо неравенство F(X) ≤ Z(Y) или <shape id="_x0000_i1101" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image105.wmz» o:><img width=«57» height=«50» src=«dopb73509.zip» v:shapes="_x0000_i1101">≤<shape id="_x0000_i1102" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image107.wmz» o:><img width=«53» height=«49» src=«dopb73510.zip» v:shapes="_x0000_i1102">                                                       (3.6)
□ Возьмём неравенства системы ограничений исходной задачи <shape id="_x0000_i1103" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image109.wmz» o:><img width=«55» height=«47» src=«dopb73511.zip» v:shapes="_x0000_i1103">≤bi и умножим соответственно на переменные y1,y2,…,ym и, сложив правые и левые части полученных неравенств, имеем
<shape id="_x0000_i1104" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image111.wmz» o:><img width=«42» height=«49» src=«dopb73512.zip» v:shapes="_x0000_i1104"><shape id="_x0000_i1105" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image113.wmz» o:><img width=«59» height=«50» src=«dopb73513.zip» v:shapes="_x0000_i1105">≤<shape id="_x0000_i1106" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image107.wmz» o:><img width=«53» height=«49» src=«dopb73510.zip» v:shapes="_x0000_i1106">.                                  (3.7)
Аналогично умножаем систему ограничений двойственной задачи на переменные x1,x2, …, хn, получим       
<shape id="_x0000_i1107" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image115.wmz» o:><img width=«40» height=«51» src=«dopb73514.zip» v:shapes="_x0000_i1107"><shape id="_x0000_i1108" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image117.wmz» o:><img width=«57» height=«49» src=«dopb73515.zip» v:shapes="_x0000_i1108">≥<shape id="_x0000_i1109" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image119.wmz» o:><img width=«57» height=«49» src=«dopb73516.zip» v:shapes="_x0000_i1109">                                      (3.8)
Т.к. левые части неравенств (3.7) и (3.8) представляют одно и тоже выражение  <shape id="_x0000_i1110" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image121.wmz» o:><img width=«31» height=«45» src=«dopb73517.zip» v:shapes="_x0000_i1110"><shape id="_x0000_i1111" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image113.wmz» o:><img width=«59» height=«50» src=«dopb73513.zip» v:shapes="_x0000_i1111">уj, то в силу транзитивности неравенств получим доказываемое неравенство (3.6).■
Теперь докажем признак оптимальности решений.
Достаточный признак оптимальности.
Если X*=(x<shape id="_x0000_i1112" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image123.wmz» o:><img width=«9» height=«24» src=«dopb73518.zip» v:shapes="_x0000_i1112">, x<shape id="_x0000_i1113" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image125.wmz» o:><img width=«11» height=«24» src=«dopb73519.zip» v:shapes="_x0000_i1113">,…, x<shape id="_x0000_i1114" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image127.wmz» o:><img width=«11» height=«25» src=«dopb73520.zip» v:shapes="_x0000_i1114">) и У*=(у<shape id="_x0000_i1115" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image123.wmz» o:><img width=«9» height=«24» src=«dopb73518.zip» v:shapes="_x0000_i1115">, у<shape id="_x0000_i1116" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image125.wmz» o:><img width=«11» height=«24» src=«dopb73519.zip» v:shapes="_x0000_i1116">,…, у<shape id="_x0000_i1117" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image129.wmz» o:><img width=«12» height=«25» src=«dopb73521.zip» v:shapes="_x0000_i1117">) – допустимые решения взаимно двойственных задач, для которых выполняется равенство
F(X*) =Z(Y*)                                                (3.9)
то Х* оптимальное решение исходной задачи I, а У* — двойственной задачи II.
□ Пусть Х1 любое допустимое решение исходной задачи I. Тогда на основании основного неравенства (3.6) получим F(X1) ≤ Z(Y*). Однако Х1 — произвольное решение задачи I. Аналогично доказывается, что решение У* оптимально для задачи II.■
Всегда ли для каждой пары двойственных задач есть одновременно оптимальные решения; возможны ли ситуации, когда одна из двойственных задач имеет решение, а другая нет?
Ответ на эти вопросы даёт следующая теорема.
Первая(основная) теорема двойственности. Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причём оптимальные значения их линейных функций равны:
Fmax=Zmin или F(X*) =Z(Y*)                                (3.10)
Если линейная функция одной из задач не ограничена, то система ограничений другой задачи противоречива.
Из первой части утверждения теоремы следует, что равенство (3.9) является не только достаточным, но и необходимым признаком оптимальности взаимно двойственных задач.
□ Докажем утверждение второй части методом от противного. Предположим, что в исходной задаче линейная функция не ограничена, т.е. Fmax=∞, а условия двойственной задачи не являются противоречивыми, т.е. существует хотя бы одно допустимое решение У=(y1,y2,…,ym). Тогда в силу основного неравенство теории двойственности (3.6)F(X) ≤ Z(Y), что противоречит условию неограниченности F(X). Следовательно, при Fmax=∞ в исходной задаче, допустимых решений в двойственной задаче быть не может. ■
 Экономический смысл первой теоремы двойственности состоит в следующем: план производства X*=(x<shape id="_x0000_i1118" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image131.wmz» o:><img width=«9» height=«24» src=«dopb73518.zip» v:shapes="_x0000_i1118">, x<shape id="_x0000_i1119" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image125.wmz» o:><img width=«11» height=«24» src=«dopb73519.zip» v:shapes="_x0000_i1119">,…, x<shape id="_x0000_i1120" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image127.wmz» o:><img width=«11» height=«25» src=«dopb73520.zip» v:shapes="_x0000_i1120">) и набор цен ресурсов У*=(у<shape id="_x0000_i1121" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image131.wmz» o:><img width=«9» height=«24» src=«dopb73518.zip» v:shapes="_x0000_i1121">, у<shape id="_x0000_i1122" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image125.wmz» o:><img width=«11» height=«24» src=«dopb73519.zip» v:shapes="_x0000_i1122">,…, у<shape id="_x0000_i1123" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image129.wmz» o:><img width=«12» height=«25» src=«dopb73521.zip» v:shapes="_x0000_i1123">) оказываются оптимальными тогда и только тогда, когда прибыль от продукции, найденная при ценах с1, с2,…, сn,«внешних» (известных заранее), равна затратам на ресурсы по «внутренним»(определяемым только из решения задачи) ценамy1,y2,…,ym. Для всех же других планов Х и У обеих задач в соответствии с основным неравенством (3.6) теории двойственности прибыль (выручка) от продукции всегда меньше (или равна) затрат на ресурсы.
Экономический смысл первой теоремы двойственности можно интерпретировать и так: предприятию безразлично, производить ли продукцию по оптимальному плану X*=(x<shape id="_x0000_i1124" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image131.wmz» o:><img width=«9» height=«24» src=«dopb73518.zip» v:shapes="_x0000_i1124">, x<shape id="_x0000_i1125" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image125.wmz» o:><img width=«11» height=«24» src=«dopb73519.zip» v:shapes="_x0000_i1125">,…, x<shape id="_x0000_i1126" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image127.wmz» o:><img width=«11» height=«25» src=«dopb73520.zip» v:shapes="_x0000_i1126">) и получать максимальную прибыль Fmax либо продавать ресурсы по оптимальным ценам У*=(у<shape id="_x0000_i1127" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image131.wmz» o:><img width=«9» height=«24» src=«dopb73518.zip» v:shapes="_x0000_i1127">, у<shape id="_x0000_i1128" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image125.wmz» o:><img width=«11» height=«24» src=«dopb73519.zip» v:shapes="_x0000_i1128">,…, у<shape id="_x0000_i1129" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image129.wmz» o:><img width=«12» height=«25» src=«dopb73521.zip» v:shapes="_x0000_i1129">) и возместить от продажи равные ей минимальные затраты на ресурсы Zmin.
Связь между двумя взаимно двойственными задачами проявляется не только в равенстве оптимальных значений их линейных функций.
Пусть даны две взаимно двойственные задачи I и II. Если каждую из них решать симплексным методом, то необходимо привести их к каноническому виду, для чего в систему ограничений задачи I следует ввести m неотрицательных переменных xn+1, xn+2, …, xn+m, а в систему ограничений задачи II  — n неотрицательных переменных ym+1, ym+2,…,ym+n. Системы ограничений двойственных задач примут вид:  
<shape id="_x0000_i1130" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image132.wmz» o:><img width=«55» height=«47» src=«dopb73522.zip» v:shapes="_x0000_i1130">+xn+i=bi, i=1,…,m (3.11)                      <shape id="_x0000_i1131" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image134.wmz» o:><img width=«53» height=«45» src=«dopb73523.zip» v:shapes="_x0000_i1131">-ym+j=cj, j=1,…,n (3.12).
установим соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи.
Переменные исходной задачи I
Первоначальные
Дополнительные
x1                 x2           …         xj           …         хn
↕                    ↕                                   ↕                                ↕
ym+1     ym+2         …        ym+j     …      ym+n
xn+1         xn+2        …       xn+I       …         xn+m
  ↕                        ↕                               ↕                         ↕
 y1                     y2         …         yj                      ym
Дополнительные
Первоначальные
Переменные исходной задачи II
Теорема. Положительным (ненулевым) компонентам оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых i=1,2,…,m и j=1,2,…,n: если <shape id="_x0000_i1132" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image136.wmz» o:><img width=«19» height=«27» src=«dopb73524.zip» v:shapes="_x0000_i1132">>0, то <shape id="_x0000_i1133" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image138.wmz» o:><img width=«32» height=«27» src=«dopb73525.zip» v:shapes="_x0000_i1133">=0; если <shape id="_x0000_i1134" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image140.wmz» o:><img width=«28» height=«25» src=«dopb73526.zip» v:shapes="_x0000_i1134">>0, то<shape id="_x0000_i1135" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image142.wmz» o:><img width=«19» height=«25» src=«dopb73527.zip» v:shapes="_x0000_i1135">=0, и аналогично, если <shape id="_x0000_i1136" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image144.wmz» o:><img width=«19» height=«25» src=«dopb73527.zip» v:shapes="_x0000_i1136">>0, то <shape id="_x0000_i1137" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image145.wmz» o:><img width=«28» height=«25» src=«dopb73526.zip» v:shapes="_x0000_i1137">=0; если <shape id="_x0000_i1138" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image146.wmz» o:><img width=«32» height=«27» src=«dopb73525.zip» v:shapes="_x0000_i1138">>0, то<shape id="_x0000_i1139" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image147.wmz» o:><img width=«19» height=«27» src=«dopb73524.zip» v:shapes="_x0000_i1139">=0.
□ Выразим дополнительные переменные из системы ограничений (3.11) исходной задачи I и (3.12) двойственной задачи, представленных в каноническом виде:
xn+i=bi-<shape id="_x0000_i1140" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image132.wmz» o:><img width=«59» height=«50» src=«dopb73528.zip» v:shapes="_x0000_i1140">, i=1,2,…,m                                  (3.13)
ym+j=<shape id="_x0000_i1141" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image134.wmz» o:><img width=«57» height=«49» src=«dopb73515.zip» v:shapes="_x0000_i1141">-cj, j=1,…,n.                                (3.14)
Умножая каждое равенство системы (4.9) на соответствующие переменные уj≥0 и складывая полученные равенства, найдём
<shape id="_x0000_i1142" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image149.wmz» o:><img width=«18» height=«45» src=«dopb73529.zip» v:shapes="_x0000_i1142">xn+iyi=<shape id="_x0000_i1143" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image151.wmz» o:><img width=«17» height=«45» src=«dopb73530.zip» v:shapes="_x0000_i1143">biyi-<shape id="_x0000_i1144" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image153.wmz» o:><img width=«17» height=«45» src=«dopb73530.zip» v:shapes="_x0000_i1144"><shape id="_x0000_i1145" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image154.wmz» o:><img width=«55» height=«47» src=«dopb73531.zip» v:shapes="_x0000_i1145">yi                            (3.15)
Аналогично, умножая каждое неравенство системы (4.10) на соответствующие переменные xj≥0 и складывая полученные равенства, найдём
<shape id="_x0000_i1146" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image156.wmz» o:><img width=«40» height=«47» src=«dopb73532.zip» v:shapes="_x0000_i1146">ym+j=<shape id="_x0000_i1147" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image158.wmz» o:><img width=«18» height=«45» src=«dopb73533.zip» v:shapes="_x0000_i1147"><shape id="_x0000_i1148" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image154.wmz» o:><img width=«55» height=«47» src=«dopb73531.zip» v:shapes="_x0000_i1148">yi-<shape id="_x0000_i1149" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image156.wmz» o:><img width=«40» height=«47» src=«dopb73532.zip» v:shapes="_x0000_i1149">cj.                                          (3.16)
Равенства (4.11)и(4.12) будут справедливы для любых допустимых значений переменных, в том числе и для оптимальных значений <shape id="_x0000_i1150" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image160.wmz» o:><img width=«22» height=«31» src=«dopb73534.zip» v:shapes="_x0000_i1150">,<shape id="_x0000_i1151" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image140.wmz» o:><img width=«32» height=«29» src=«dopb73535.zip» v:shapes="_x0000_i1151">,<shape id="_x0000_i1152" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image163.wmz» o:><img width=«22» height=«29» src=«dopb73536.zip» v:shapes="_x0000_i1152">, <shape id="_x0000_i1153" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image138.wmz» o:><img width=«36» height=«30» src=«dopb73537.zip» v:shapes="_x0000_i1153">. В силу первой теоремы двойственности (3.10)F(X*) =Z(Y*) или <shape id="_x0000_i1154" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image166.wmz» o:><img width=«70» height=«51» src=«dopb73538.zip» v:shapes="_x0000_i1154">=<shape id="_x0000_i1155" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image168.wmz» o:><img width=«56» height=«49» src=«dopb73539.zip» v:shapes="_x0000_i1155">, поэтому из записи правых частей равенств (3.15) и (3.16) следует, что они должны отличаться только знаком. С другой стороны, из неотрицательности выражений <shape id="_x0000_i1156" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image149.wmz» o:><img width=«18» height=«45» src=«dopb73529.zip» v:shapes="_x0000_i1156">xn+iyiи <shape id="_x0000_i1157" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image156.wmz» o:><img width=«40» height=«47» src=«dopb73532.zip» v:shapes="_x0000_i1157">ym+j, входящие в выражения (3.15) и (3.16), следует, что правые части этих равенств должны быть неотрицательны.
Эти условия могут выполняться одновременно только при равенстве этих правых частей для оптимального значения переменных нулю:
<img width=«14» height=«77» src=«dopb73540.zip» v:shapes="_x0000_s1172"><shape id="_x0000_i1158" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image149.wmz» o:><img width=«19» height=«45» src=«dopb73541.zip» v:shapes="_x0000_i1158"><shape id="_x0000_i1159" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image140.wmz» o:><img width=«32» height=«29» src=«dopb73535.zip» v:shapes="_x0000_i1159"><shape id="_x0000_i1160" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image163.wmz» o:><img width=«22» height=«29» src=«dopb73536.zip» v:shapes="_x0000_i1160">=0,
<shape id="_x0000_i1161" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image172.wmz» o:><img width=«25» height=«47» src=«dopb73542.zip» v:shapes="_x0000_i1161"><shape id="_x0000_i1162" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image160.wmz» o:><img width=«21» height=«31» src=«dopb73543.zip» v:shapes="_x0000_i1162"><shape id="_x0000_i1163" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image138.wmz» o:><img width=«36» height=«30» src=«dopb73537.zip» v:shapes="_x0000_i1163">=0.                                          (3.17)
В силу условия неотрицательности переменных каждое из слагаемых в равенстве (4.13) должно равняться нулю:
<img width=«14» height=«59» src=«dopb73544.zip» v:shapes="_x0000_s1173"><shape id="_x0000_i1164" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image140.wmz» o:><img width=«32» height=«29» src=«dopb73535.zip» v:shapes="_x0000_i1164"><shape id="_x0000_i1165" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image163.wmz» o:><img width=«22» height=«29» src=«dopb73536.zip» v:shapes="_x0000_i1165">=0,  i=1,2,…,m
<shape id="_x0000_i1166" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image160.wmz» o:><img width=«21» height=«31» src=«dopb73543.zip» v:shapes="_x0000_i1166"><shape id="_x0000_i1167" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image138.wmz» o:><img width=«36» height=«30» src=«dopb73537.zip» v:shapes="_x0000_i1167">=0, j=1,2,…,n
Откуда и вытекает заключение теоремы. ■
Из доказанной теоремы следует, что введённое ранее соответствие между переменными двойственных задач представляет соответствие между основными (как правило не равными нулю) переменными одной из двойственных задач и неосновными (равными нулю) переменными другой задачи, когда они образуют допустимые базисные решения.
Рассмотренная теорема является следствием следующей теоремы.
Вторая теорема двойственности. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной функции исходной задачи, выраженной через неосновные переменные её оптимального решения.
Метод, при котором вначале симплексным методом решается двойственная задача, а затем оптимум и оптимальное решение исходной задачи находятся с помощью теорем двойственности, называется двойственным симплексным методом. Этот метод бывает выгодно применять, когда первое базисное решение исходной задачи недопустимое или, например, когда число её ограничений m больше числа переменных n.
С помощью теорем двойственности найдём решение задачи II. Получаем следующий набор цен ресурсов (<shape id="_x0000_i1168" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image176.wmz» o:><img width=«28» height=«41» src=«dopb73545.zip» v:shapes="_x0000_i1168"> <shape id="_x0000_i1169" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image178.wmz» o:><img width=«16» height=«21» src=«dopb73546.zip» v:shapes="_x0000_i1169"> <shape id="_x0000_i1170" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image180.wmz» o:><img width=«16» height=«41» src=«dopb73547.zip» v:shapes="_x0000_i1170">),  при котором минимальные затраты составят 1330.                                                                                                 [5]
4) Задача нелинейного программирования. (ЗНП)
Рассмотрим ЗНП и способы её решения. Математическая модель ЗНП в общем виде формулируется следующим образом:
f =(x1,x2, …,хn)→ min (max). При этом переменные должны удовлетворять ограничениям:<shape id="_x0000_i1171" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image091.wmz» o:><img width=«12» height=«23» src=«dopb73501.zip» v:shapes="_x0000_i1171">
<img width=«26» height=«191» src=«dopb73548.zip» v:shapes="_x0000_s1174">g1(x1,x2, …, хn)≤b1,
…………………………
gm(x1,x2, …, хn)≤bm,
gm+1(x1,x2, …, хn)≥bm+1,
…………………………                                                                                  
gk(x1,x2, …, хn)≥bk,
gk+1(x1,x2, …, хn)=bk+1,
………………………
gp(x1,x2, …, хn)=bp.
x1,x2,…, хn≥0,  где хотя бы одна из функций f, gi нелинейная.
Для ЗЛП нет единого метода решения. В зависимости от вида целевой функции и системы ограничений разработаны специальные методы решения, к которым относятся метод множителей Лагранжа, градиентные методы, приближённые методы решения, графический метод.
Рассмотрим основные идеи графического метода.
Максимум и минимум достигается в точках касания линии уровня с областью допустимых решений (ОДР), которая  задается системой ограничений. Например, если линии уровня — прямые, то точки касания можно определить, используя геометрический смысл производной.
    продолжение
--PAGE_BREAK--Рассмотрим на примерах решение ЗНП.
1. Найти экстремумы функции L(x1,x2)=x1+2x2при ограничениях
<shape id="_x0000_i1172" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image183.wmz» o:><img width=«99» height=«28» src=«dopb73549.zip» v:shapes="_x0000_i1172">, <shape id="_x0000_i1173" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image185.wmz» o:><img width=«75» height=«27» src=«dopb73550.zip» v:shapes="_x0000_i1173">.
<lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1176" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><shapetype id="_x0000_t19" coordsize=«21600,21600» o:spt=«19» adj="-5898240,,,21600,21600" path=«wr-21600,,21600,43200,,,21600,21600nfewr-21600,,21600,43200,,,21600,21600l,21600nsxe» filled=«f»><path arrowok=«t» o:extrusionok=«f» gradientshapeok=«t» o:connecttype=«custom» o:connectlocs=«0,0;21600,21600;0,21600»><img width=«170» height=«159» src=«dopb73551.zip» v:shapes="_x0000_s1175 _x0000_s1176 _x0000_s1177 _x0000_s1178 _x0000_s1179 _x0000_s1180 _x0000_s1181 _x0000_s1182 _x0000_s1183 _x0000_s1184 _x0000_s1185 _x0000_s1186 _x0000_s1187">  Решение. ОДР – это часть круга с радиусом 5, расположенная в I четверти. Найдём линии уровня функции L: x1+2x2=C. Выразим x2=<shape id="_x0000_i1174" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image188.wmz» o:><img width=«51» height=«43» src=«dopb73552.zip» v:shapes="_x0000_i1174">. Линиями уровня будут параллельные прямые с угловым коэффициентом, равным -<shape id="_x0000_i1175" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image190.wmz» o:><img width=«16» height=«41» src=«dopb73486.zip» v:shapes="_x0000_i1175">. Минимум функции достигается в точке (0;0), Lmin=0, т.к. градиент <shape id="_x0000_i1176" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image191.wmz» o:><img width=«15» height=«25» src=«dopb73553.zip» v:shapes="_x0000_i1176">(1,2) направлен вверх вправо. Максимум достигается в точке касания  кривой х2=<shape id="_x0000_i1177" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image193.wmz» o:><img width=«64» height=«29» src=«dopb73554.zip» v:shapes="_x0000_i1177"> и линии уровня. Т.к. угловой коэффициент касательной к графику функции равен -<shape id="_x0000_i1178" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image190.wmz» o:><img width=«16» height=«41» src=«dopb73486.zip» v:shapes="_x0000_i1178">, найдём координаты точки касания, используя геометрический смысл производной.
<shape id="_x0000_i1179" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image195.wmz» o:><img width=«54» height=«29» src=«dopb73555.zip» v:shapes="_x0000_i1179">=-<shape id="_x0000_i1180" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image190.wmz» o:><img width=«16» height=«41» src=«dopb73486.zip» v:shapes="_x0000_i1180">; (<shape id="_x0000_i1181" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image193.wmz» o:><img width=«64» height=«29» src=«dopb73554.zip» v:shapes="_x0000_i1181">)<shape id="_x0000_i1182" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image197.wmz» o:><img width=«7» height=«20» src=«dopb73506.zip» v:shapes="_x0000_i1182">=-<shape id="_x0000_i1183" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image190.wmz» o:><img width=«16» height=«41» src=«dopb73486.zip» v:shapes="_x0000_i1183">;
<shape id="_x0000_i1184" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image198.wmz» o:><img width=«75» height=«52» src=«dopb73556.zip» v:shapes="_x0000_i1184">=-<shape id="_x0000_i1185" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image190.wmz» o:><img width=«16» height=«41» src=«dopb73486.zip» v:shapes="_x0000_i1185">; <shape id="_x0000_i1186" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image200.wmz» o:><img width=«20» height=«16» src=«dopb73557.zip» v:shapes="_x0000_i1186">x=<shape id="_x0000_i1187" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image202.wmz» o:><img width=«24» height=«24» src=«dopb73558.zip» v:shapes="_x0000_i1187">; x2=2<shape id="_x0000_i1188" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image202.wmz» o:><img width=«24» height=«24» src=«dopb73558.zip» v:shapes="_x0000_i1188">.
Тогда L=<shape id="_x0000_i1189" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image202.wmz» o:><img width=«24» height=«24» src=«dopb73558.zip» v:shapes="_x0000_i1189">+2∙2<shape id="_x0000_i1190" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image202.wmz» o:><img width=«24» height=«24» src=«dopb73558.zip» v:shapes="_x0000_i1190">=5<shape id="_x0000_i1191" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image202.wmz» o:><img width=«24» height=«24» src=«dopb73558.zip» v:shapes="_x0000_i1191">.
Ответ: Минимум достигается в точке О(0;0), глобальный максимум, равный 5<shape id="_x0000_i1192" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image202.wmz» o:><img width=«24» height=«24» src=«dopb73558.zip» v:shapes="_x0000_i1192">, в точке А(<shape id="_x0000_i1193" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image202.wmz» o:><img width=«24» height=«24» src=«dopb73558.zip» v:shapes="_x0000_i1193">;2<shape id="_x0000_i1194" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image202.wmz» o:><img width=«24» height=«24» src=«dopb73558.zip» v:shapes="_x0000_i1194">).
2. Найти экстремумы функции L=(x1-6)2+(x2-2)2 при ограничениях    
                   
<img width=«18» height=«90» src=«dopb73559.zip» v:shapes="_x0000_s1189">                    x1+x2≤8
                    3 x1+x2 ≤15
                    x1+x2 ≥1  
                   <shape id="_x0000_i1195" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image185.wmz» o:><img width=«64» height=«23» src=«dopb73560.zip» v:shapes="_x0000_i1195">.
<lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1191" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><path o:connectlocs=«17312,0;18568,23954;0,12918»><img width=«195» height=«232» src=«dopb73561.zip» v:shapes="_x0000_s1190 _x0000_s1191 _x0000_s1192 _x0000_s1193 _x0000_s1194 _x0000_s1195 _x0000_s1196 _x0000_s1197 _x0000_s1198 _x0000_s1199 _x0000_s1200 _x0000_s1201 _x0000_s1202 _x0000_s1203 _x0000_s1204 _x0000_s1205 _x0000_s1206 _x0000_s1207 _x0000_s1208 _x0000_s1209 _x0000_s1210 _x0000_s1211 _x0000_s1212 _x0000_s1213 _x0000_s1214 _x0000_s1215 _x0000_s1216 _x0000_s1217 _x0000_s1218 _x0000_s1219">Решение.  ОДР – многоугольник ABCDE. Линии уровня представляют собой окружности (x1-6)2+(x2-2)2=С с центром в точке О1(6;2). Возьмём, например, С=36, видим, что максимум достигается в точке А(0;4), которая лежит на окружности наибольшего радиуса, пересекающую  ОДР. L(A)=(0-6)2+(4-2)2=40. Минимум  — в точке F, находящейся на пересечении прямой 3x1+x2 =15 и перпендикуляра к этой прямой, проведённого из точки О1. Т.к. угловой коэффициент равен -3, то угловой коэффициент перпендикуляра равен <shape id="_x0000_i1196" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image207.wmz» o:><img width=«15» height=«41» src=«dopb73562.zip» v:shapes="_x0000_i1196">. Из уравнения прямой, проходящей через данную точку О1 с угловым коэффициентом <shape id="_x0000_i1197" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image207.wmz» o:><img width=«15» height=«41» src=«dopb73562.zip» v:shapes="_x0000_i1197">, получим (x2-2)= <shape id="_x0000_i1198" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image207.wmz» o:><img width=«15» height=«41» src=«dopb73562.zip» v:shapes="_x0000_i1198">(x1-6). Найдём координаты точки Е
<img width=«14» height=«50» src=«dopb73563.zip» v:shapes="_x0000_s1220">х1-3х2=0
3 x1+x2 =15.
Решив систему, получаем Е(4.5; 1.5).
L(E) = (4.5-6)2+ (1.5-2)2=2.5.
Ответ: Минимум, равный 2.5 достигается в точке (4.5; 1.5), максимум, равный 40, в точке (0;4).
3. Найти экстремумы функции L=(x1-1)2+(x2-3)2
   при ограничениях <shape id="_x0000_i1199" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image210.wmz» o:><img width=«84» height=«24» src=«dopb73564.zip» v:shapes="_x0000_i1199">, <shape id="_x0000_i1200" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image185.wmz» o:><img width=«64» height=«23» src=«dopb73560.zip» v:shapes="_x0000_i1200">.
<lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1222" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><img width=«173» height=«149» src=«dopb73565.zip» v:shapes="_x0000_s1221 _x0000_s1222 _x0000_s1223 _x0000_s1224 _x0000_s1225 _x0000_s1226 _x0000_s1227 _x0000_s1228 _x0000_s1229 _x0000_s1230 _x0000_s1231">Решение: ОДР является часть круга, с центром в начале координат,  с радиусом 5, расположенная в I четверти. Линии уровня – это окружности с центром в точке О1 и радиуса С, т.к. (x1-1)2+(x2-3)2=С. Точка О1 – это вырожденная линия уровня, соответствующая минимальному значению С=0. глобальный максимум достигается в точке А, лежащей на пересечении ОДР с линией уровня наибольшего радиуса. При этом
L(A)=(5-1)2+(0-3)2=25.
Ответ: Минимум, равный, достигается в точке (1;3),
              Максимум, равный 25, — в точке А(5;0).
4. Предприниматель решил выделить на расширение своего дела 150 тыс.руб. известно, что если на приобретение нового оборудования затратить х тыс. руб., а на зарплату вновь принятых работников у тыс. руб., то прирост объёма продукции составит Q=0.001x0.6·y0.4. Как следует распределить выделенные денежные ресурсы, чтобы прирост объёма продукции был максимальным.
 <img width=«18» height=«50» src=«dopb73566.zip» v:shapes="_x0000_s1232"> Решение: Целевая функция имеет вид 0.001x0.6·y0.4→max при ограничениях   x+y≤150,
   <shape id="_x0000_i1201" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image185.wmz» o:><img width=«64» height=«23» src=«dopb73560.zip» v:shapes="_x0000_i1201">.
ОДР – треугольник. <lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1234" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><shapetype id="_x0000_t6" coordsize=«21600,21600» o:spt=«6» path=«m,l,21600r21600,xe»><path gradientshapeok=«t» o:connecttype=«custom» o:connectlocs=«0,0;0,10800;0,21600;10800,21600;21600,21600;10800,10800» textboxrect=«1800,12600,12600,19800»><img width=«219» height=«205» src=«dopb73567.zip» v:shapes="_x0000_s1233 _x0000_s1234 _x0000_s1235 _x0000_s1236 _x0000_s1237 _x0000_s1238 _x0000_s1239 _x0000_s1240 _x0000_s1241 _x0000_s1242">Линии уровня будут иметь вид 0.001x0.6·y0.4=С. Выразив отсюда у, получим у=<shape id="_x0000_i1202" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image215.wmz» o:><img width=«100» height=«52» src=«dopb73568.zip» v:shapes="_x0000_i1202">. Т.к. максимум достигается в точке касания линии уровня с ОДР, то  условие касания имеет вид <shape id="_x0000_i1203" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image217.wmz» o:><img width=«125» height=«66» src=«dopb73569.zip» v:shapes="_x0000_i1203">=-1. Найдя производную, получаем <shape id="_x0000_i1204" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image219.wmz» o:><img width=«137» height=«47» src=«dopb73570.zip» v:shapes="_x0000_i1204">=-1. Выразив х, получим х=<shape id="_x0000_i1205" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image221.wmz» o:><img width=«100» height=«47» src=«dopb73571.zip» v:shapes="_x0000_i1205">. у=<shape id="_x0000_i1206" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image223.wmz» o:><img width=«164» height=«69» src=«dopb73572.zip» v:shapes="_x0000_i1206">=<shape id="_x0000_i1207" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image225.wmz» o:><img width=«100» height=«44» src=«dopb73573.zip» v:shapes="_x0000_i1207">.
Ответ: Факторы х и у следует распределить в отношении 2:3.
5.Предприятие выпускает изделия А и Б, при изготовлении которых используется сырьё S1и S2. Известны запасы bi(i=1,2) сырья, нормы его расхода на единицу изделия aij(j=1,2), оптовые цены pjна изделия и их плановая себестоимость с<shape id="_x0000_i1208" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image227.wmz» o:><img width=«11» height=«27» src=«dopb73574.zip» v:shapes="_x0000_i1208">. Как только объём выпускаемой продукции перестаёт соответствовать оптимальному размеру предприятия, дальнейшее увеличение выпуска хjведёт к повышению себестоимости продукции b, в первом приближении фактическая себестоимость сjописывается функцией сj= с<shape id="_x0000_i1209" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image227.wmz» o:><img width=«11» height=«27» src=«dopb73574.zip» v:shapes="_x0000_i1209">+ с<shape id="_x0000_i1210" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image229.wmz» o:><img width=«11» height=«27» src=«dopb73575.zip» v:shapes="_x0000_i1210">хj, где сj– некоторая постоянная. Все числовые данные приведены в таблице
Найти план выпуска изделий, обеспечивающий предприятию наивысшую прибыль в условиях нарушения баланса между объёмом и оптимальным размером предприятия.
Решение: Составим математическую модель задачи.
Пусть Z – прибыль, получаемая предприятием после реализации х1 выпущенных изделий А и х2 изделий Б.
Z=( 12-( 7+ 0,2 х1)) х1+( 10-( 8+ 0,2 х2)) х2 →max,
<img width=«14» height=«40» src=«dopb73578.zip» v:shapes="_x0000_s1243">при ограничениях    13 х1+ 6 х2≤ 90,
                                  8 х1+ 11 х2≤88,
                               <shape id="_x0000_i1215" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image185.wmz» o:><img width=«64» height=«23» src=«dopb73560.zip» v:shapes="_x0000_i1215">
Преобразуя целевую функцию, получим:
Z=5х1-0,2х<shape id="_x0000_i1216" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image236.wmz» o:><img width=«11» height=«24» src=«dopb73475.zip» v:shapes="_x0000_i1216">+2 х2-0,2х<shape id="_x0000_i1217" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image049.wmz» o:><img width=«11» height=«24» src=«dopb73476.zip» v:shapes="_x0000_i1217">→max
    ОДР – многоугольник ОАВD. Для построения линий уровня функции, приведём функцию к следующему виду:
(х1-12,5)2+(х2-5)2=181,25-5Z.
Линиями уровня будут окружности с центром в точке О1(12,5; 5) и радиуса <shape id="_x0000_i1218" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image237.wmz» o:><img width=«92» height=«27» src=«dopb73579.zip» v:shapes="_x0000_i1218">. Окружность наибольшего радиуса будет проходить через точку М, находящейся на пересечении прямой ВD и прямой O1М, перпендикулярной к BD. Найдём координаты точки М.
<img width=«14» height=«50» src=«dopb73580.zip» v:shapes="_x0000_s1244">      13х1+ 6х2=90
      х2-5=6/13(х1-12,5). Решив систему, получим, М(6;2).
Z(М)=30-7,2-2,8+4=26.
Ответ: Для получения предприятием максимальной прибыли, составляющей 26 ден.ед., следует выпустить 6 ед. изделия А и 2 ед. изделия Б. 
5)Задача на условный экстремум.
Если система ограничений (3.1) задана в виде равенств, то это задача на условный экстремум. В случае функцииn независимых переменных (x1,x2, …, хn) задача на условный экстремум формулируется следующим образом:
L=f(x1,x2, …,хn)→max (min)
при условиях: gi(x1,x2, …, хn)=0, i=<shape id="_x0000_i1219" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image240.wmz» o:><img width=«28» height=«25» src=«dopb73581.zip» v:shapes="_x0000_i1219">. (m<n).
В конце XVIII века Лагранж предложил остроумный метод решения задачи на условный экстремум. Суть метода Лагранжа состоит в построении функции L(x1,x2, …, хn)= f(x1,x2, …, хn)+<shape id="_x0000_i1220" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image242.wmz» o:><img width=«39» height=«45» src=«dopb73582.zip» v:shapes="_x0000_i1220">gi(x1,x2, …, хn), где λiнеизвестные постоянные, и нахождении экстремума функции L.
Верна следующая теорема: если точка (<shape id="_x0000_i1221" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image244.wmz» o:><img width=«83» height=«25» src=«dopb73583.zip» v:shapes="_x0000_i1221">) является точкой условного экстремума функции f(x1,x2, …, хn) при условии g(x1,x2, …, хn)=0, то существует значение λi такие, что точка (<shape id="_x0000_i1222" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image246.wmz» o:><img width=«124» height=«25» src=«dopb73584.zip» v:shapes="_x0000_i1222">) является точкой экстремума функции L(<shape id="_x0000_i1223" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image248.wmz» o:><img width=«121» height=«25» src=«dopb73585.zip» v:shapes="_x0000_i1223">).
Рассмотрим метод Лагранжа для функции двух переменных.
L(x1,x2,λ)= f(x1,x2)+λg(x1,x2)
Таким образом, для нахождения условного экстремума функции f(x1,x2) при условии g(x1,x2)=0 требуется найти решение системы
                                     <img width=«18» height=«76» src=«dopb73586.zip» v:shapes="_x0000_s1245">L<shape id="_x0000_i1224" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image251.wmz» o:><img width=«13» height=«27» src=«dopb73587.zip» v:shapes="_x0000_i1224">=f <shape id="_x0000_i1225" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image251.wmz» o:><img width=«13» height=«27» src=«dopb73587.zip» v:shapes="_x0000_i1225">(x1,x2)+λg<shape id="_x0000_i1226" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image253.wmz» o:><img width=«13» height=«27» src=«dopb73587.zip» v:shapes="_x0000_i1226">(x1,x2)=0,                           (3.18)
     L<shape id="_x0000_i1227" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image254.wmz» o:><img width=«15» height=«27» src=«dopb73588.zip» v:shapes="_x0000_i1227">=f <shape id="_x0000_i1228" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image254.wmz» o:><img width=«15» height=«27» src=«dopb73588.zip» v:shapes="_x0000_i1228">(x1, x2) +λg<shape id="_x0000_i1229" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image256.wmz» o:><img width=«14» height=«27» src=«dopb73589.zip» v:shapes="_x0000_i1229">(x1, x2) =0,
                                    L<shape id="_x0000_i1230" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image258.wmz» o:><img width=«11» height=«25» src=«dopb73590.zip» v:shapes="_x0000_i1230">= g(x1, x2) =0.                                                  [4]
Есть и достаточные условия, при выполнении которых решение (x1,x2,λ) системы (3.18) определяет точку, в которой функция f достигает экстремума, для этого нужно вычислить значения <shape id="_x0000_i1231" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image260.wmz» o:><img width=«157» height=«27» src=«dopb73591.zip» v:shapes="_x0000_i1231">и составить определитель
<shape id="_x0000_i1232" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image262.wmz» o:><img width=«15» height=«17» src=«dopb73461.zip» v:shapes="_x0000_i1232">=-<shape id="_x0000_i1233" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image263.wmz» o:><img width=«119» height=«77» src=«dopb73592.zip» v:shapes="_x0000_i1233">.
Если <shape id="_x0000_i1234" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image262.wmz» o:><img width=«15» height=«17» src=«dopb73461.zip» v:shapes="_x0000_i1234"><0, то функция имеет в точке (<shape id="_x0000_i1235" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image265.wmz» o:><img width=«63» height=«24» src=«dopb73593.zip» v:shapes="_x0000_i1235">) условный максимум, если <shape id="_x0000_i1236" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image262.wmz» o:><img width=«15» height=«17» src=«dopb73461.zip» v:shapes="_x0000_i1236">>0 – то условный минимум.
Решим задачу методом множителей Лагранжа.
Общие издержки производства заданы функцией Т=0,5х2+0,6ху+0,4у2++700х+600у+2000, где х и у соответственно количество товаров А и В. Общее количество произведённой продукции должно быть равно 500 единиц. Сколько единиц товара А и В нужно производить, чтобы издержки на их изготовление были минимальными?
Решение: составим функцию Лагранжа.
L(x, y, λ) =0,5х2+0,6ху+0,4у2++700х+600у+2000+λ(х+у-500). Приравнивая к нулю её частные производные, получим      
<img width=«14» height=«74» src=«dopb73594.zip» v:shapes="_x0000_s1246">х+0,6у+700+ λ=0,
 0,6х+0,8у+600+ λ=0,
                                            х+у-500=0.
Решив систему, найдём (0, 500, -1000).
Воспользуемся достаточным условием для определения найденного значения L<shape id="_x0000_i1237" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image268.wmz» o:><img width=«15» height=«25» src=«dopb73595.zip» v:shapes="_x0000_i1237">(x,y)=1, L<shape id="_x0000_i1238" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image270.wmz» o:><img width=«15» height=«27» src=«dopb73596.zip» v:shapes="_x0000_i1238">(x,y)=0.8, L<shape id="_x0000_i1239" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image272.wmz» o:><img width=«15» height=«26» src=«dopb73597.zip» v:shapes="_x0000_i1239">(x,y)=0.6. Функция g= х+у-500. g<shape id="_x0000_i1240" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image274.wmz» o:><img width=«11» height=«25» src=«dopb73598.zip» v:shapes="_x0000_i1240">=1, g<shape id="_x0000_i1241" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image276.wmz» o:><img width=«11» height=«27» src=«dopb73599.zip» v:shapes="_x0000_i1241">=1.
<shape id="_x0000_i1242" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image262.wmz» o:><img width=«15» height=«17» src=«dopb73461.zip» v:shapes="_x0000_i1242">=-(0·L<shape id="_x0000_i1243" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image268.wmz» o:><img width=«15» height=«25» src=«dopb73595.zip» v:shapes="_x0000_i1243">·L<shape id="_x0000_i1244" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image270.wmz» o:><img width=«15» height=«27» src=«dopb73596.zip» v:shapes="_x0000_i1244">+ g<shape id="_x0000_i1245" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image274.wmz» o:><img width=«11» height=«25» src=«dopb73598.zip» v:shapes="_x0000_i1245">·L<shape id="_x0000_i1246" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image272.wmz» o:><img width=«15» height=«26» src=«dopb73597.zip» v:shapes="_x0000_i1246">· g<shape id="_x0000_i1247" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image276.wmz» o:><img width=«11» height=«27» src=«dopb73599.zip» v:shapes="_x0000_i1247">+ g<shape id="_x0000_i1248" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image276.wmz» o:><img width=«11» height=«27» src=«dopb73599.zip» v:shapes="_x0000_i1248">·g<shape id="_x0000_i1249" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image274.wmz» o:><img width=«11» height=«25» src=«dopb73598.zip» v:shapes="_x0000_i1249">·L<shape id="_x0000_i1250" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image272.wmz» o:><img width=«15» height=«26» src=«dopb73597.zip» v:shapes="_x0000_i1250">— g<shape id="_x0000_i1251" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image274.wmz» o:><img width=«11» height=«25» src=«dopb73598.zip» v:shapes="_x0000_i1251">·L<shape id="_x0000_i1252" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image268.wmz» o:><img width=«15» height=«25» src=«dopb73595.zip» v:shapes="_x0000_i1252">·g<shape id="_x0000_i1253" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image276.wmz» o:><img width=«11» height=«27» src=«dopb73599.zip» v:shapes="_x0000_i1253">-0·L<shape id="_x0000_i1254" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image268.wmz» o:><img width=«15» height=«25» src=«dopb73595.zip» v:shapes="_x0000_i1254">·L<shape id="_x0000_i1255" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image272.wmz» o:><img width=«15» height=«26» src=«dopb73597.zip» v:shapes="_x0000_i1255">— g<shape id="_x0000_i1256" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image274.wmz» o:><img width=«11» height=«25» src=«dopb73598.zip» v:shapes="_x0000_i1256">· g<shape id="_x0000_i1257" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image274.wmz» o:><img width=«11» height=«25» src=«dopb73598.zip» v:shapes="_x0000_i1257">·L<shape id="_x0000_i1258" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image270.wmz» o:><img width=«15» height=«27» src=«dopb73596.zip» v:shapes="_x0000_i1258">)=0,6>0
Значит, в точке (0;500) функция L имеет условный минимум.
Ответ: Выгодно производить только 500 ед. товара В, а товар А не производить.
Наиболее простым способом нахождения условного экстремума функции двух переменных  является сведение задачи к  отысканию экстремума функции одной переменной. Пусть уравнениеg(x1,x2)=0 удалось разрешить относительно одной из переменных, например, выразить х2 через х1: х2=φ(х1). Подставив полученное выражение в функцию, получим y=f(x1,x2)= y=f(x1, φ(х1)), т.е. функцию одной переменной. Её экстремум и будет условным экстремумом функции y=f(x1,x2).
Проиллюстрируем данный метод на конкретной задаче.
Фирма реализует автомобили двумя способами: через розничную и оптовую торговлю. При реализации х1 автомобилей в розницу расходы на реализацию составляют (4 х1+х<shape id="_x0000_i1259" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image047.wmz» o:><img width=«11» height=«24» src=«dopb73475.zip» v:shapes="_x0000_i1259">) у. е., а при продаже х2 автомобилей оптом – х<shape id="_x0000_i1260" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image049.wmz» o:><img width=«11» height=«24» src=«dopb73476.zip» v:shapes="_x0000_i1260">у. е. Найти оптимальный способ реализации автомобилей, минимизирующий суммарные расходы, если общее число, предназначенных для продажи автомобилей составляет 200шт.
Решение: Составим функцию L(х1, х2)=4х1+х<shape id="_x0000_i1261" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image047.wmz» o:><img width=«11» height=«24» src=«dopb73475.zip» v:shapes="_x0000_i1261">+х<shape id="_x0000_i1262" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image049.wmz» o:><img width=«11» height=«24» src=«dopb73476.zip» v:shapes="_x0000_i1262"> и будем находить её минимум. Т.к. для продажи предназначено 200 автомобилей, то х1+х2=200. Разрешим данной уравнение относительно переменной х2: х2=200-х1. Подставим полученное выражение в функцию L, получим L=4 х1+ х<shape id="_x0000_i1263" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image047.wmz» o:><img width=«11» height=«24» src=«dopb73475.zip» v:shapes="_x0000_i1263">+ (200- х1)2=2х<shape id="_x0000_i1264" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image047.wmz» o:><img width=«11» height=«24» src=«dopb73475.zip» v:shapes="_x0000_i1264">--396 х1+40000, х1<shape id="_x0000_i1265" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image278.wmz» o:><img width=«13» height=«16» src=«dopb73600.zip» v:shapes="_x0000_i1265">0.
Найдём экстремум данной функции.
<lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1248" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><img width=«293» height=«136» src=«dopb73601.zip» v:shapes="_x0000_s1247 _x0000_s1248 _x0000_s1249 _x0000_s1250 _x0000_s1251 _x0000_s1252 _x0000_s1253 _x0000_s1254 _x0000_s1255 _x0000_s1256 _x0000_s1257">            L<shape id="_x0000_i1266" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image282.wmz» o:><img width=«9» height=«27» src=«dopb73602.zip» v:shapes="_x0000_i1266">=4 х1-396.
Приравняв её к нулю, получим х1=99.
Ответ: оптимальный способ реализации автомобилей – это 99 автомобилей в розницу и 101 автомобиль оптом (х2=200-99). Расходы составят 20398 р.
В экономических задачах, в которых отыскивается оптимум функции f=(x1,x2, …, хn), где n <shape id="_x0000_i1267" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image284.wmz» o:><img width=«13» height=«16» src=«dopb73600.zip» v:shapes="_x0000_i1267">2, полагают, что найденное единственное решение, удовлетворяющее необходимому условию экстремума, является оптимальным.

4. Задача потребительского выбора.
1) Функция полезности. Бюджетное ограничение. Формулировка задачи потребительского выбора.
Будем считать, что потребитель располагает доходом Q, который он полностью тратит на приобретение благ (продуктов) Учитывая структуру цен, доход и собственные предпочтения, потребитель приобретает определённое количество благ, и математическая модель такого его поведения называется моделью потребительского выбора.
В некоторых задачах выделяют один продукт, а вторым считают все остальные. Поэтому сначала рассмотрим модель с двумя видами продуктов. Потребительский набор – это вектор (x1,x2), координата x1 которого равна количеству единиц первого продукта, а координата x2 равна количеству единиц второго продукта.
Выбор потребителя характеризуется отношением предпочтения, суть которого состоит в следующем. Считается, что потребитель про каждые два набора может сказать, что либо один из них более желателен, чем другой, либо потребитель не видит между ними разницы. Отношение предпочтения транзитивно, т.е. если набор А=(а1, а2) предпочтительнее набора B=(b1,b2), а набор B=(b1,b2) предпочтительнее набора С=(с1, с2), то наборА=(а1, а2) предпочтительнее набораС=(с1, с2).
На множестве потребительских наборов (x1,x2) определена функция u(x1,x2) (называемая функцией полезности потребителя), значение u(x1,x2) которой на потребительском наборе(x1,x2)равно потребительской оценке индивидуума для этого набора. Потребительскую оценку u(x1,x2) набора (x1,x2) принято называть уровнем (илистепенью) удовлетворения потребительского индивидуума, если он приобретает или потребляет данный набор (x1,x2). Каждый потребитель имеет, вообще говоря, свою функцию полезности. Если набор А <shape id="_x0000_i1268" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image091.wmz» o:><img width=«12» height=«23» src=«dopb73501.zip» v:shapes="_x0000_i1268">предпочтительнее набора В, то u(А)>u(В).
Функция полезности удовлетворяет следующим свойствам:
1.     Возрастание потребления одного продукта при постоянном потреблении другого продукта ведёт к росту потребительской оценки, т.е. если x<shape id="_x0000_i1269" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image285.wmz» o:><img width=«11» height=«24» src=«dopb73475.zip» v:shapes="_x0000_i1269">>x<shape id="_x0000_i1270" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image286.wmz» o:><img width=«8» height=«24» src=«dopb73472.zip» v:shapes="_x0000_i1270">, то u(x<shape id="_x0000_i1271" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image287.wmz» o:><img width=«11» height=«24» src=«dopb73475.zip» v:shapes="_x0000_i1271">,x2)> u(x<shape id="_x0000_i1272" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image288.wmz» o:><img width=«8» height=«24» src=«dopb73472.zip» v:shapes="_x0000_i1272">,x2);
                  если x<shape id="_x0000_i1273" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image289.wmz» o:><img width=«11» height=«24» src=«dopb73476.zip» v:shapes="_x0000_i1273">>x<shape id="_x0000_i1274" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image290.wmz» o:><img width=«11» height=«24» src=«dopb73473.zip» v:shapes="_x0000_i1274">, то u(x1, x<shape id="_x0000_i1275" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image289.wmz» o:><img width=«11» height=«24» src=«dopb73476.zip» v:shapes="_x0000_i1275">)> u(x1, x<shape id="_x0000_i1276" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image290.wmz» o:><img width=«11» height=«24» src=«dopb73473.zip» v:shapes="_x0000_i1276">).
Иначе говоря, u<shape id="_x0000_i1277" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image291.wmz» o:><img width=«13» height=«27» src=«dopb73587.zip» v:shapes="_x0000_i1277">(x1,x2)=u<shape id="_x0000_i1278" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image292.wmz» o:><img width=«8» height=«24» src=«dopb73603.zip» v:shapes="_x0000_i1278">>0, u<shape id="_x0000_i1279" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image294.wmz» o:><img width=«15» height=«27» src=«dopb73588.zip» v:shapes="_x0000_i1279">(x1,x2)=u<shape id="_x0000_i1280" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image295.wmz» o:><img width=«11» height=«24» src=«dopb73604.zip» v:shapes="_x0000_i1280">>0.
Первые частные производные u<shape id="_x0000_i1281" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image292.wmz» o:><img width=«8» height=«24» src=«dopb73603.zip» v:shapes="_x0000_i1281"> и u<shape id="_x0000_i1282" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image295.wmz» o:><img width=«11» height=«24» src=«dopb73604.zip» v:shapes="_x0000_i1282"> называются предельными полезностями первого и второго продуктов соответственно.
2.     Предельная полезность каждого продукта уменьшается, если объём его потребления растёт (закон убывания предельной полезности). Из свойства второй производной следует, что u<shape id="_x0000_i1283" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image297.wmz» o:><img width=«13» height=«27» src=«dopb73605.zip» v:shapes="_x0000_i1283">(x1,x2)<0, u<shape id="_x0000_i1284" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image299.wmz» o:><img width=«15» height=«27» src=«dopb73606.zip» v:shapes="_x0000_i1284">(x1,x2)<0.
3.     Предельная полезность каждого продукта увеличивается, если растёт количество другого продукта. В этом случае продукт, количество которого фиксировано, оказывается относительно дефицитным. Если блага могут замещать друг друга в потреблении, свойство не выполняется. u<shape id="_x0000_i1285" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image301.wmz» o:><img width=«21» height=«27» src=«dopb73607.zip» v:shapes="_x0000_i1285">(x1,x2)=u12>0, u<shape id="_x0000_i1286" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image303.wmz» o:><img width=«21» height=«27» src=«dopb73608.zip» v:shapes="_x0000_i1286">(x1,x2)=u21>0.
Линия, соединяющая потребительские наборы  (x1,x2), имеющие один и тот же уровень удовлетворения потребностей называется линией безразличия. Линия безразличия есть не что иное, как линия уровня функции полезности. Множество линий безразличия называется картой линий безразличия. Линии безразличия, соответствующие разным уровням удовлетворения потребностей не пересекаются и не касаются. Чем выше и правее расположена линия безразличия, тем большему уровню удовлетворения потребностей она соответствует. Условия 1-3 означают, что линия безразличия убывает и является выпуклой вниз.
Задача потребительского выбора заключается в выборе такого потребительского набора (х<shape id="_x0000_i1287" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image305.wmz» o:><img width=«9» height=«24» src=«dopb73576.zip» v:shapes="_x0000_i1287">, х<shape id="_x0000_i1288" type="#_x0000_t75" o:ole=""><imagedata src=«15300.files/image306.wmz» o:><img width=«11» height=«24» src=«dopb73577.zip» v:shapes="_x0000_i1288">), который максимизирует его функцию полезности при заданном бюджетном ограничении.
    продолжение
--PAGE_BREAK--