Методы экономико-математического моделирования (стр. 1 )

Глава 1

МЕТОДЫ ЭКОНОМИКО-МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ

1.1. ПРЕДМЕТ И НАЗНАЧЕНИЕ МОДЕЛИРОВАНИЯ

Принцип аналогии в моделировании, общее понятие модели

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

При изучении методом аналогии непосредственному исследо­ванию всегда подвергается одна система, а вывод делается для другой. Система, которая исследуется непосредственно, является отображением или моделью изучаемой системы, оригинала.

Модель (лат. modulus) - мера, мерило, образец, норма. В математике существует теория моделей, в которой под моделью понимается произвольное множество с заданным на нем набо­ром свойств и отношений. Модель представляет собой отображение каким-либо способом наиболее существенных характеристик, процессов и взаимосвязей реальных систем, а под моделированием понимает­ся воспроизведение или имитирование какой-либо существующей системы на специально построенном аналоге или модели.

Под моделированием понимается ис­следование объектов познания не непосредственно, а косвенным путем, с помощью анализа некоторых других вспомогательных объектов - моделей.

Все экономические модели можно в общем смысле разбить на два класса:

•  модели позитивного анализа - для познания свойств реаль­ных или гипотетических экономических систем. Значение их па­раметров невозможно оценить по эмпирическим данным;

•  модели нормативного анализа - для прогнозирования или принятия управляющих решений. Их параметры можно оценить по опытным данным.

Объектом моделирования является зафиксированный или по крайней мере наблюдаемый процесс развития экономического объекта во времени.

Экономико-математические модели

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

Математическая модель имеет другую по сравнению с реаль­ным объектом природу и представляет собой уравнение или систему уравнений и неравенств, описывающую взаимосвязи, происходящие в оригинале.

Математическое моделирование получило широкое распростра­нение в исследовании экономических систем. Это обусловлено тем, что экономические системы характеризуются сложными количественными взаимозависимостями, которые можно выразить как взаимосвязь множества переменных и которые хорошо поддаются ма­тематическому описанию в виде уравнений и неравенств. Исполь­зуется оно как средство изучения, как инструмент познания эко­номических явлений. Анализируя уравнения и неравенства, кото­рые описывают количественные взаимосвязи данной системы, мож­но анализировать и саму экономическую систему.

Следовательно, под экономико-математической моделью пони­мается описание количественных взаимосвязей и взаимозависимо­стей экономических систем или процессов в математической форме.

Экономические системы характеризуются огромным количест­вом взаимосвязей, детальный учет которых привел бы к очень громоздким и практически неиспользуемым моделям или системе моделей. Важно включить в модель факторы, оказывающие основ­ное влияние на производство, и не менее важно опускать те из них, которые не оказывают на него существенного влияния. Таким об­разом, экономико-математическая модель характеризует наиболее важные свойства конкретных экономических систем, абстрагируясь от деталей и частностей.

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

Математическое моделирование открыло широкие возможно­сти для изучения экономических взаимосвязей и закономерностей. С появлением математического модели­рования и ЭВМ стало возможным экспериментирование и в эко­номике, но не на реальных объектах, а на математических моделях экономических систем и явлений. Для этого необходимо представить экономический процесс в виде экономико-мате­матической задачи и решить ее на ЭВМ. Причем, изменяя условия, можно проанализировать множество вариантов и выбрать наибо­лее выгодный из них. Это открывает новые возможности, как в проверке различных гипотез, предположений, так и в совершенствовании реального про­цесса воспроизводства.

Математическое моделирование предполагает предварительный качественный анализ условий, в которых будут проявляться коли­чественные взаимосвязи моделируемого объекта. Вид и характер математической модели определяются взаимо­связями и взаимозависимостями экономических систем.

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

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

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

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

Экономико-математическая модель должна включать форма­лизованное описание критерия выбора, т. е. экономической цели: целевую функцию.

Делая свой выбор, люди всегда учитывают не только сущест­вующую экономическую ситуацию, но и ее будущие изменения, т. е. изменившиеся ожидания. Следовательно, выбор осуществля­ется в динамике.

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

1.2. ОБЩАЯ ЗАДАЧА ОПТИМИЗАЦИИ

Первые задачи, связанные с отысканием наименьших и наибольших величин, были поставлены в древности. Упоминания о максимумах и минимумах встречаются в трудах Евклида, Аполло­ния, Архимеда. Потребность решать экстремальные проблемы спо­собствовала созданию математического анализа и вариационного исчисления. В XVII и XVIII веках были открыты вариационные принципы в оптике и механике, вариационное исчисление стало языком экономики и естествознания.

В становлении современных методов оптимизации сыграли оп­ределенную роль ученые Куисни (1759) и Л. Вальрас (1874), предло­жившие первые элементарные модели математического программи­рования. Фон Нейман (1937) и (1939) разработали экономические модели оптимизации. Математические основы линейного программирования разрабатывались
М. Жорданом (1873), Г. Мынковским (1896) и Ю. Фаркашем (1903). Серьезный вклад в| динамическое программирование внес (1954), а также
(1920), разработавший элементы теории массового обслуживания. Важную роль в теории оптимизации сыграл фундаментальный труд Г. Вагнера (1969), который является одним из ведущих специалистов по исследованию операций.

Оптимизация имеет важное значение в экономических исследованиях.

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

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

Предприятие (фирма) - группа лиц, организующих совместную деятельность для производства товаров и услуг и реализации их домашним хозяйствам и другим фирмам.

Основная экономическая цель потребителя — достичь максимального уровня удовлетворения при расходовании дохода, выбрав среди доступных ему вариантов поведения один — наи­лучший.

Основная экономическая цель производителя — достичь максимума прибыли при выборе наилучшей производственной прог­раммы.

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

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

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

Поведение производителя или потребителя математически выражается в выборе неизвестного вектора (объемов товаров и услуг) из множества векторов, или некоторой «n-мерной точки х = (х1, х2,..,хп) из n-мерного «пространства товаров». «Товар» - объем некоторого блага (услуги), который производится или пот­ребляется, т. е. x j (j=1,2…,n).

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

1.3. ЗАДАЧА МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Пусть поведение некоторого экономического объекта описы­вается системой уравнений (1.1)

g](x],x2,...,xn)=0;

(1.1)

g2(x1,x2,...,xn)=0;

…………………

gm(xl, x2,...,xn)=0.

где gj (i = 1,2, ..., m) - производственные условия деятельности объекта;

xj (j=1,2,…,п) - интенсивности деятельности (объемы выпуска про­дукции).

В общем случае система уравнений (1.1) не имеет единственного решения (т. е. единственного способа функционирования объекта: завода, фирмы, холдинга). Каждому набору переменных х = (x1,х2,хп), например объемов производства товаров, соответствует набор способов их получения:
g1 (x), g2(х), …, g m(x).

Ставится задача отыскать наилучшее (оптимальное, экстремальное) в определенном смысле решение. Для этого строится специальная функция
f(х1, х2, хn), которая оценивает качество каждого конкретного решения (х1,x2,…,xn) - плохое или хорошее. Наилучшим будет решение (х1,x2,…,xn) при котором
f (х1,x2,…,xn) , принимает свое экстремальное значение, т. е.

f (х1,x2,…,xn) ® max(min). (1.2)

Таким образом, система уравнений (1.1) вместе с функцией (1.2) представляет собой экономико-математическую модель оптимального планирования или задачу математического программирования. Здесь (1.1) - система условий, или ограничений; (1.2) - функция цели, критерий оптимизации.

В зависимости от конкретного вида функций gi и f в теории математического программирования выделяют несколько разделов:

• линейное программирование: f — линейная функция, (1.1) — система линейных уравнений и неравенств. Этот метод моделирования, наиболее простой и изученный, до сих пор наиболее широко применяется для решения экономических задач;

• нелинейное программирование (выпуклое) — условия задачи и ее цель выражены нелинейными зависимостями.

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

В 1939 г. появилась работа советского ученого «Математические методы организации и планирования производства», где впервые был предложен метод решения задач линейного программирования. В 1940-х гг. в США этой же теорией занимался Дж. Данциг. В 1952 г. задача линейного программирования впервые была решена на ЭВМ.[1.3,1.4,1.10,1.11]

Сформулируем задачу линейного программирования в общем виде:

(i=1,...,m);

z =,

где аij и cj — известные параметры; xj - неизвестные.

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

max f(x), x=[xj],j=1,...,n

при условиях:

gj ≤ 0, i= 1,...,m; (1.3)

xj ≥ 0, j= 1, 2,...,n. (1.4)

Содержательная формулировка задачи: найти х* € К такой, что f(x*) ≥ f(x) для всех х € К, где K — допустимое множество, определяемое условиями (1.3), замкнутое; f (х) — целевая функция (цель задачи); х — n-мерный вектор переменных; (1.3) — функциональные ограничения (нестрогие, чтобы обеспечить замкнутость допустимого множества); (1.4) — прямые ограничения.

Функции f (х), gj (х) — непрерывные.

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

Достаточные условия существования оптимума

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

Двумерный случай: f(х) =f(x1, х2) показан на рис. 1.1 и 1.2.

Оптимальная точка должна лежать в допустимом множестве. Это либо внутренняя, либо граничная точка. Таким образом, решение общей задачи на оптимум заключается в том, чтобы найти max (min) f(x) при х, принадлежащих замкнутому допустимому множеству К. Если решение существует, то является либо критической точкой функции f(x), либо граничной точкой множества К.

Если f(х) не является всюду дифференцируемой, то вместе с критическими и граничными точками необходимо исследовать и точки, в которых f(x), не дифференцируема.

Целевая функция f (х) может иметь глобальный оптимум (единственный) либо несколько локальных. Большинство известных методов оптимизации позволяет вычислить только локальный оптимум.

Достаточные условия совпадения оптимумов

В задаче оптимизации непрерывной функции f(x), на замкнутом допустимом множестве K каждый локальный оптимум будет глобальным, если:

1) f(x) - вогнутая (выпуклая вверх) функция в задаче максимизации и выпуклая в задаче минимизации;

2) К - выпуклое множество.

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

1.4. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

В развернутом виде линейная модель оптимального планирования запишется следующим образом:

f = c1 x1 + c2 x2 +… + cn xn ® max (min) (1.5)

при условиях:

a11 x1 + a 12 x2 +… + a 1n xn ≤ b1 ;

a21 x1+ a 22 x2 +… + a 2 n xn ≤ b2 ;

………………………………. (1.6)

am1 x1 + a m2 x2 +… + a mn xn ≤ bm ;

xj ≥ 0 (j=1,2,…n).

Эту же экономико-математическую модель можно записать в сжатой форме (структурной):

F = (1.5’)

при условиях

i=1,...,m; (1.6’)

xj ≥0, ( j= 1, 2, ..., n),

где п — общее количество переменных (неизвестных) величин;

j - порядковый номер переменной;

т — общее количество ограничений;

i — порядковый номер ограничений;

хj - — переменная, обозначающая j-й способ деятельности;

- оценка целевой функции в расчете на единицу j-го вида деятельности;

aij - норма затрат /-го вида ресурса на единицу j-го вида деятельности;

bi — объем имеющегося ресурса i-го вида.

Дадим определения основных структурных элементов задачи линейного программирования.

Итак, задача линейного программирования (1.5, 1.6) в экономике называется линейной моделью оптимального планирования. Целевая функция f — критерий оптимальности модели. Решение [xj] - план (производственная программа, способ функционирования). Множество решений системы линейных неравенств (1.6) без учета целевой функции — множество допустимых решений (в математике) и совокупность допустимых планов (в экономике). Точка оптимума (n-мерный вектор [x*j], при котором достигается f(х)), т. е. оптимальное решение задачи линейно­го программирования (1.5, 1.6), в экономике называется оптимальным планом.

Повторим: задача линейного программирования состоит в отыскании значений п переменных x1, х2,…,хn доставляющих экстремум функции f(x1x2,..,хn) при условиях (1.6), представляющих собой систему линейных нестрогих неравенств, которые в случае необходимости могут быть превращены в равенства посредством присоединения искусственных переменных xn+i (i=1,2,..,m). Обычно добавляются условия неотрицательности переменных xj ≥ 0 (j = 1, 2,.., n).

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

Свойства решений задачи линейного программирования во многом зависят от особенностей области определения, заданной условиями (1.6). Для изучения этих свойств введем основные понятия.

1.  Множество точек {х}, х = (х1 х2,…, хn), удовлетворяющих системе (1.6), есть область определения задачи линейного программирования. Когда
п = 2, область определения - многоугольник на плоскости, в общем случае — n-мерный многогранник.

2.  Функция f(x) — целевая функция (плоскость при п = 2, в общем случае — гиперплоскость); она достигает экстремума в одной или нескольких допустимых точках области определения. Эти точки называются оптимальным решением.

3.  Область определения называется выпуклой, если вместе с двумя любыми точками она содержит и весь отрезок, соединяющий эти точки.

4.  Область определения является замкнутой (т. е. содержащей собственную границу), так как в выражении (1.6) все неравенства нестрогие.

Точка х, принадлежащая выпуклой области, называется крайней, если в данной области нет двух таких точек х1 и х2, что х находится на отрезке между х1 и х2.

Крайняя точка не совпадает с граничной.

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

5.  Если не существует точки х = (х1 х2,.., хn), удовлетворяющей системе (1.6), тогда область определения задачи линейного программирования — пустое множество, а система (1.6) называется несовместной. Экстремум целевой функции не существует.

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

7.  Множество экстремальных точек х* (точек, в которых f = extr) в задаче линейного программирования (если оно непусто) всегда содержит, хотя бы одну крайнюю точку многогранника (области определения).

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

На рис. 1.3 точки О, Е1 Е2 Е3, Е4 — экстремальные. Оптимум задачи лежит в одной из них либо на множестве экстремальных точек (отрезок в двумерном случае).

Из свойств 1—7 следует, что всякая процедура, предусматривающая направленный перебор крайних точек области определения задачи (1.5, 1.6), должна привести к отысканию среди них точки экстремума х*, т. е. оптимального решения. Эта идея отражена в симплекс-методе. Он позволяет найти крайнюю точку области определения и оценить, является ли она точкой экстремума целевой функции f. Если нет, то обеспечивается переход к соседней крайней точке, где значение f больше (меньше) предыдущего. Через конечное число шагов точка экстремума либо оказывается найденной, либо признается несуществующей (система условий (1.6) несовместна).

Рис. 1.3. Геометрическая схема решения задачи линейного программирования

Симплекс-метод часто называют методом последовательного улучшения плана. Для обоснования алгоритма расчетов симплекс-метода будем рассматривать каноническую задачу линейного программирования (простейшую): min сх при Ах = b, х ≥ 0, где А - матрица; b, с, х — векторы.

Пусть известна угловая (крайняя) точка х = (х1 х2,.., хп) — опорный план.

Ненулевые значения компонент хj образуют вектор, который называется базисом. Для невырожденных задач базис содержит т компонент (т < п). Итерационный шаг метода состоит в переходе от угловой точки х к угловой точке х', при котором значение целевой функции убывает: (сх') < (сх).

Метод реализован в виде стандартных пакетов прикладных программ на всех массовых моделях ЭВМ и широко используется при решении практических задач экономического анализа и планирования.

Перечислим другие классы задач оптимизации, для которых существуют эффективные (не всегда конечные) методы решения [1.4].

1.  Квадратичное программирование — задача минимизации положительно определенной квадратичной формы при линейных ограничениях.

2.  Целочисленное программирование - задача ЛП, в которой все или некоторые переменные могут принимать только дискретные значения.

3.  Выпуклое программирование — задача максимизации вогнутых целевых функций на выпуклых множествах.

4.  Стохастическое программирование — задача Л П, в которой матрица А и вектор b содержат случайные параметры с известным законом распределения либо сами ограничения носят вероятностный характер.

5.  Блочная задача линейного программирования большой
размерности — задача ЛП, в которой матрица А имеет вид шахматной доски со связующими переменными и (или) ограничениями, а общая размерность превышает (500*500).

6.  Динамическое программирование — система методов, поз­воляющих решать многоэтапные задачи планирования.

7.  Многокритериальная оптимизация — с несколькими целе­выми функциями.

1.5. ДВОЙСТВЕННАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Для экономического анализа весьма важным является анализ двойственной задачи ЛП, так как принципы двойственности проясняют природу цен. Цена — самое фундаментальное понятие экономической теории.

Пусть стандартная задача ЛП в векторно-матричных обозначениях записывается в виде: найти

х = (х1 х2,…, хп )

чтобы получить

max cx (1.7)

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

Ax ≤ b, x ≥0. (1.8)

Где с - n-мерная вектор-строка;

b - m-мерный вектор-столбец;

А – матрица m*n;

m – произвольное число, m < n.

Двойственной по отношению к исходной задаче (1.7, 1.8) называется задача вида: найти

y (y1,y2,…,ym) (1.9)

чтобы обеспечить

min yb

при условиях

yA ≥ c, y ≥ 0. (1.10)

Здесь А, b, с имеют тот же смысл, что в задаче (1.7, 1.8).

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

1-я теорема двойственности (теорема существования). Допустимый вектор прямой задачи х* оптимален тогда и только тогда, когда существует допустимый вектор двойственной задачи у*, такой, что сх* = y*b. В этом случае у* — оптимальный вектор двойственной задачи.

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

2-я теорема двойственности (теорема равновесия).

1. Пусть векторы х* и у* допустимы в прямой и двойственных задачах соответственно. Они оптимальны тогда и только тогда, когда выполняются следующие условия:

а) у*i ≥ 0, но у*i = 0, если , i=1,...,m;

б) x*j ≥ 0, но х j * = 0, если , j=1,…,n.

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

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

2-я теорема двойственности дает возможность экономической интерпретации двойственной задачи, что иллюстрирует следующий пример.

Задана линейная модель производства, в которой выпускается п продуктов [xj] и затрачивается т факторов [bi], [аij] - постоянные коэффициенты затрат.

С другой стороны, заданы векторы цен [pi] и вектор ресурсов [bi], ограничивающий использование факторов.

По 1-й теореме двойственности имеем рх* = y*b (стоимость продукции равна стоимости затраченных факторов. Следова­тельно, у* — вектор цен на факторы).

Двойственные переменные часто называются условными оценками (двойственными оценками, объективно обусловленными оценками). В данном случае они дают ответ на вопрос: какова наименьшая стоимость набора факторов b, дающая возможность обращения факторов в продукты и продажи продуктов по ценам р. Если оценка затрат, необходимых для производства продукта, меньше цены продукта, то более выгодно произвести и продать продукт, чем продать эти факторы. При оптимальных значениях х* и у* фирме безразлично, выпускать ли продукты, чтобы продать по ценам р, или продать ресурсы по ценами y*, так как y* b= р х* .

По 2-й теореме двойственности имеем:

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

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

Прямая задача Двойственная задача

max px min yb

Ах ≤ Ь, х ≥0 yА ≥ р, у ≥ 0

Запись прямой и двойственной задач в развернутой форме приведена ниже.

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

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

F = c1 x1 + c2 x2 + …+ cn xn ® max при ограничениях a11 x1 + a 12 x2 +… + a 1n xn ≤ b1 a21 x1+ a 22 x2 +… + a 2 n xn ≤ b2 ………………………………. am1 x1 + a m2 x2 +… + a mn xn ≤ bm и условии неотрицательности x1 ≥ 0 ,x2 ≥ 0,…, xn ≥ 0. Составить такой план выпуска про­дукции Х= (x1 ,x2 ,…, xn ), при кото­ром прибыль (выручка) от реализа­ции продукции будет максималь­ной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов

Z = b1 y1 + b2 y2 + …+ bn yn ® min при ограничениях a11 y1 + a 21 y2 +… + a m1 ym ≥ p1 a12 y1 + a 22 y2 +… + a m2 ym ≥ p2 ………………………………. a1n y1 + a 2n y2 +… + a mn ym ≥ pm и условии неотрицательности y1 ≥ 0 ,y 2 ≥ 0,…, ym ≥ 0. Найти такой набор цен (оценок) ре­сурсов У = (у1 у2 ,..., ут), при кото­ром общие затраты на ресурсы бу­дут минимальными при условии, что затраты на ресурсы при произ­водстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции

Пусть ν * — оптимальное значение целевой функции, у* — оптимальный вектор двойственной задачи. Заменим b на b+ b так, чтобы х* — начальный оптимальный план и в новой задаче оставался допустимым. Тогда вариация v* оптимального значения целевой функции определяется соотношением: v* = у* b, или для фиксированного i: v* = yi* bi.