Дипломная работа: Некоторые задачи оптимизации в экономике

Стандартную задачу можно привести к каноническому виду, путём введения дополнительных неотрицательных переменных. Т.е. свести к системе 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 ₂ +…+р _n x_n =р. Х≥0 .

р₁ = р₂ = … р_n =.

Для того чтобы рассмотреть теоретические основы метода линейного программирования, определим понятие выпуклого множества точек, дав ему определение в аналитической форме:

Множество точек является выпуклым, если оно вместе с любыми своими двумя точками содержит их произвольную линейную комбинацию. Точка Х является выпуклой линейной комбинацией точек Х₁ , Х₂ , … Х _n ,если выполняются условия Х= α ₁ x ₁ + α ₂ x ₂ +…+ α_n x_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 (Х₂ )+…+ α_q F (Х _q )= α ₁ M + α ₂ M +…+ α_q M = M = M , т.е. линейная функция F принимает максимальное значение в произвольной точке Х , являющейся выпуклой линейной комбинацией угловых точек Х₁ , Х₂ , … Х _q ■

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

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

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

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

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

F=c₁ x₁ +c₂ x₂ + с ₀ →min(max) ,

При ограничениях а₁₁ х₁ + а₁₂ х₂ ≤ b ₁ ,

а₂₁ х₁ + а₂₂ х₂ ≤ b ₂ ,