Некоторые задачи оптимизации в экономике (стр. 4 из 12)
Обозначим х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.
Графическим решением системы ограничений является множество точек плоскости, называемое областью допустимых решений (ОДР). Линии уровня 2х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 |
Определить план выпуска изделий, обеспечивающий получение оптимального дохода.