Xreferat.com » Рефераты по экономико-математическому моделированию » Некоторые задачи оптимизации в экономике

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

height="24" />,…, у) и возместить от продажи равные ей минимальные затраты на ресурсы Zmin.

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

Пусть даны две взаимно двойственные задачи I и II. Если каждую из них решать симплексным методом, то необходимо привести их к каноническому виду, для чего в систему ограничений задачи I следует ввести m неотрицательных переменных xn+1, xn+2, … , xn+m, а в систему ограничений задачи II  - n неотрицательных переменных ym+1, ym+2,…,ym+n. Системы ограничений двойственных задач примут вид:  

+xn+i=bi, i=1,…,m (3.11)                      -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: если >0, то =0; если >0, то=0, и аналогично, если >0, то =0; если >0, то=0.

□ Выразим дополнительные переменные из системы ограничений (3.11) исходной задачи I и (3.12) двойственной задачи, представленных в каноническом виде:

xn+i=bi-, i=1,2,…,m                                  (3.13)

ym+j=-cj, j=1,…,n.                                (3.14)

Умножая каждое равенство системы (4.9) на соответствующие переменные уj≥0 и складывая полученные равенства, найдём

xn+iyi=biyi-yi                            (3.15)

Аналогично, умножая каждое неравенство системы (4.10) на соответствующие переменные xj≥0 и складывая полученные равенства, найдём

ym+j=yi-cj .                                          (3.16)

Равенства (4.11)и(4.12) будут справедливы для любых допустимых значений переменных, в том числе и для оптимальных значений ,,, . В силу первой теоремы двойственности (3.10) F(X*) =Z(Y*) или =, поэтому из записи правых частей равенств (3.15) и (3.16) следует, что они должны отличаться только знаком. С другой стороны, из неотрицательности выражений xn+i yi и ym+j, входящие в выражения (3.15) и (3.16), следует, что правые части этих равенств должны быть неотрицательны.

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

=0,

=0.                                          (3.17)

В силу условия неотрицательности переменных каждое из слагаемых в равенстве (4.13) должно равняться нулю:

=0,  i=1,2,…,m

=0,  j=1,2,…,n

Откуда и вытекает заключение теоремы. ■

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

Рассмотренная теорема является следствием следующей теоремы.

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

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

С помощью теорем двойственности найдём решение задачи II. Получаем следующий набор цен ресурсов (  ),  при котором минимальные затраты составят 1330.                                                                                                 [5]

4) Задача нелинейного программирования. (ЗНП)

Рассмотрим ЗНП и способы её решения. Математическая модель ЗНП в общем виде формулируется следующим образом:

f =(x1,x2, …,хn) → min (max). При этом переменные должны удовлетворять ограничениям:

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 нелинейная.

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

Рассмотрим основные идеи графического метода.

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

Рассмотрим на примерах решение ЗНП.

1. Найти экстремумы функции L(x1,x2)=x1+2x2 при ограничениях

, .

5

 
Решение. ОДР – это часть круга с радиусом 5, расположенная в I четверти. Найдём линии уровня функции L: x1+2x2=C. Выразим x2=. Линиями уровня будут параллельные прямые с угловым коэффициентом, равным -. Минимум функции достигается в точке (0;0), Lmin=0, т.к. градиент (1,2) направлен вверх вправо. Максимум достигается в точке касания  кривой х2= и линии уровня. Т.к. угловой коэффициент касательной к графику функции равен -, найдём координаты точки касания, используя геометрический смысл производной.

=-; ()=-;

=-; x0=; x2=2.

Тогда L=+2∙2=5.

Ответ: Минимум достигается в точке О(0;0), глобальный максимум, равный 5, в точке А(;2) .

2. Найти экстремумы функции L=(x1-6)2+(x2-2)2 при ограничениях    

                   

                    x1+x2≤8

                    3 x1+x2 ≤15

                    x1+x2 ≥1  

                   .

Решение.  ОДР – многоугольник 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, то угловой коэффициент перпендикуляра равен . Из уравнения прямой, проходящей через данную точку О1 с угловым коэффициентом , получим (x2-2)= (x1-6). Найдём координаты точки Е

х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

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

Решение: ОДР является часть круга, с центром в начале координат,  с радиусом 5, расположенная в I четверти. Линии уровня – это окружности с центром в точке О1 и радиуса С, т.к. (x1-1)2+(x2-3)2. Точка О1 – это вырожденная линия уровня, соответствующая минимальному значению С=0. глобальный максимум достигается в точке А, лежащей на пересечении ОДР с линией уровня наибольшего радиуса. При этом

L(A)=(5-1)2+(0-3)2=25.

Ответ: Минимум, равный 0, достигается в точке (1;3),

              Максимум, равный 25, - в точке А(5;0).

4. Предприниматель решил выделить на расширение своего дела 150 тыс.руб. известно, что если на приобретение нового оборудования затратить х тыс. руб., а на зарплату вновь принятых работников у тыс. руб., то прирост объёма продукции составит Q=0.001x0.6·y0.4 . Как следует распределить выделенные денежные ресурсы, чтобы прирост объёма продукции был максимальным.

  Решение: Целевая функция имеет вид 0.001x0.6·y0.4max при ограничениях   x+y≤150,

   .

ОДР – треугольник. Линии уровня будут иметь вид 0.001x0.6·y0.4. Выразив отсюда у, получим у=. Т.к. максимум достигается в точке касания линии уровня с ОДР, то  условие касания имеет вид =-1. Найдя производную, получаем =-1. Выразив х, получим х=. у==.

Ответ: Факторы х и у следует распределить в отношении 2:3.

5.Предприятие выпускает изделия А и Б, при изготовлении которых используется сырьё S1 и S2. Известны запасы bi (i=1,2) сырья, нормы его расхода на единицу изделия aij (j=1,2), оптовые цены pj на изделия и их плановая себестоимость с. Как только объём выпускаемой продукции перестаёт соответствовать оптимальному размеру предприятия, дальнейшее увеличение выпуска хj ведёт к повышению себестоимости продукции b, в первом приближении фактическая себестоимость сj описывается функцией сj= с+ схj, где сj – некоторая постоянная. Все числовые данные приведены в таблице

b1    

b2

a11

a12

a21

a22

p1

p2

с

с

с

с

90 88 13 6 8 11 12
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: