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

42

Федеральное агентство по образованию

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

Математический факультет

Кафедра математического анализа и методики преподавания математики

Выпускная квалификационная работа

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

Выполнила:

студентка V курса математического факультета

Голомидова Ирина Витальевна

Научный руководитель:

Ст. преподаватель кафедры математического анализа и МПМ

С. А. Фалелеева.

Рецензент:

кандидат педагогических наук, ст. преподаватель кафедры математического анализа и МПМ

Л.В. Караулова.

Допущена к защите в государственной аттестационной комиссии

«___» __________2005 г. Зав. кафедрой М.В. Крутихина

«___»___________2005 г. Декан факультета В.И. Варанкина

Киров

2005

Содержание

Введение 3

1. Математические модели в экономике 4

2. Некоторые понятия функций нескольких переменных 6

3. Задача математического программирования

1) Общая постановка задачи 8

2) Задача линейного программирования и способы её решения 9

3) Двойственная задача 19

4) Задача нелинейного программирования 26

5) Задача на условный экстремум 31

4. Задача потребительского выбора.

1) Функция полезности. Бюджетное ограничение. Формулировка задачи потребительского выбора. 34

2) Решение задачи потребительского выбора и его свойства 36

3) Общая модель потребительского выбора 39

4) Модель Стоуна 40

Заключение 42

Библиографический список 43

Введение

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

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

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

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

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

При написании дипломной работы были поставлены следующие задачи:

· Рассмотрение некоторых экономических задач и составление математических моделей.

· Изучение некоторых математических методов, применяемых для решения оптимизационных задач в экономике.

· Практическое решение задач.

1. Математические модели в экономике

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

Математические модели использовались с иллюстративными исследованиями ещё Ф. Кене (1758г., «Экономическая таблица»), А. Смитом (Классическая макроэкономическая модель), Д. Риккардо (Модель международной торговли). В XIX веке большой вклад в моделирование рыночной экономики внесли математики Л. Вальрас, О. Курно, В. Парето и другие. В XX веке математические методы моделирования применялись очень широко, с их использованием связаны практически все работы, удостоенные Нобелевской премии по экономике (Р. Солоу, В. Леонтьев, Л. Канторович и другие). Развитие макроэкономики, микроэкономики, прикладных дисциплин связано со все более высоким уровнем их формализации. Основу для этого заложил прогресс в области прикладной математики. В России в начале XX века большой вклад в математическое моделирование экономики внесли В.К. Дмитриев и Е.Е. Слуцкий. В 1960-е - 80-е годы экономико-математическое направление было связано, в основном, с попытками формально описать «систему оптимального функционирования социалистической экономики» (Н.П. Федоренко, С.С. Шаталин). Строились многоуровневые системы моделей народно - хозяйственного планирования, оптимизационные модели областей и предприятий.

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

Можно выделить 3 этапа проведения математического моделирования в экономике:

1. ставятся цели и задачи исследования, проводится качественное описание объекта в виде экономической модели.

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

3. осуществляется обработка и анализ полученных результатов.

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

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

2. Некоторые понятия функций нескольких переменных

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

Переменная y называется функцией нескольких переменных x₁,x₂,…,x_n, если существует отображение f: Rⁿ>R. Множество всех точек М, участвующих в этом отображении, называется областью определения функции, где М(x₁,x₂,…,x_n).

Наиболее часто встречается функция двух переменных. В экономике для её изучения широко применяются линии уровня.

Линиями уровня функции двух переменных y=f(x₁,x₂) называется проекция пересечения графика функции y=f(x₁,x₂) с горизонтальной плоскостью на плоскость Ох₁х₂, причём линия пересечения находится от плоскости Ох₁х₂ на высоте С. Уравнение линии уровня имеет вид f(x₁,x₂)=С. Число С в этом случае называется уровнем.

Как и в случае одной переменной, функция y=f(x₁,x₂) имеет узловые, определяющие структуру графика, точки. В первую очередь это точки экстремума. Точки экстремума функции двух переменных определяются аналогично точкам экстремума функции одной переменной

Сформулируем необходимое условие экстремума - многомерный аналог теоремы Ферма: Пусть точка () - есть точка экстремума дифференцируемой функции y=f(x₁,x₂). Тогда частные производные (), () в этой точке равны нулю.

Точки, в которых выполнены необходимые условия экстремума функции y=f(x₁,x₂), т. е частные производные равны нулю, называются стационарными.

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

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

Достаточное условие экстремума функции двух переменных. Пусть функция y=f(x₁,x₂):

a) определена в некоторой окрестности стационарной точки (), в которой ()=0 и ()=0;

b) имеет в этой точке непрерывные частные производные второго поряка()=А,()=()=В,()=С.

Тогда, если =АС-В² >0, то в точке () функция имеет экстремум, причём, если А>0 минимум, А<0 - максимум. В случае =АС-В² <0, функция y=f(x₁,x₂) экстремума не имеет. Если =АС-В² =0, то вопрос о наличии экстремума остаётся открытым. Требуются другие методы определения экстремума. [11]

В экономических задачах чаще встречаются задачи на условный экстремум. Перейдем к рассмотрению таких задач.

3. Задача математического программирования (ЗМП).

1) Общая постановка задачи

В теории экстремума на независимые переменные x₁,x_2, …,х_n не накладываются никакие дополнительные условия, т.е. не требуется, чтобы переменные удовлетворяли некоторым дополнительным ограничениям.

Рассмотрим другую задачу. Найти максимум (минимум) функции y=f(x₁,x_2, …,х_n), при условии, что независимые переменные x₁,x_2, …,х_n удовлетворяют системе ограничений:

g₁(x₁,x_2, …,х_n) ?b₁,

…………………………

g_m(x₁,x_2, …,х_n) ?b_m,

g_m+1(x₁,x_2, …,х_n) ?b_m+1,

…………………………

g_k(x₁,x_2, …,х_n) ?b_k, (3.1)

g_k+1(x₁,x_2, …,х_n) =b_k+1,

…………………………

g_p(x₁,x_2, …,х_n) =b_p,

x₁,x_2,…,х_n ?0.

Функцию y=f(x₁,x_2, …,х_n) принято называть целевой, т.к. её максимизация (минимизация) часто есть выражение какой-то цели, систему ограничений (3.1) - специальными ограничениями ЗМП, неравенства x₁?0 ,x?0_2, …, х_n?0 - общими ограничениями ЗМП. Множество всех допустимых решений ЗМП (х_j?0, j=) называется допустимым множеством этой задачи.

Точка () называется оптимальным решением для функции двух переменных, если, во-первых, она есть допустимое решение этой ЗМП, а во-вторых, на этой точке целевая функция достигает максимума (минимума) среди всех точек, удовлетворяющих ограничениям (3.1), причём

f ()? f(x₁,x₂)(в случае решения задачи на отыскание максимума),

f () ? f(x₁,x₂) (в случае решения задачи на отыскание минимума).

Если в ЗМП все функции f(x₁,x_2, …,х_n), g_i(x₁,x_2, …,х_n) линейны, то имеем задачу линейного программирования (ЗЛП), если хотя бы одна из функций нелинейная, имеем задачу нелинейного программирования (ЗЛП). Рассмотрим ЗЛП.

2) ЗЛП и способы её решения.

ЗЛП имеет вид F=c₁x₁+c₂x₂+…+c_nx_n+c₀>min(max). При этом переменные должны удовлетворять ограничениям:

а₁₁х₁+ а₁₂х₂+…+а_1nх_n?b₁

…………………………

а_m1х₁+ а_m2х₂+…+a_mnx_n?b_m

а_m+11х₁+ а_m+12х₂+…+а_m+1nх_n?b_m+1

…………………………

а_k1х₁+ а_k2х₂+…+а_knх_n?b_k (3.2)

а_k1+1х₁+ а_k+12х₂+…+а_k+1nх_n=b_k+1

………………………….

а_p1х₁+а_p2х₂+…+а_pnх_n=b_p

x₁,x_2,…,х_n ?0.

ЗЛП может быть записана в различных формах:

Общий вид: найти минимум (максимум) целевой функции F при ограничениях (3.2) и условии неотрицательности переменных.

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

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

Стандартную задачу можно привести к каноническому виду, путём введения дополнительных неотрицательных переменных. Т.е. свести к системе m линейных уравнений с n переменными.

Любые m переменных системы m линейных уравнений с n переменными (m<n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные m-n переменных называются неосновными или (свободными).

Базисным решением системы m линейных уравнений с n переменными называют решение, в котором все m-n неосновных переменных равны нулю.

Для обоснования свойств ЗЛП и методов её решения, рассмотрим 2 вида записи канонической задачи.

1 вид - матричная форма записи: С=(c₁,c₂…c_n,c₀).

Х= А= В= (3.3)

F=CX> min (max)

AX=B, X?0

2 вид - векторная форма записи:

F=CX> min (max)

р₁x₁+р₂x₂+…+р_nx_n=р. Х?0.

р₁= р₂= … р _n=.

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

Множество точек является выпуклым, если оно вместе с любыми своими двумя точками содержит их произвольную линейную комбинацию. Точка Х является выпуклой линейной комбинацией точек Х₁, Х₂, … Х_n, если выполняются условия Х= б₁x₁+б₂x₂+…+б_nx_n, б_j?0, (j=1,…,n), .

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

Теорема 2. Множество всех допустимых решений системы ограничений ЗЛП является выпуклым.

? Пусть Х₁=( x,x_, …,х) и Х₂=( x,x_, …,х)- два допустимых решения задачи (3.3), заданной в матричной форме. Тогда АХ₁=В и АХ₂=В. рассмотрим выпуклую линейную комбинацию решений Х₁ и Х₂ , т.е. Х=б₁Х₁+б₂Х₂ при б₁ ?0, б₂ ?0 и б₁+б₂=1. Покажем, что она также является допустимым решением системы АХ=В. В самом деле, АХ=А(б₁Х₁+б₂Х₂)=б₁АХ₁+(1-б₁)АХ₂= б₁В+(1-б₁)В=В, т.е. решение удовлетворяет системе ограничений. Но т.к. Х₁?0, Х₂ ?0, б₁ ?0, б₂ ?0 , то и Х ?0, т.е. решение Х удовлетворяет условию (3.3). ¦

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

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

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

? Будем полагать, что многогранник решений является ограниченным. Обозначим его угловые точки через Х₁,Х_2, …,Х_n , а оптимальное решение через Х^*. Тогда F(Х^*) ?F(X), для всех точек многогранника решений. Если Х^* угловая, то первая часть теоремы доказана. Предположим, что Х^* не является угловой точкой, тогда Х^*, на основании теоремы 1, можно представить как выпуклую линейную комбинацию угловых точек многогранника решений, т.е. Х^*=б₁x₁+б₂x₂+…+б_рx_р, б_j?0, (j=1,…,n), . Т.к.

F(Х^*)=F(б₁x₁+б₂x₂+…+б_рx_р)=б₁F(x₁)+б₂F(x₂)+…+б_рF(x_р). (3.4)

В этом выражении среди значений F(X_j)(j=1,2,…,p) выберем максимальное. Обозначим его через М, т.е. М=max F(X_j). Тогда

б₁F(x₁)+ б₂F(x₂) +…+ б_рF(x_р)? б₁М+ б₂М +…+ б_рМ = М(б₁+б₂+…+б_р) =М.

Значит F(Х^*)?М. Пусть М=F(X_k), т.е. соответствует угловой точке X_k (1?к?р).

Тогда F(Х^*) ? F(X_k). Но по предположению Х^* - оптимальное решение, поэтому F(Х^*)?F(X_k)=М, следовательно, F(Х^*)=М=F(X_k), где X_k- угловая точка. Итак, существует угловая точка X_k, в которой линейная функция принимает максимальное значение.

Для доказательства второй части теоремы допустим, что F(Х) принимает максимальное значение более чем в одной угловой точке, например в точках Х₁, Х₂, … Х_q , где 1? q ? р; тогда F(Х₁)=F(Х₂)=…=F(Х_n)=M.

Пусть Х выпуклая линейная комбинация этих угловых точек, т.е. Х= б₁Х₁+б₂Х₂+ …+б_qХ_q , б_j?0, (j=1,…,q), . В этом случае, учитывая, что функция F(Х) - линейная, получим F(Х)=F(б₁Х₁+б₂Х₂+…+б_qХ_q)=б₁F(Х₁)+ +б₂F(Х₂)+…+б_qF(Х_q)=б₁M+б₂M+…+б_qM=M=M, т.е. линейная функция F принимает максимальное значение в произвольной точке Х, являющейся выпуклой линейной комбинацией угловых точек Х₁, Х₂, … Х_q ¦

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

Доказанная теорема является фундаментальной, т.к. она указывает принципиальный путь решения ЗЛП.

Рассмотрим геометрический метод решения ЗЛП в случае функции двух переменных.

Было доказано, что оптимальное решение ЗЛП находится, по крайней мере, в одной из угловых точек многогранника решений.

Рассмотрим задачу в стандартной форме с двумя переменными.

F=c₁x₁+c₂x₂+с₀ >min(max),

При ограничениях а₁₁х₁+ а₁₂х₂ ?b₁,

а₂₁х₁+ а₂₂х₂ ?b₂,

………………

a_n1х₁+ а_n2х₂?b_n ,

при условии, что x₁ ?0 ,x₂ ?0 .

Пусть геометрическим изображением системы ограничений является многоугольник ABCDE. Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c₁x₁+c₂x₂+с₀ принимает максимальное (или минимальное) значение. Рассмотрим линии уровня функции F или

c₁x₁+c₂x₂=С ( 3.5).

Это уравнение прямой. Линии уровня функции F параллельны, т.к. их угловые коэффициенты определяются только соотношением между коэффициентами c₁ и c₂ и, следовательно, равны. Т.о., линии уровня функции F - это своеобразные «параллели», расположенные обычно под углом к осям координат.

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

Геометрическим изображением системы ограничений может служить и многоугольная область. Рассмотрим следующую задачу.

1.В суточный рацион включают два продукта питания П₁ и П₂, причём продукта П₁ должно войти в дневной рацион не более 200 ед. Стоимость питательных веществ в 1 ед. продукта, минимальные нормы потребления указаны в таблице. Определить оптимальный рацион питания, стоимость которого будет наименьшей.

Питательные вещества	Минимальная норма потребления	Содержание питательных веществ в 1 ед. продукта.
		П1	П1
А В	120 160	0,2 0,4	0,2 0,2

Решение.

Обозначим х₁ - количество продукта питания П₁,

х₂ - количество продукта питания П₂.

F=2 х₁ +4 х₂ >min. (суммарная стоимость) При ограничениях

х₁ ? 200,

0,2 х₁ +0,2 х₂ ?120,

0,4 х₁ +0,2 х₂ ?160.

Графическим решением системы ограничений является множество точек плоскости, называемое областью допустимых решений (ОДР). Линии уровня 2х₁+4х₂=0 х₂=-х_1.

Получаем, что минимальное значение, при заданных ограничениях на переменные, достигается в точке А(200;400). F(A)=2000.

Ответ: наименьшая стоимость 2000 будет при рационе 200 ед. продукта П₁ и 400 ед. продукта П₂.

Не всегда бывает единственное оптимальное решение. Рассмотрим другую задачу.

2. F=4x₁+4x₂ >max. При ограничениях

2x₁+x₂ ?7,

x₁-2x₂ ?-5,

x₁+x₂?14,

2x₁-x₂ ?18.

Решив, систему ограничений найдём ОДР. Линия уровня будет иметь вид 4x₁+4x₂=0 x₂=-x₁.

В данной задаче линия уровня с максимальным уровнем совпадает с граничной линией многоугольника решений. Найдём точку пересечения линии II с линией III:

х₁=.

Найдём точку пересечения линии III с линией IV: 14- х₁=2 х₁-18. Отсюда х₁= . Следовательно, х₁=c, x₂=14-c, c[;]. Пусть х₁=9 [;], х₂=5.

F=4·9+4·5=56.

Ответ: F_max=56 при множестве оптимальных решений х₁=c, x₂=14-c, где c[;].

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

Однако есть и недостатки. Возникают «технические» погрешности, которые неизбежно возникают при приближенном построении графиков. Второй недостаток геометрического метода заключается в том, что многие величины, имеющие чёткий экономический смысл (например, такие, как остатки ресурсов производства), не выявляются при геометрическом решении задач. Его можно применять только в том случае, когда число переменных в стандартной задаче равно двум. Поэтому необходимы аналитические методы, позволяющие решать ЗЛП с любым числом переменных и выявить экономический смысл, входящих в них величин.

Одним их таких методов является симплексный метод.

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

Пусть ОДР изображается многоугольником ABCDEGH. Предположим,

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

Идея последовательного улучшения решения легла в основу универсального метода решения ЗЛП - симплексного метода. Для использования симплексного метода ЗЛП должна быть приведена к каноническому виду. Для реализации симплексного метода необходимо освоить 3 основных элемента:

· способ определения какого - либо первоначального допустимого решения

· правило перехода к лучшему решению

· критерий проверки оптимальности найденного решения.

Алгоритм конкретной реализации этих элементов рассмотрим на примере.

Практические расчёты при решении реальных задач симплексным методом выполняются в настоящее время с помощью компьютера, однако, если расчёты выполняются без ЭВМ, то удобно использовать симплексные таблицы.

Алгоритм составления симплексных таблиц:

1. Система ограничений приводится к каноническому виду.

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

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

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

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

· ?, если b_i и а_is имеют разные знаки;

· ?, если b_i=0 и а_is<0;

· ?, если а_is=0;

· 0, если b_i=0 и а_is>0;

· , если b_i и а_is имеют одинаковые знаки.

Определяют min . Если конечного минимума нет, то задача не имеет конечного оптимума. Далее выбирают строку с номером q, на которой он достигается (любую, если их несколько), и называют её разрешающей строкой. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент а_qs.

5. Переходим к следующей таблице по правилам:

а) в левом столбце записывают новый базис: вместо основной переменной х_q - переменную х_s, а геометрически произойдёт переход к соседней вершине многоугольника, где значение линейной функции «лучше». Значение линейной функции увеличится, т.к. переменная, входящая в выражение функции, станет основной, т.е. будет принимать не нулевое, а положительное значение;

b) новую строку с номером q получают из старой делением на разрешающий элемент а_qs;

c) все остальные элементы вычисляют по правилу многоугольника:

;

Далее переходим к пункту 3 алгоритма.

Замечание: при отыскании минимума функции Z, полагаем, что F=-Z и учитываем, что Z_min=-F_max.

Решим задачу симплексным методом.

Для производства трёх изделий А,В и С используются три вида ресурсов. Каждый из них используется в объёме, не превышающем 180, 210 и 236 кг. Нормы затрат каждого из видов ресурсов на одно изделие и цена единицы изделий приведены в таблице.

Вид ресурса	Нормы затрат ресурсов на 1 изделие, кг
	А	В	С
1 2 3	4 3 1	2 1 2	1 3 5
Цена изделия, у.е.	10	14	12

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

Решение. х₁- количество выпускаемых изделий А

х₂- количество выпускаемых изделий В

х₃- количество выпускаемых изделий С.

Тогда целевая функция будет иметь вид: F=10x₁+14x₂+12 х₃ >max

при ограничениях: 4x₁+2x₂+х₃?180

3x₁+x₂+3х₃?210

x₁+2x₂+5х₃?236

Приведём систему к каноническому виду:

4x₁+2x₂+х₃+х₄=180

3x₁+x₂+3х₃+х₅=210

x₁+2x₂+5х₃+х₆=236.

Составляем таблицу

	х1	х2	х3	х4	х5	х6	Свободный член
х4 х5 х6	4 3 1	2 1 2	1 3 5	1 0 0	0 1 0	0 0 1	180 210 236
F'	-10	-14	-12	0	0	0	0

Определим ведущий элемент: min. Далее выполняем действия, следуя алгоритму.

	х1	х2	х3	х4	х5	х6	Свободный член
х2 х5 х6	2 1 -3	1 0 0	1/2 5/2 4	1/2 -1/2 -1	0 1 0	0 0 1	90 120 56
F'	18	0	-5	7	0	0	1260

min

	х1	х2	х3	х4	х5	х6	Свободный член
х2 х5 х3	19/8 23/8 -3/4	1 0 0	0 0 1	5/8 1/8 -1/4	0 1 0	-1/8 -5/8 1/4	83 85 14
F'	54/4	0	0	23/4	0	5/4	1330

Ответ: Чтобы получить оптимальный доход, нужно выпускать 83 ед. изделия В, 14 ед. изделия С, а изделие А не выпускать. Оптимальный доход составит 1330 у.е. По решению задачи видим, что у предприятия остаются свободными 85 кг. второго вида ресурсов, 1 и 3 вид полностью расходуются [5]

3) Двойственная задача.

Каждой задаче линейного программирования соответствует другая задача, называемая двойственной или сопряжённой по отношению к исходной. Теория двойственности полезна для проведения качественных исследований ЗЛП. В главе I пункте 2) рассмотрена задача об использовании ресурсов. Предположим, что некоторая организация решила закупить ресурсы и необходимо установить оптимальные цены на эти ресурсы y_1,y₂,y₃. Очевидно, что

покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z в количествах 180, 210, 236 по ценам соответственно y_1,y₂,y₃ были минимальными, т.е. Z= 180y₁+210y₂+236y₃>min. С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не мене той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. На изготовление единицы продукции А расходуется 4кг. ресурса 1, 3кг. ресурса 2, 1кг. ресурса 3 по цене соответственно y_1,y₂,y₃. Поэтому, для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении единицы продукции, должны быть не менее её цены 10у.е., т.е. 4 y₁+3 y₂+ y₃?10.

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

Задача I (исходная)	Задача II (двойственная)
F= 10x1+14x2+12x3>max При ограничениях: 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 При ограничениях: 4y1+3y2+y3?10 2y1+y2+2y3?14 y1+3y2+5y3?12 и условие неотрицательности переменных y1?0, у2?0, у3?0. Найти такой набор цен ресурсов, при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли от реализации этой продукции.

Обе задачи, представленные в таблице обладают следующими свойствами:

1. В одной задаче ищут максимум линейной функции, в другой минимум.

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

3. Каждая из задач задана в стандартной форме, причём в задаче максимизации - все неравенства вида «?», а в задаче минимизации - все неравенства вида «?».

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

Для задачи I А=, для задачи II А=

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

6. Условия неотрицательности переменных имеются в обеих задачах.

Две задачи I и II линейного программирования, обладающие указанными свойствами, называются симметричными взаимодвойственными задачами.

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

1. Приводят все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задач ищут максимум линейной функции, то все неравенства системы ограничений приводят к виду «?», а если минимум - к виду «?».

2. Составляют расширенную матрицу системы А₁, в которую включают матрицу коэффициентов при переменных, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.

3. Находят матрицу А, транспонированную к матрице А₁.

4. Формулируют двойственную задачу на основании полученной матрицы Аи условия неотрицательности переменных.

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

Основное неравенство теории двойственности. Пусть имеется пара двойственных задач I и II. Покажем, что для любых допустимых решений Х= (x₁,x_2, …,х_n) и У=(y_1,y₂,…,y_m)исходной и двойственной задачи справедливо неравенство F(X) ? Z(Y) или ? (3.6)

? Возьмём неравенства системы ограничений исходной задачи ?b_i и умножим соответственно на переменные y_1,y₂,…,y_m и, сложив правые и левые части полученных неравенств, имеем

?. (3.7)

Аналогично умножаем систему ограничений двойственной задачи на переменные x₁,x_2, …,х_n , получим

? (3.8)

Т.к. левые части неравенств (3.7) и (3.8) представляют одно и тоже выражение у_j, то в силу транзитивности неравенств получим доказываемое неравенство (3.6).¦

Теперь докажем признак оптимальности решений.

Достаточный признак оптимальности.

Если X^*=(x, x,…, x) и У^*=(у, у,…, у) - допустимые решения взаимно двойственных задач, для которых выполняется равенство