Симплекс - метод

Министерство  образования и науки Республики Казахстан

Мангистауский политехнический колледж

 

 

 

 

 

 

 

 

 

 

 

Тема:     Симплекс - метод

По предмету: Моделирование  экономических и производственных процессов

 

 

 

 

 

 

 

 

 

 

Выполнил:

 

                                                          Проверила:

 

 

 

 

 

 

 

 

Актау 2013

 

Содержание

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

В чем видятся преимущества математического  подхода? Отметим лишь два момента.

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

 

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

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

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

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

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

Применение экономико-математических методов и моделей позволяет  существенно улучшить качество планирования и получить дополнительный эффект без вовлечения в производство дополнительных ресурсов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.  Линейное  или математическое программирование.

На практике постоянно встречаются  такие ситуации, когда достичь  какого-то результата можно не одним, а многими различными способами. В подобной ситуации может оказаться и отдельно взятый человек, например, когда он решает вопрос о распределении своих расходов, и целое предприятие или даже отрасль, если необходимо определить, как использовать имеющиеся в их распоряжении ресурсы, чтобы добиться максимального выхода продукции, и, наконец народное хозяйство в целом. Естественно, при большом количестве решений выбирается наилучшее. Математически это обычно сводится к нахождению наибольшего или наименьшего значения некоторой функции, т.е. к задаче: найти max (min) f (х)  при условии, что переменная х (обычно говорят - точка х) пробегает некоторое данное множество Х. Пишут так:

f(x) ® max (min), xÎ X                                    (1.1)

                                 

Определенная таким образом  задача называется задачей оптимизации. Множество Х называется допустимым множеством данной задачи, а функция f(x) - целевой функцией.

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

х = (х₁, х₂, ..., х₃),

т.е. является точкой n- мерного арифметического пространства Rⁿ.

Соответственно множество Х есть подмножество в Rⁿ.

Очень многое зависит от того, в таком виде задается допустимое множество Х. Во многих случаях Х выделяется из Rⁿ с помощью системы неравенств (нестрогих):

                              (1.2)

где g₁, g₂, ..., g_n - какие-то заданные функции в Rⁿ.

Иначе говоря, Х есть множество точек (х₁, х₂,..., х_n)ÎRⁿ ,удовлетворяющих системе неравенств (1.2).

В этом случае задача оптимизации  приобретает следующий вид. Даны функция n переменных f(х₁, х₂, ..., х_n) и система неравенств (1.1). Требуется найти max (min) f при условиях (1.1).

f(х₁, х₂, ..., х_n) ® max (min) при условиях (1.1).

 

Понятно, что следует найти не только само значение max (min) f, но и точку или точки, если их несколько, в которых это значение достигается. Такие точки называются оптимальными решениями. Множество всех оптимальных решений будем называть оптимальным множеством и обозначать Х^*.

Задачи подобного рода получили название задачи математического программирования ( не следует путать математическое программирование с машинным). При этом функцию f называют целевой функцией, а неравенства g_i ³ 0 (i = 1,2,...,m) - ограничениями. В большинстве случаев в число ограничений входят условия неотрицательности переменных:

х₁³ 0, х₂ ³ 0,..., х_n³ 0

или части переменных, но это, впрочем, не обязательно.

В зависимости от характера функции f, g₁, ...,g_m различают разные виды математического программирования. Наиболее простой и часто встречающийся случай, когда эти функции являются линейными, т.е. каждая из них имеет вид

а₁х₁+а₂х₂+ ...+а_nх_n +b.

 

Дадим теперь общую формулировку задачи линейного программирования.

Пусть S - система линейных ограничений ( т.е. линейных уравнений или нестрогих линейных неравенств) с n переменными х₁, х₂,..., х_n , а f(х) - целевая функция вида

f(х) = с₁х₁ + с₂х₂ + ...+ с_nx_n + c.

 

Требуется решить задачу

f(х) ® max (min) при условиях S.

 

Обычно система S включает в себя условия неотрицательности всех переменных:

х₁³ 0, х₂ ³ 0,..., х_n³ 0,                          (1.3)

 

что вытекает из реального смысла чисел х₁, х₂,..., х_n. Будем называть эти условия тривиальными ограничениями.

1.  Каноническая задача.

В этом случае система S, помимо тривиальных ограничений (1.3), включает в себя только уравнения.

Определение:

Если ищется max значение функции цели, а все ограничения являются равенством, все переменные не отрицательны, то такая система - называется системой в каноническом виде, а задача - является задачей в канонической форме.

В этом случае модель задач  можно записать в векторной форме:

f(х) = с₁х₁ + с₂х₂ + ...+ с_nx_n ® max

`А<sub>1</sub>х<sub>1</sub> + `А₂х₂ + ... + `А_nх_n = B

x_j = 0    (j =1`,n)

 

`A₁ =

          `A<sub>2</sub> =            `B =

 

Записать задачу в каноническом виде:

f = -х₁+2х₂-х₃+х₄ ® min

           x_j=0 (j=1`; 4)

 

Вместо того, чтобы исследовать  функцию f на min, будем исследовать на

f₁= - f на max.

В ограничениях содержащих £ к левой части прибавим дополнительную не отрицательную переменную. В ограничениях содержащих ³ - в левой части вычтем не отрицательную дополнительную переменную. Условие не отрицательности в равенство не переводится.

 

f₁ = -f =х₁ - 2х₂ + х₃ - х₄ ® max

 

  х_j³ 0 (j =`1; 7)

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

Замечание: Если переменная х_к не подчинена условию не отрицательности, ее нужно заменить на разность двух не отрицательных величин

x_k = u_k + v_k .

Определение: Совокупность не отрицательных чисел х₁, х₂,..., х_n , удовлетворяющих ограничениям задачи, называются допустимым решением или просто планом задачи.

План Х^* = (х₁^*, х₂^*, ..., х_n^*) при котором целевая функция достигает своего экстремального значения, называется оптимальной.

Не нулевые  допустимые решения задачи, называются базисными решениями, если соответствуют им векторы `А_j образуют линейно не зависимую систему.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Симплекс - метод .

 

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

Для  работы по симплекс-методу требуется:

1. привести задачу к канонической форме;
2. представить ее в векторной форме;
3. заполнить первую симплексную таблицу;
4. проверить план на оптимальность;
5. если план не оптимален, то выбрать разрешающий элемент, произвести пересчет всех элементов симплексной таблицы и перейти к п.4

 

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

Для построения первой таблицы из векторов `А_j нужно выбрать несколько компонентов, которые образуют единичную матрицу . И если исходная система ограничений, содержит только неравенства £ или ³, то при введении дополнительных переменных, сразу получают базисные векторы, которые образуют первый базис в симплекс-таблицах.

 

 

 

 

 

Сб	Хб	план	С1   х1	С2   х2	.....   ....	Сn   хn
Dj		D0	D1	D2	...	Dn