29. Задачи линейного программирования. Экономический анализ задач с использованием теории двойственности.

ЗЛП имеет вид 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= .

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

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

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

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 ед. продукта, минимальные нормы потребления указаны в таблице. Определить оптимальный рацион питания, стоимость которого будет наименьшей.

Решение.

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

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

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, а геометрически произойдёт переход к соседней вершине многоугольника, где значение линейной функции «лучше». Значение линейной функции увеличится, т.к. переменная, входящая в выражение функции, станет основной, т.е. будет принимать не нулевое, а положительное значение;

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

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

;

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

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

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

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

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

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

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

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

Тогда целевая функция будет иметь вид: 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.

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

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

min

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