45 Графический метод решения злп

Применяется для решения задач малой размерности, когда число перем. n≤ 3.

Описание графич. метода:

Ш1: графич. способом строится обл. огр. D исходной задачи.

Ш2: строится направляющий вектор: с=f(x),

Ш3: через любую точку области D проводится плоскость(прямая), ортогональная вектору .

Ш4: построенная плоскость (прямая) перемещается в направлении вектора C параллельно самой себе до точки последнего соприкосновения перемещаемой плоскости (прямой) с областью D. Точка отрыва определяет оптимальный план задачи.

Ш5: путём анализа выясняется, результатом пересечения каких плоскостей (прямых) является найденная точка отрыва. Выписывается СЛУ прямых, породивших оптим. план. СЛУ решается, её решение даёт точные значения компонент оптим. плана.

46 Назначение и обоснование см

СМ предназначен для решения ЗЛП в канонической форме:

f(x)=c^tx→max (1)

Aх=b (2)

х ≥0

В основе метода лежат теорема о решении ЗЛП и теорема о вершине.

СМ состоит в процедуре последующего перехода от одной вершины обл-ти огр-ний исходной з-чи к другой, на кот-ой знач-е цел-ой ф- ии f(x) больше, чем на предыдущей. Поскольку число вершин любого выпуклого многогр-ка конечны, то СМ за конечное число шагов приводит либо к опт-му плану, либо устанавливает неразрешимость исходной за-чи (когда обл-ть огр-ний пуста или не огр-на).

Процедура перехода от вершины к вер-не основана на алгебре СМ.

47 Алгебра см

f(x)=c^tx→max (1)

Aх=b (2)

х ≥0

Ш1 (поиск 1-го опорного плана):

Опорный план задачи (1)-(2) может быть найден путем решения СЛУ Ax=b ограничений (2).методом Гаусса с последующим присвоением всем своб.переменным нулевых значений. Без ограничения общности можно считать, что базисными переменными будут первые m переменных общности. Их можно переименовать, которые могут быть выражены через свободные след.обр.:

x_i=β_i-Σ_j=m+1ⁿ α_ijx_j , i=1,m (3)

Все β_i в (3) должны быть неотрицательными. Если это не так, то СЛУ перерешивается методом Гаусса относительно др. базисных перем., до тех пор, пока все β_i станут неотрицат. Согласно теореме о вершине, точка x^t(1)=( β₁, β₂,…, β_m, 0,…,0) является вершиной, т. к. все своб. перемен. равны 0.

Ш2 (выражение эл-тов текущей задачи через своб. перем.):

Подставляя (3) в выражение (1) получаем:

f(х)= c^tx =Σ_i=1ⁿ c_ix_i=Σ_i=1^m c_ix_i + Σ_j=m+1ⁿ c_ix_j= Σ_i=1^m c_i(β_i- Σ_j=m+1ⁿ α_ijx_j) + Σ_j=m+1ⁿ c_jx_j= f₀- Σ_j=m+1ⁿ Δ_jx_j (4)где

f₀= Σ_i=1^m c_i β_i= С^т_бР₀ (5)

Δ_j=Σ_i=1^m c_iα_ij – c_j= С^т_бР_j – c_j, j = m+1,n (6)

где P₀^т=(β₁, β₂, ..., β_m) – вектор правой части ф-и СЛУ, дающей решение (3),

P_j^т=(α_1j, α_2j, …, α_mj) – j-тый столбец м-цы этой системы

СЛУ, к кот. привёл метод Гаусса на 1-м шаге.

С_б^т=(с₁, с₂, …, с_m) – вектор, состоящ. из коэф-тов при базисных переменных в целевой функции (1).

α – элементы матрицы финальной СЛУ.

Исходная задача принимает вид:

f(x)=f₀-Σ_j=m+1ⁿ Δ_jx_j → max (7)

x_i= β_i- Σ_j=m+1ⁿ α_ijxj>=0, i=1,m

x_j>=0, j=m+1,n (8)

1-ое нер-во в (8) –следствие изнач.-го требования неотрицательности всех переменных,в т.ч. и базисных.Константа f0 в (7) не зависит не от каких перемен. Знач.целевой ф-и на 1-ом опорном плане ,что следует из (7) после обнуления всех своб.переменных:

f(x(1))=f₀= С^т_бР₀ (9)

Ш 3 (поиск возможных переходов):

Найти вершину D, на кот. значение целев. ф-ции > чем на x(1)

а) Все Δ_j в (4) не меньше 0. В этом случаеx(1). является

оптим. планом, поскольку любые изменения своб. переменных не увеличивают значение целевой ф-ции.

б) Существует хотя бы одно k, что Δ_k<0. Тогда значение целев. ф-ции можно увеличить за счёт своб. переменной х_k, изначально равной 0.

Ш 4 (переход к новой вершине):

Увеличим до предела переменную х_k , оставляя все другие своб. перем. равными 0. Предел увеличения устанавливается из условия неотрицательности всех баз. перем. , кот., как следует из (3) будут изменятся по закону: x_i = β_i - α_ikx_k

Условие неотрицательности даёт: x_i = β_i - α_ikx_k ≥ 0, i = 1,m (10)

Возможны варианты:

а) Все α_ik ≤ 0. В этом случае все нерав-ва (10) остаются справедливыми при сколь угодно больших значениях x_k. В результате целевая ф-я может быть ув-на до люб.сколь угодно большего числа и решения нет,т.к. она не ограничена.

б) Одно или несколько α_ik > 0. Тогда каждая α_ik порождает верхнюю границу γ_i для увеличения переменной :

x_k ≤ β_i / α_ik = γ_i (11)

Пусть этот min γ достигается при i=r: γ=γ_r – β_r / α_rk

Увеличим x_k до предела, оставляя при этом все другие своб. переменные равными 0. По достижении верхней границы, перем x_k обнуляет базис. перем. x_r , кот. объявляется свободной, x_k объявляется базисной. Тогда точка:

х^т(2)=( β₁, …, β_r-1, 0, β_r+1, …, β_m, 0, 0, …, γ_k, 0 )

является вершиной области ограничения задачи. Далее переход на шаг 2.

Замечание 1: шаг 4 равносилен перерешиванию сис-мы уравнений-ограничений методом Гаусса, при этом в качестве разрешающ. эл-та будет элемент м-цы системы α_rk

Замечание 2: для задачи поиска минимума достаточно найти max этой ф-ции, взятый с обратным знаком.

48 С-Т. Правила построения и заполнения С-Т

С-Т предназн. для облегчения реализации СМ вручную. Решается задача:

f(x)=c^tx→max (1)

Ax=b (2)

x≥0

Ax=b – система m уравнений с n неизвестными, кот. можно представить в векторной форме записи:

f=c^тx → max (3)

Σ_j=1ⁿ x_jP_j = P₀ (4)

x≥0

где x_j – аргументы целевой ф-ции,

P_j^т = (a_1j, …, a_mj) – j-тый столбец м-цы системы А СЛУ-ограничений Ax=b. P₀=b

С-Т содержит инф. о текущем состоянии процесса решения задачи СМ-ом и о возможных вариантах перехода к следующ. вершине. Каждой вершине, через кот. СМ достигает оптим. плана, соотв. своя С-Т. Если СЛУ-ограничений решена и базисными перем. оказались x_i1, …, x_im, то это озн., что соотв. вектора P_i1, …, P_im в (4) являются единичными векторами, образующими канонический базис в пространстве R^m. Если компоненты вектора P₀ неотриц., то вектор х, в кот. все свободные перем. =0 определяет опорный план, т. е. все условия шага 1 алгебры СМ выполнены и для реализации СМ табл. способом необходимо заполнить С-Т.

В 1-м столбце С-Т содержатся наименов. базисн. перем. в текущий момент и наименов. целев. ф-ции f. Во 2-м столбце– компоненты векторы с_б^т = (c_i1, …, c_im)

3-й столбецbсодержит компоненты вектора Р₀, а нижняя клетка столбца – значение f₀=c_б^тP₀ в текущ. вершине.

4-й и последующ. столбцы содержат компоненты вектора P_j, j=1,n. А нижние клетки столбцов – значения

Δ_j=c_б^тP_j – c_j , j=1,n