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

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

F принимает максимальное значение в произвольной точке Х, являющейся выпуклой линейной комбинацией угловых точек Х1, Х2, … Хq ■   

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

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

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

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

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

F=c1x1+c2x2+с0 →min(max),

При ограничениях    а11х1+ а12х2b1,

                                    а21х1+ а22х2b2,

                                     ………………

                                     an1х1+ аn2х2bn  ,

при условии, что x1 ≥0  ,x2 ≥0 .

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

c1x1+c2x2                                             ( 3.5).

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

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

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

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

Питательные

вещества

Минимальная норма

потребления

Содержание питательных

 веществ в 1 ед. продукта.

П1

П1

А

В

120

160

0,2

0,4

0,2

0,2

 Решение.

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

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

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

  х1 ≤ 200,

  0,2 х1 +0,2 х2 ≥120,

 0,4 х1 +0,2 х2 ≥160.

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

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

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

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

2. F=4x1+4x2 max. При ограничениях

   2x1+x2 ≥7,

   x1-2x2 ≥-5,

   x1+x2≤14,

  2x1-x2 ≤18.

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

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

х1=.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

·        ∞, если bi и аis имеют разные знаки;

·        ∞, если bi=0 и аis<0;

·        ∞, если аis=0;

·         0, если bi=0 и аis>0;

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

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

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

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

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

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

;

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

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

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

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

Вид ресурса

Нормы затрат ресурсов на 1 изделие, кг

А

В

С

1

2

3

4

3

1

2

1

2

1

3

5

Цена изделия, у.е.

10

14

12

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

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

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

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

Тогда целевая функция будет иметь вид: F=10x1+14x2+12 х3max

при ограничениях:          4x1+2x23≤180

                                         3x1+x2+3х3≤210

                                         x1+2x2+5х3≤236

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

4x1+2x234=180

                                         3x1+x2+3х35=210

                                       x1+2x2+5х36=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
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

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

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

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