39 Достат-ть усл-й к-т

Тип оптим-ции

Целевая ф-ия

Область опр-й

Мах-ция

Вогнутая

Выпуклое множ-во

Min-ция

Выпуклая

Выпуклое множ-во

44 Графический метод решения ЗЛП

Применяется для решения задач малой размерности, когда число перем. ≤ 3. в основе метода лежит факт, что град. ф-ции ортогонален гиперплоскости во всех точках, в кот. целев. ф-ция принимает одинаков. значения.

П_β = xЄRⁿ : f(x) = c^тx=β

Направленный отрезок zЄП_β. z ортогонален грандиенту целев. ф-ции:

grad^тf(x)=c, z=y-x

(grad f, z) = (c, y-x) = (c, y) – (c, x) =

c^тy – c^тx = f(y) – f(x) = β – β = 0

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

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

Шаг 2: строится вектор с, компонентами кот. служат коэф-ты при перем. в выражении целев. ф-ции.

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

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

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

42 Понятие угловой точки выпуклого многогранника, опорного плана ЗЛП. Понятие оптимального плана ЗЛП.Вырожденный и невырожденный опорный план.

Опред: т. xЄD области ограничения ЗЛП называется угловой точкой(вершиной), если не существует отрезка, принадлежащего D для кот. т. x является внутренней точкой. Т. x назыв-ся внутренней точкой отрезка z y, если справедливо:

x=λz+(1-λ)y, 0<λ<1

Опред: Опорным планом назыв-ся любая вершина обл. определений ЗЛП. Опорный план назыв-ся невырожденным если он содержит ровно m (число ограничений) положит. компонент. В противном случае он называетсяся вырожденным.

47 Алгебра СМ

Шаг 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.

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

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

f(x)=c^т=Σ_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_ix_i=f₀- Σ_j=m+1ⁿ Δ_jx_j где

f₀= Σ_i=1^m c_i β_i=c_б^tP₀ (5)

Δ_j=Σ_i=1^m c_iα_ij – c_j=c_б^tP_j – c_j , j = m+1,n (6)

где P₀^т=β₁, β₂, ..., β_m) – вектор правой части,

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

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

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

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

Исходная задача принимает вид: f(x)=f₀-Σ_j=m+1ⁿ Δ_jx_j → max (7)

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

Найти вершину D, на кот. значение целев. ф-ции > чем на х⁽¹⁾:

а) Все Δ_j в (7) не меньше 0. В этом случае т. х⁽¹⁾ является

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

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

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

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

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

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

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

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

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

Пусть этот 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 этой ф-ции, взятый с обратным знаком.

41 Общая постановка ЗЛП и формы её представления

ЗЛП называется оптимиз. задача f(x) → max (min) (xЄDcRⁿ), где

f(x)=c^tx=Σ_j=1ⁿ c_jx_j – линейная целевая функция, а D выпуклый многогранник. Формы представления:

1. ЗЛП в канонической форме (с ограничениями равенствами)

f(x) → max (min)

x≥0

Ax=b

2. ЗЛП в симметрич. форме (с ограничениями неравенствами)

f(x) → max (min)

Ax≤b

x≥0

3. ЗЛП в общей форме ( со смешан. ограничениями)

f(x) → max (min)

A₁x=b₁

A₂x≤b₂

Замечание: 1-я и 2-я формы задач ЗЛП содержат требование неотрицательности инструм. переменных x≥0. Общая форма задачи этого не требует.

Канонич, симметрич и общая форма представления ЗЛП эквивалентны в том смысле , что любая исходн. ЗЛП м.б. представлена в любой из перечисленных форм и её решение не зависит от форм представления.

43 Понятие крайней точки области ограничений ЗЛП. Теорема Каратеодори. Теорема о решении ЗЛП. Теорема о вершине

Опред: т. xЄD области ограничения ЗЛП называется угловой точкой(вершиной), если не существует отрезка, принадлежащего D для кот. т. x является внутренней точкой. Т. x назыв-ся внутренней точкой отрезка z y, если справедливо:

x=λz+(1-λ)y, 0<λ<1

Теорема Каратеодори:

Пусть x(1), x(2),…,x(N) – вершины выпуклого многогранника D, тогда любая т. xЄD этого многогранника может быть представлена в виде выпуклой линейной комбинации его вершин

x=Σ_j=1^N λ_jx(j), где Σ_j=1^N λ_j=1, λ_j≥0, j=1,N

Теорема о решении ЗЛП:

Пусть D есть обл. ограничений ЗЛП, тогда справедливо следующее:

1. Максимум(минимум) целевой функции достигается в вершине области D.

2. Если максимум(минимум) целевой функции достигается сразу в нескольких вершинах, то такое же значение целевая функция принимает на любой выпуклой линейной комбинации этих вершин. Теорема о вершине:

Для того, чтобы т. x была вершиной обл. ограничений задачи 1-2, необходимо и достаточно чтобы она была решением СЛУ Ax=b, заданной в (2), в кот. все свободные переменные =0, а базисные неотрицательны.

Следствие:

Число положит. компонент вершины обл. ограничений задачи 1-2 не может быть >m, где m число уравнений в системе Ax=b.

Опред: Опорным планом назыв-ся любая вершина обл. определений ЗЛП. Опорный план назыв-ся невырожденным если он содержит ровно m (число ограничений) положит. компонент. В противном случае он называетсяся вырожденным.

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

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

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

48 Правила пересчёта С-Т

1) Поиск возможных переходов. Рассмотрим посл. строку табл:

а) В строке нет отрицат. чисел, кроме f₀. Задача решена, значения оптим. плана содержатся в столбце Р₀.

б) Среди всех Δ_j есть отриц. Выбираем любое из них Δ_k<0. Соотв. столбец Р_k объявляется разрешающим.

2) Определение путей перехода. Рассм. эл-ты разрешающего столбца:

а) Все эл-ты столбца не положительны. Решения нет. Целев. ф-ция неограниченна сверху.

б) Среди эл-тов столбца есть положительные a_ik>0. Для каждого находим значение γ_i = b_i/a_ik , как отношение соотв. компонент столбцов Р₀ и Р_j. Среди всех γ_i выбираем миним. Пусть минимум достигается при i = r, тогда соотв. эл-т разрешающего столбца a_rk объявляется разрешающим, а строка, его содержащая - разрешающей. если минимум достигается сразу для неск. эл-тов, то разрешающим выбирается любой.

3) Переход к новой вершине. Заполняется новая таблица. На месте эл-тов разрешающей строки в новой табл. записываются эл-ты старой, поделённые на разрешающий эл-т. На месте разреш. столбца в новой табл. записывается единичный вектор, с единицей на месте разрешающего эл-та. Остальные эл-ты табл. включая послед. строку пересчитываются также, как при реализации метода исключения Гаусса.

30 Постановка ЗНЛП с ограничениями-равенствами

F(x)→max(min) (1) F(x)→max(min) (3)

g1(x)=b1 g(x)=b (4)

……….. (2) или

gm(x)=bm

здесь b=(b1 b2….dm)-заданный вектор правой части ограничений.g(x)=(g1(x) g2(x) …..gm(x))-вектор-функция ограничений задачи (3)-(4).

49 МИБ. Теорема о решениях..

Реализация СМ требует наличия опорного плана. Его можно получить, решив методом Гаусса СЛУ-ограничений исходной задачи. Можно действовать иначе.

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

f=c^тx → max (3)

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

x≥0

Теорема о решениях

Для существования оптим. плана x*^т = (x₁*, …, x_n*) исходной задачи (3)-(4) необходимо и достаточно, чтобы в оптим. плане

X*^т = (x₁*, …, x_n*, 0, …, 0) все искусств. компоненты были бы равны 0.

50. Схема реализации М-метода

Шаг 1: В рассмотрение вводится m «искусственных» переем. x_n+1, …, x_n+m и формулируется расширенная ЗЛП:

F = Σ_i=1ⁿ c_i x_i – M Σ_j=n+1^n+m → max (5)

Σ_i=1ⁿ x_i P_i + Σ_j=n+1^n+m x_iP_i = P₀ (6)

x_k ≥ 0, k = 1, n+m

М – очень большое положит. число. М>>0 – штрафной множитель. P_j, j = n+1, n+m – единичный вектора, составляющие ИБ.

x^т(1) = (0, …, 0, b₁, …, b_m), в кот. все истинные перем. равны 0 являются точкой опорного плана расширенной задачи.

Шаг 2: сформированная задача (5)-(6) решается обычным СМ и оптим. план исходной задачи, если он существ., присутствует как составная часть в оптим. плане расширенной задачи.

51 С-Т для реализации МИБа

Для решения расширенной ЗЛП применяются таблицы, имеющие на 1 строку больше, чем обычные. Послед. строка обычной табл. как бы разбивается на 2. В предпослед. строку записывают составляющие f₀ и Δ_j, не зависящие от М, а в последнюю строку –

составляющие этих величин, зависящие от М или просто коэф-ты при М. Пересчёт эл-тов ведут сначала по последней строке. Выбираем в качестве разрешающих столбцы, соотв. наименьшему из чисел этой строки, до тех пор, пока: либо все искусств. перем. не будут исключены из базиса, либо последняя строка не будет содержать отрицат. эл-тов, кроме Р₀. Далее пересчёт ведут по предпослед. строке, убрав из рассмотрения все эл-ты табл., соотв. искусственным перем., покинувшим базис.

Замечание: Если исход. задача содержит несколько векторов P_j, то их следует включить в ИБ.

58 Двойственный СМ

Предназначен для решения ЗЛП в канонической форме. В его основе лежит процедура перехода от одной вершине к другой. В отличие от обычного СМ, в Двойственном СМ решение начинается с недопустимого (т.е. имеющего «отрицат.» компоненты) плана. Последовательные переходы приближают текущее решение к области допустимости без нарушения «оптимальности» промежуточных решений. В момент достижения обл. допустимых решений процесс вычислений заканчивается; последнее решение является допустимым и оптим. планом.

Реализация двойств. СМ с помощью таблицы требует, чтобы начальная табл. в базисном решении обязательно содержала отриц. перем., т. е. чтобы начальная вершина была бы недопустимой с т. зр. неотрицательности компонент. Переход к новой вершине производится в соотв. со следующ. условиями:

а) Двойственное условие допустимости:

В качестве исключаемой перем. х_i выбирается базисная перем., имеющая наибольшее по абс. величине отрицат. значение. Если их несколько, то выбор произволен. Если все базис. переменные неотрицат, процесс вычислений заканчивается.

б) Двойственное условие оптимальности:

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

min { среди всех своб. x_j } { |Δ_j / a_rj|, a_rj<0 }

где Δ_j = c_б P_j – c_j – эл-т j-го столбца нижней строки

a_rj – это эл-т, стоящий на пересечении разрешающей строки j-го столбца.

34 Метод подстановки в решении ЗНЛП с ограничениями-равенствами.

Метод предназначен для решения задачи вида

f(x)→max (min) (1)

xi=φi(xm=1, xm=2 … xn) i=1,n (2)

Метод состоит в подстановке выражений (2) на место аргументов целевой функции (1) с последующим решением классическим методом следущей задачи без ограничений

F(xm+1, ….., xn)→max(min), где f(xm+1, …, xn)=f(φ1(xm+1,…, xn),…..,φm(xm+1,…, xn), xm+1,xn)

После получения оптимального плана задачи (3) и искомых значений xm+1,…, xn . Обратной подстановкой получаем все искомые значения исходной задачи x1, ….,xm, доставляющие экстремальное значение целевой функции.

55 Теорема о представлении оптим. плана основной ЗЛП.

Пусть оптим. план x* основной задачи определяется базисными переменными x_i1, x_i2, …, x_im, тогда справедливо соотношение:

x*_баз = Ρ ^-1 Р₀, (1) где

х*^т_баз = (x*_i1, x*_i2, …, x*_im) – базисн. компоненты оптим. плана x*

Р = (P_i1, P_i2, …, P_in) – м-ца, составленная из векторов при базис. перем. в выражении Σ_j=1ⁿ x_j P_j = P₀, x≥0 (2)

Доказательство:

Собирая вместе все слагаемые левой части системы уравнений-ограничений (2), содержащие базисные перем. имеем:

Σ_j=1ⁿ x*_jP_j = x*_i1P_i1 + x*_i2P_i2 + … + x*_imP_im + Σ_{j≠i1, i2,.., im} x*_jP_j =

0

= (P_i1, P_i2, …, P_im)x*_баз = P x*_баз т.о.

Р x*_баз = P₀ => P ^-1P x*_баз = Р ^-1Р₀ , т. о. = Е

x*_баз = Р ^-1Р₀ , ЧТД.

56 Теорема о представлении оптим. плана двойственной ЗЛП

Если основная ЗЛП имеет оптим. план x*, то оптим. план двойственной задачи y* может быть определён по формуле:

y*^т = с_баз Р ^-1 (1), где

Р = (P_i1, P_i2, …, P_in) – м-ца, составленная из векторов при базис. перем. в выражении Σ_j=1ⁿ x_j P_j = P₀, x≥0

с^т_баз= (c_i1, c_i2, …, c_im) – вектор, состоящий из коэф-тов при базисных перем. целевой ф-ции основной задачи.

Доказательство:

В соответствии с 1-й теоремой двойственности f(x*) = g(y*)

f(x*) = c^т_баз x*_баз = (с^т_баз Р ^-1)Р₀ = g(y*) = y*^тР₀ => y*^т = c^т_баз Р ^-1, ЧТД.

Замечание 1: в том случае, когда решение прямой задачи находится с помощью С-Т, м-цы Р ^-1 образуют эл-ты тех векторов последней С-Т, которые в 1-й табл. были единичными (прямое следствие метода поиска обратной м-цы с помощью элемент. преобразований).

Замечание 2: Компоненты оптим. плана y*_I двойственной задачи можно найти по формуле

y*_I = Δ_i + c_i , где

Δ_i – значение эл-тов последней строки финальной С-Т тех векторов, которые в первой табл. были единичными.

52 Двойственные ЗЛП.

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

Прямая ЗЛП: Двойственная ЗЛП:

f(x) = c^тx → max(1) g(y) = b^тy → min

Ax ≤ b (2) A^тy ≥ c

x ≥ 0 y ≥ 0

c, x Є Rⁿ, b Є R^m b, y Є R^m, c Є Rⁿ

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

53 Двойственная лемма:

Для любого плана х прямой задачи, и любого плана y двойственной задачи справедливо:

f(x) ≤ g(y)

Следствие:

Если для некоторых планов x* и y* f(x*) = g(y*), то эти планы являются оптим. планами в своих задачах. Компоненты y*_i , i = 1, m оптим. плана двойственной задачи называются двойственными оценками.

54

1-я теорема двойственности:

Если одна задача двойств. пары имеет оптим. план, то и вторая тоже имеет оптим. план, причём значения целевых ф-ций этих задач на этих планах равны мужду собой. Если целевая ф-ция одной из задач двойствен. пары не ограничена, то множество допустимых решений второй задачи пусто, и наоборот.

2-я теорема двойственности:

План x* прямой задачи и план y* двойствен. задачи являются оптим. планами своих задач тогда и только тогда, когда выполняется соотношение:

(Σ_j=1ⁿa_ijx^*_j - b_j)y*_i = 0, i = 1, m

(Σ_i=1^ma_ijy*_i – c_j)x*_j = 0, j = 1, n

Следствие:

Если какая либо компонента оптим. плана одной из задач двойств. пары отлична от 0, то соотв. ограничение другой задачи должно выполнятся как строгое неравенство. Если же какое либо ограничение одной из задач выполняется как строгое неравенство, то соотв. компонента оптим. плана другой задачи этой пары равны 0.

3-я теорема двойственности

Пусть f٭=f(x٭)- значение целевой ф-ии прямой задачи 1 и 2 на оптимальном плане x٭,тогда двойственность можно найти по соотношениям:уi=df٭ dbi

i=1,m

bi-компоненты b прав части ограничений Ax≤b, заданных b

57 Экономическая интерпретация двойственных оценок

Согласно 1-й теореме двойственности значения целевых ф-ций прямой и двойств. ЗЛП равны между собой:

Σ_j=1ⁿc_jx*_j = f(x*) = g(y*) = Σ_i=1^mb_iy*_i

Пусть целевая ф-ция в прямой задаче выражает прибыль ($), а b_i – общее кол-во ресурса i-го вида, тогда y*_i должно выражаться в $ на единицу ресурса, выражая его цену. Поэтому двойственные оценки иногда называют «теневыми ценами». Они могут быть использованы для определения приоритета ресурсов в соотв. с их вкладом в величину целевой ф-ции. Они показывают, насколько изменяется max прибыль при изменении запаса соотв. ресурса на единицу. Для любых неоптим. планов x и y задачи двойтсв. пары справедливо:

f(x) < g(y)

В экон. интерпретации это означает: прибыль < общей ценности ресурсов.

До тех пор, пока неравенство строгое, решения не оптимальны, оптимум достигается, когда прибыль равна общей ценности ресурсов.

59 Устойчивость решений ЗЛП. Теорема об условиях устойчивости двойственных оценок.

Рассмотрим двойственную пару задач:

f(x) = c^тx → max g(y) = b^тy → min

Ax ≤ b A^тy ≥ c

x ≥ 0 y ≥ 0

x* и y* зависят от параметров этих задач, таких как c, b и A. При некоторых условиях оптим. плана x* и y* сохраняют свои значения неизменными при некоторых изменениях c, b и А. Говорят, что в этом случае они обладают устойчивостью к измененям параметров задач c, b и А.

Теорема об условиях устойчивости двойственных оценок:

Пусть b изменяется по схеме b = b + Δb

Условием устойчивости двойств. оценок является неизменность состава базисных перем. в оптим. плане прямой задачи, выражаемое, согласно теореме о представлении оптим. плана прямой задачи как:

x*_баз = Р ^-1(b + Δb) ≥ 0 (1)

При выполнении (1) согласно теореме о представлении оптим. плана двойств. задачи будут равны:

y*^т = c^т_баз Р ^-1 (2)

Если справедливо (1), то сотав базисных перем. оптим. плана x* не меняется. Вектор с_баз т.е. неизменными остаются компоненты оптим. плана y*.

При небольших изменениях правой части b ограничений прямой задачи, удовлетворяющих условию (1), справедливо:

f(x*(Δb)) = f(x*) + Σ_i=1^my*_iΔb_i (3), где

x* - оптим план основной задачи.

x*(Δb) – оптим. план задачи

f(x) = c^тx → max

Ax ≤ b + Δb

x ≥ 0

y*_i – двойственные оценки.

60

Теорема об условиях устойчивости прямых оценок

Условием устойчивости прямых оценок является условие (C^T_б+∆∙ C^T_б)∙ Р ^-1≥0

∆∙ C^T_б – метод приращения коэф при базисных переменных оптимального плана прямой З

61 Закрытая ТЗ..

Имеется m поставщиков A₁, A₂, …, A_m некоторого однородного груза с запасами a₁, a₂, …, a_m.

Имеется n потребителей B₁, B₂, …, B_n с потребностями b₁, b₂, …, b_n соответственно.

Известны так же тарифы перевозок: c_ij, i = 1, m , j = 1,n

означающие стоимость перевозок единицы груза от A_i к B_j. Требуется организовать перевозки так, чтобы:

1. Суммарная стоимость всех перевозок была бы минимальной.

2. Каждый поставщик полностью реализует свой запас.

3. Каждый потребитель полностью удовл. свои потребности.

Формализация задачи:

f = Σ_i=1^mΣ_j=1ⁿ c_ijx_ij → min (1)

Σ_i=1^m x_ij = b_j , j = 1, n

Σ_j=1ⁿ x_ij = a_i , i = 1, m (2)

x_ij ≥ 0

62 Теорема о разрешимости ТЗ:

Задача (1)-(2) имеет решение тогда и только тогда, когда выполнено уравнение баланса:

Σ_i=1^ma_i = Σ_j=1ⁿb_j (3)

Следствие:

Соотношение (3) означает, что уравнения системы ограничений (2) линейно зависимы. Всего уравнений в системе (2) n+m. Линейно независимых из них не более n+m-1.

63 Открытая ТЗ на недостаток..

Пусть в ТЗ нарушено арвнение баланса:

Σ_i=1^ma_i < Σ_j=1ⁿb_j

т.е. общие запасы < общих потребностей. Также заданы штрафные тарифы r_j, j = 1, n, означающие штрафы за непоставку единицы

груза j-му потребителю. Необходимо так спланировать перевозки, чтобы:

1. Суммарные транспортные и штрафные издержки были бы min.

2. Каждый поставщик реализует свой запас.

3. каждый потребитель получает товар не более, чем ему требуется.

65.Сведение ТЗ к закрытой.

Введём в рассмотрение фиктивного поставщика A_m+1 с фиктивными запасами равными:

a_m+1 = Σ_j=1ⁿb_j – Σ_i=1^ma_i

тарифы перевозок фиктивного груза установим равными штрафным тарифам за непоставку c_{m+1, j} = r_j , j = 1, n

Теперь открытая ТЗ может быть записана как закрытая ТЗ:

f = Σ_i=1^mΣ_j=1ⁿ c_ijx_ij + Σ_j=1ⁿx_{m+1, j}r_j = Σ_i=1^m+1Σ_j=1ⁿ c_ijx_ij → min

Σ_i=1^m+1 x_ij = b_j , j = 1, n

Σ_j=1ⁿ x_ij = a_i , i = 1, m+1 (2)

x_ij ≥ 0

Закрытая ТЗ является ЗЛП в канонической форме и поэтому может быть решена с помощью СМ. Есть и другие специфические методы для решения ТЗ.

64 Открытая ТЗ на избыток..

Пусть в ТЗ нарушено арвнение баланса:

Σ_i=1^ma_i > Σ_j=1ⁿb_j

т.е. общие запасы > общих потребностей. Известны штрафные тарифы r_i, i = 1, m, означающие издержки, связанные с невывозом единицы груза от j-го поставщика. Необходимо спланировать перевозки так, чтобы:

1. Суммарные транспортные и штрафние издержки были бы min.

2. Каждый потребитель получает не более, чем требуется.

66 Сведение её к закрытой ТЗ.

Введём в рассмотрение мнимого потребителя B_n+1 с мнимыми потребностями равными:

b_n+1 = Σ_i=1^ma_i – Σ_j=1ⁿb_j

тарифы перевозок фиктивного груза установим равными штрафным тарифам за непоставку c_{i, n+1} = r_j , j = 1, n

Теперь открытая ТЗ может быть записана как закрытая ТЗ:

f = Σ_i=1^mΣ_j=1ⁿ c_ijx_ij + Σ_i=1ⁿx_{i, n+1}r_j = Σ_j=1ⁿ⁺¹Σ_j=1ⁿ c_ijx_ij → min

Σ_i=1^m+1 x_ij = b_j , j = 1, n

Σ_j=1ⁿ x_ij = a_i , i = 1, m+1 (2)

x_ij ≥ 0

Закрытая ТЗ является ЗЛП в канонической форме и поэтому может быть решена с помощью СМ. Есть и другие специфические методы для решения ТЗ.

72-73 Методы отсечения в решении ЗЛДП. Метод Гомори.

Суть метода отсечения состоит в том что исходная ЗЛДП сначала решается без учёта целочисленности. Если найденный оптим. план оказался целочисленным, то задача решена. В противном случае к ограничениям исходной задачи добаляется 1 или несколько «правильных» ограничений – отсечений, которые должны удовлетворять следующим требованиям:

1. Ограничение должно быть минимальным неравенством.

2. Ограничение должно отсекать найденный нецелочисленный план.

3. Ограничение не должно отсекать ни одного целочисленного допустимого решения задачи.

Метод Гомори

Включает в себя использование классических методов ЛП (графический, СМ) совместно и использованием правильного отсечения спец. вида (отсечения Гомори).

Предположим, что в результате решения ЗЛДП с помощью СМ получен оптим. план x*^т = (β₁, …, β_m, 0, …, 0) (без ограничения общности, можно считать, что базисные перем. оказались первые m перем.). При этом базисные перем. выразились через свободные так:

x_i = β_i – α_{i, m+1}x_m+1 – α_{i, m+2}x_m+2 - … - α_inx_n

где x_m+1, …, x_n – свободные перем., которые равны 0 в точке оптим. плана.

Следующее линейное неравенство называется отсечением Гомори и удовлетворяет всем требованиям правильного отсечения:

{ β_i } – { α_{i, m+1} }x_m+1 – { α_i,m+2 }x_m+2 - … - { α_in }x_n ≤ 0

{z } - означает дробную часть числа z. По определению она равна z - [ z ]

69 Метод потенциалов решения закрытой ТЗ. Теорема об оптимальном плане ТЗ.

В основе метода лежит теорема об оптим. плане ТЗ:

Теорема об оптим. плане ТЗ:

Если для некоторого опорного плана X = x_ij ТЗ существуют такие числа α_i, i = 1, m и β_j, j = 1, n, называемые потенциалами поставщиков и потребителей соответственно, для которых справедливо соотношение:

0, если x_ij > 0

z_ij = β_j – α_i – c_ij =

< 0, если x_ij = 0

то указанный опорный план является оптимальным.

Опред: Цепь – упорядоченный набор клеток таблицы условий ТЗ, в которой каждая пара соседних клеток расположена либо в одном столбце, либо в одной строке, причём никакие 3 клетки не лежат в одном столбце (строке).

Опред: Цикл – цепь, в которой последняя клетка лежит в одной строке с начальной.

Алгоритм метода потенциалов:

Шаг 1: находится опорный план заполняются n + m – 1 клеток таблицы условий ТЗ.

Шаг 2: из системы уравнений β_j – α_i = c_ij , составленных для заполненных клеток определяются потенциалы поставщиков и потребителей.

Шаг 3: для свободных клеток определяются величины z_ij = β_j – α_i – c_ij. Если среди них нет положительных, то найденный опорный план является оптим. В противном случае среди всех z_ij выбирается максимальное число. Клетку, которой соотв. это число следует заполнить.

Шаг 4: определяется цикл, одной из клеток которого является клетка, подлежащая заполнению, а все другие уже заполнены. Клеткам цикла поочерёдно приписываются знаки “+” и “-“, начиная с “+” для заполняемой клетки.

Шаг 5: в заполняемую клетку заносится наименьшее из чисел x_ij, стоящих в минусовых клетках, одновременно это число вычитается из всех минусовых и прибавляется ко всем плюсовым. Эта операция называется «сдвигом по циклу пересчёта». Переход на шаг 2.

Замечание: если при этом сдвиге имеются несколько одинаковых минимальных чисел x_ij, то освобаждается только одна из таких клеток, а остальные считают занятыми с нулевыми поставками.

70 Общая постановка ЗЛДП. ЗЛДП называется любая ЗЛП с дополнительным требованием целочисленности некоторых перем., участвующих в задаче. К этой задаче относятся в частности задачи определения оптим. плана производства некоторой неделимой продукции и др. задачи.

71 Задача коммивояжера

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

Расстояния (стоимость, время) мужду пунктами A_i и A_j , i,j = 1, n

заданы и равны c_ij. Требуется составить такой план движения коммивояжера, согласно которому он смог бы побывать во всех пунктах, а общее расстояние всего маршрута было min.

1, если есть переезд из A_i в A_j

x_ij =

0 в противном случае.

Тогда исходная задача может быть записана в виде:

f = Σ_i=1ⁿΣ_j=1ⁿ c_ijx_ij → min

Σ_i=1ⁿ x_ij = 1 (приезд в A_j , j = 1, n)

Σ_j=1ⁿ x_ij = 1 (выезд из A_i , i = 1, n)

x_ij = бинарное число

Задача о назначениях

Имеется n видов работ A₁, …, A_n и такое же количество работников B₁, …, B_n, причём эффективности выполнения работ работниками известны и равны c_ij если работа A_i выполняется работником B_j.

Требуется распределить работы мужду работниками так, чтобы каждому досталось по работе и все работы были бы распределены.

1, A_i поручена B_j

x_ij =

0 в противном случае.

Тогда

f = Σ_i=1ⁿΣ_j=1ⁿ c_ijx_ij → max

Σ_i=1ⁿ x_ij = 1 (B_j имеет работу, j = 1, n)

Σ_j=1ⁿ x_ij = 1 (работа A_i будет выполнена, i = 1, n)

x_ij = бинарное число

74 Метод ветвей и границ в решении ЗЛДП.

Пусть компонента x*_j оптим. плана x* исходной ЗЛДП не является целым числом, тогда решение исходной задачи, в которой областью ограничений является область D лежит либо в области

D₁ = D∩{x : x_j ≤ [x_j]} либо в области

D₂ = D∩{x : x_j ≥ [x_j] + 1}

В результате чего исходная задача фактически распадается на 2 (ветвится):

В результате рассмотрения всех возможных

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