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

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 основных элемента:

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

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

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

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

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

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