Геометрический смысл стандартной ЗЛП. Множество допустимых решений. Графический способ решения.

Различные формы задачи ЛП. Переход от стандартной задачи к канонической (допустимое решение (план), оптимальное решение).

Система m линейных уравнений и неравенств с n переменными

а₁₁ X₁ + a₁₂X₂ + … + а_1nX_n≤b₁
а₂₁ X₁ + a₂₂X₂ + … + а_2nX_n≤b₂

(1) ………………………………………………….
а_к1 X₁ + a_к2X₂ + … + а_кnX_n≤b_к

а_к1+1,1 X₁ + a_к+1,2X₂ + … + а_к+1,nX_n≤b_к+1

a_m1 X₁ + а_m2X₂ +…+ а_mnx_n ≤b_m

F=C₁x₁+C₂x₂+……+C_nx_n (2)

Необходимо найти такое решение Х=(х₁,х₂,х _l …х_n), где х _i ≥0, i =1͞, l; l ≤n(3), при котором линейная функция (2) принимает оптимальное (max/min) значение.

F=

Система:

, i =1͞,k

, i =k͞+1, m

x _j≥ 0, j=1͞, l; l ≤n

Система (1) – система ограничений, F – целевая функция (функция цели)

Опр. Оптимальное решение (оптимальный план) ЗЛП – это решение Х=(х₁,х₂,х₃…х_n) системы ограничений (1), удовлетворяющее условию (3), при котором линейная функция (2) принимает оптимальное значение.

Опр. Если все x _j ≥0 (j=1͞,n) и система ограничений (1) состоит только из неравенств, то задача называется стандартной.

Опр. Если все x _j ≥0 (j=1͞,n) и система ограничений (1) состоит только из уравнений, то задача называется канонической.

Теорема: Все перечисленные формы задач эквивалентны.

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

1) стандартная задача→каноническая задача

Рассмотрим новые переменные z₁, z₂….z_m;m=числу ограничений

Рассмотрим каноническую задачу

а₁₁ X₁ + a₁₂X₂ + … + а_1nX_n+ z₁=b₁
а₂₁ X₁ + a₂₂X₂ + … + а_2nX_n+z₂=b₂

……………………………………..

a_m1 X₁ + а_m2X₂ +…+ а_mnx_n +z_m= b_m

x _j≥ 0, j=1͞,n; z _i ≥0; i =1͞,m

F=C₁x₁+C₂x₂+…+C_nx_n + 0*z₁+0*z₂+…+0*z_m→max

Пусть Х^*=(х₁^*,х₂^*,х₃^*…х_n^*,z₁^*,z₂^*,…z_m^*) –решение канонической задачи (КЗ),

тогда (х₁^*,х₂^*,х₃^*…х_n^*) – решение стандартной задачи (СЗ).

Х^*– удовлетворяет всем ограничениям СЗ, x _j^* ≥0 и т.к. z _j ^*≥0, то равенству

а _{i 1} X₁^* + a _{i 2}X₂^* + … + а _{i n}^*+ z _i ^*=b _i соответствует неравенство а _{i 1} X₁^* + a _{i 2}X₂^* + … + а _{i n}^*≤b _i

Допустим, что Х^* - не является оптимальным решением СЗ, т.е. найдется набор =( _{1, 2,… n}), который дает большее значение целевой функции, т.е.

С_{1 1}+С_{2 2}+_…+С_{n n}=C₁x₁^*+C₂x₂^*+…+C_nx_n^*

Покажем, что это невозможно:

Рассмотрим набор ( _{1, 2,… n}, ₁, ₂… _m), где z _i = b _i – a _{i 1 1} – a _{i 2 2} – a _{i n n}, т.е. набор удовлетворяет условиям КЗ, но это противоречит оптимальности набора Х^*.

2) Каноническая→стандартная

а _{i 1} X₁ + a _{i 2}X₂ + … + а _{i n}=b _i

Система:

а _{i 1} X₁ + a _{i 2}X₂ + … + а _{i n}≤ b _i

─а _{i 1} X₁ ─ a _{i 2}X₂ ─… ─ а _{i n}≤ ─b _i

и т.д.

Замечание: в случае, когда в задаче требуется минимизировать линейную функцию, задачу можно свести к задаче максимизации.

Опр. Набор (вектор) Х=(х₁,х₂,х₃…х_n), удовлетворяющий всем ограничениям ЗЛП называется допустимым набором (вектором).

Опр. Если множество допустимых решений не пусто, то задача называется допустимой.

Геометрический смысл стандартной ЗЛП. Множество допустимых решений. Графический способ решения.

n=2

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

а₁₁ X₁ + a₁₂X₂ + … + а_1nX_n≤b₁
а₂₁ X₁ + a₂₂X₂ + … + а_2nX_n≤b₂

(4)………………………………….

a_m1 X₁ + а_m2X₂ +…+ а_mnx_n ≤b_m

(5) х₁≥0, х₂ ≥0

(6) F=C₁x₁+C₂x₂→max

Замечание: к такой форме может быть сведена КЗ, когда число переменных n, больше числа уравнений на 2, т.е. n – m = 2

Теорема 2.1:

Множество решений неравенства а₁₁ X₁ + a₁₂X₂ ≤b₁, с двумя переменными является одной из полуплоскостей, на которые вся плоскость делится прямой, включая эту прямую (а₁₁ X₁ + a₁₂X₂ =b₁), а другая полуплоскость с этой же прямой есть множество решений неравенства а₁₁ X₁ + a₁₂X₂ ≤b₁

PQ║OX₂,x_2p x_2m и x_2q x_2m↔х₂ │*а₁₂ 0

Замечание: n=3 (x₁,x₂,x₃) – точка пространства (7) а₁₁х₁+а₁₂х₂+а₁₃х₃=b₁ – плоскость

Решением неравенства а₁₁х₁+а₁₂х₂+а₁₃х₃ ≤ b₁ будет одно из полупространств, на которые данная плоскость делит все пространства, включая эту плоскость.

Если , то (x₁,x₂,…x_n) – точка n-мерного пространства

(8) а₁₁ X₁ + a₁₂X₂ + a₁₃X₃ + … + а_1nX_n = b₁ – гиперплоскость

Теорема 2.2:

Множество всех решений линейного неравенства с «n» переменными

а₁₁ X₁ + a₁₂X₂ + a₁₃X₃ + … + а_1nX_n ≤ b₁ является одним из полупространств, на которые все пространство делится гиперплоскостью (8), включая эту плоскость

Множество решений системы неравенств

2х₁+х₂≤3

х₁+2х₂≤3

х₁≥0, х₂≥0

а)Ограниченное множество б)неограниченное множество в) точка

г)система несовместна (множество решений пусто)

Опр.1 Множество точек плоскости (пространства) называется выпуклым, если вместе с любыми двумя своими точками содержит весь отрезок, соединяющий эти точки.

Теорема 2.3:

Пересечение выпуклых множеств – есть выпуклое множество

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

Пусть M и N A B, отсюда M и N A; и M и N B (А и В выпуклые множества) следовательно MN A и MN B, отсюда MN A B

Следствие: множество решений системы неравенств (4) является выпуклым (если оно не пусто).

Опр2. Точка множества называется внутренней, если в некоторой ее окрестности содержатся только точки данного множества.(М)

Опр3. Точка множества называется граничной, если в любой ее окрестности содержатся, как точки данного множества, так и точки, не принадлежащие данному множеству.(N)

Опр4. Точка выпуклого множества называется угловой или крайней, если она не является внутренней ни для какого отрезка целиком принадлежащего данному множеству.(Р)

Опр5. Множество точек называется замкнутым, если оно содержит все свои граничные точки.

Опр6. Множество называется ограниченным, если существует круг (в пространстве шар) конечного радиуса, который полностью содержит в себе данное множество.

Опр7. Выпуклое замкнутое множество точек плоскости (пространства), имеющее конечное число угловых точек называется выпуклым многоугольником (многогранником), если оно ограничено и выпуклой многоугольной областью, если оно неограниченно.

Теорема 2.4:

Множество решений совместной системы (4), (5) m линейных неравенств с двумя переменными является выпуклым многоугольником (многоугольной областью).

Замечание: Опр.1-7 имеют место и в случае n-мерного пространства.

Х'=(x₁', x₂',…x_n')

X²=(x₁²,x₂²,…x_n²)

Отрезком, соединяющим эти точки, называется множество точек Х=(x₁,x₂,…x_n), удовлетворяющих условию Х=αх'+(1-α)x², где α [0;1] можно переписать в виде Х=α₁х¹+α₂x², где α₁,α₂≥0, α₁+α₂=1

Опр. Точка Х называется выпуклой линейной комбинацией точек х¹, х²,..хⁿ, если Х=α₁х¹+α₂x²+..+ α_nxⁿ

Теорема 2.5:

Множеством решений совместной системы m неравенств с n переменными является выпуклым многогранником (многогранная область) в n-мерном пространстве.

Теорема 2.6:

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

Геометрическим способом можно решить только стандартную задачу (4) – (6) с двумя переменными (n=2).

F=C₁x₁+C₂x₂

Линия уровня функции F=F(х₁;х₂)

F=a

C₁x₁+C₂x₂=а – прямая

gradF(x₁;x₂)=(z'x₁;z'x₂) – показывает направление наискорейшего роста функции.

q=gradF=(C₁;C₂)

min – в точке Е – точке входа в многоугольник

max – в точке С – точка выхода из многоугольника

Пример:

2х₁+3х₂≤12

2х₁+х₂≤8

х₁≥0, х₂≥0

F=4x₁+3x₂→max

1)2х₁+3х₂=12

2)2х₁+х₂=8

Линия уровня F=0

q=(4,3)

B – Точка пересечения прямых 1) и 2)

2х₁+3х₂=12

2х₁+х₂=8

х₁=3;х₂=2

Fmax=4*3+3*2=18

Замечание: При решении графическим методом задачи (4) – (6) на отыскание max возможны следующие случаи:

бесконечное множество оптимальных единственное оптимальное решение

решений CD=a _{i 1}x₁+a _{i 2}x₂=b _i

отсутствует конечный оптимум F=∞ отсутствие допустимых решений

Теорема 3.1:

Если ЗЛП имеет оптимальное решение, то линейная функция принимает max (min) значение в одной из угловых точек многогранника решений. Если функция принимает max(min) более чем в одной угловой точке, то она принимает его в любой точке, является выпуклой линейной комбинацией этих точек.

3. Метод исключения Жордано-Гаусса для систем линейных уравнений. (базовые, свободные переменные, разрешающий элемент, базисное решение, опорный план, вырожденное решение)

Данасистема: a₁₁x₁+a₁₂X₂+…+a_1nx_n = b ₁

_{……………………………………………………………}

a_m1x₁+a_m2X₂+…+a_mnx_n= b _ь

Замечание

Будем считать, что ранг А=m, т.е. все уравнения линейно независимы. Если rangA=m=n, то решение единственное. Если rangA=m<n- бесконечное кол-во решений.

Любые m-переменные системы называются базисными или основным, если определитель матрицы коэффициентов при них отличен от нуля, а остальные n-m переменные – свободные. |a₁₁a_1n |

|a_m1a_mn|

A= (a₁₁…a_1j…a_1n|b₁)

....

(a_i1…a_ij….a_in|b_i )

....

(a_m1..a_mj…a_mn|b_m)

Пусть a_ij не равно 0 – разрешающий элемент, ai1…aij….ain - разрешающая строка\ стобец

3. Метод исключения Жордано-Гаусса для систем линейных уравнений. (базовые, свободные переменные, разрешающий элемент, базисное решение, опорный план, вырожденное решение)

Данасистема: a₁₁x₁+a₁₂X₂+…+a_1nx_n = b ₁

_{……………………………………………………………}

a_m1x₁+a_m2X₂+…+a_mnx_n= b _ь

Замечание

Будем считать, что ранг А=m, т.е. все уравнения линейно независимы. Если rangA=m=n, то решение единственное. Если rangA=m<n- бесконечное кол-во решений.

Любые m-переменные системы называются базисными или основным, если определитель матрицы коэффициентов при них отличен от нуля, а остальные n-m переменные – свободные. |a₁₁a_1n |

|a_m1a_mn|

Алгоритм.

На первом этапе (прямой ход) система приводится к ступенчатому виду, путем последовательного исключения переменных.

На втором этапе решения (обратный ход) мы будем последовательно находить переменные из получившейся ступенчатой системы.

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

2. Если самое верхнее число в этом столбце ноль, то меняют всю первую строку матрицы с другой строкой матрицы, где в этой колонке нет нуля.

3. Все элементы первой строки делят на верхний элемент выбранного столбца.

4. Из оставшихся строк вычитают первую строку, умноженную на первый элемент соответствующей строки, с целью получить первым элементом каждой строки (кроме первой) ноль.

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

6. После повторения этой процедуры раз получают верхнюю треугольную матрицу

7. Вычитают из предпоследней строки последнюю строку, умноженную на соответствующий коэффициент, с тем, чтобы в предпоследней строке осталась только 1 на главной диагонали.

8. Повторяют предыдущий шаг для последующих строк. В итоге получают единичную матрицу и решение на месте свободного вектора (с ним необходимо проводить все те же преобразования).

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

Пример

Для решения следующей системы уравнений:

Запишем её в виде матрицы 3×4, где последний столбец является свободным членом:

Проведём следующие действия:

· К строке 2 добавим: −4 × Строку 1.

· К строке 3 добавим: −9 × Строку 1.

Получим:

· К строке 3 добавим: −3 × Строку 2.

· Строку 2 делим на −2

· К строке 1 добавим: −1 × Строку 3.

· К строке 2 добавим: −3/2 × Строку 3.

· К строке 1 добавим: −1 × Строку 2.

В правом столбце получаем решение:

.

Через конечное число шагов получим таблицу, где m-столбцов, в которых, каждая из исключенных переменных входит в только одно из уравнений системы с коэф=1. Исключенные переменные являются базисными, а остальные – свободными. Конечная таблица –приведённая. Решение x=(x₁, x₂…x_n) называется допустимым, если все его компоненты не отрицательные. Допустимое базисное решение называется опорным планом.

Базисное решение, в котором хотя бы одна неосновная базисная переменная равна нулю, называется вырожденное.

4. Симплексные преобразования исключения переменных

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

Замечание: Без огранич. общ.можно считать, что в системе все правые части не отрицательные. Если какое то b_i<0, то соответствующее уравнение умножается на (-1).

Считаем, что b_i>=0, то: В симплексных преобразованиях системы, в которых все переменные правой части не отрицательные, есть неотрицательное базисное решение. Если получено одно неотрицательное базисное решение, то остальные неотрицательные базисные решения можно получить из него симплексными преобразованиями.

Док-во из формул пересчета симплексных преобразований.

В самом деле не нулевые компоненты базисного решения равны правым частям β_i, а они остаются неотрицательными.

= , где a – разрешающий элемент

Если a_kj<0 то _k>=0 /// если a_kj>0, то _k делится на a_kj=> то _k>0

1) Составляем симплекс таблицу из коэффициента системы

2) Выбираем разрешающий элемент

3) Осуществляется пересчет по след.правилам:

1. все элементы делятся на разрешающий элемент.

2. все элементы разрешающего столбца зануляются.

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

Если в разрешающей строке имеется 0, то соответствующий столбец переносится без изменений.

= =….= =

Базисное решение (0,1,0,2,3)

5.Решение симплексным методом, канонической задачи Л.П.

A₁₁X₁+A₁₂X₂+...A_1nX_n=B₁

A₂₁X₁+A₂₂X₂+...A_2nX_n=B₂ (12)

A_m1X₁+A_m2X₂+...A_mnX_n=B_m

X1,2>=0 Xn>=0 (13)

F=C₁X₁+C₂X₂+...C_nX_n-->max (14)

___

rang A=m Bj>=0 (i=1,m)

Тогда, с помощью симплексных преобразований системы(12), можно привести к виду:

X₁+d_1.m+₁X_m+1+...d_1.nX_n=B₁

X₂+d_2.m+₁X_m+1+...d_2.nX_n=B₂ (15)

X_m+d_m.m+₁X_m+1+...d_m.nX_n=B_m

X₁=-d_1.m+₁X_m+1+...-d_1.nX_n=B₁

X₂=-_d2.m+₁X_m+1+...-d₂._nX_n=B₂ (15)

X_m=-d_m.m+₁X_m+1+...-d_m.nX_n=B_m

(15) - общее решение

Решение (B1,B2,Bm, 0,0) -допустимое базисное решение.

Подставляя в целевуюфун-ю (14) вместо базисных пер-ныч X1,X2,Xm их выражения (15)

через свободное, получим:

F=-j_m+₁X_m+1-j_m+₂X_m+2-...-j_nXn+j (17)

Для получения базисного решения (16) значения целевой ф-ии F=j0

m

jn=d_1кC1+d_2кC₂+...d_mкC_n-C_к= di_кC_i-C_к

i=1

j₀=B₁C₁+B₂C₂+...B_nC_n-C₀

величина jn-оценки

Если все jnn>=0, то увеличить значения fun F нельзя и следовательно решения (16)является

оптимальным и Fmax=jo

F=-3X₁-2X₂+5

X₁-0x₂=0 Fmax=5

Если существует jp<0, то значения фун-ии можно увеличить за счет увеличения

соответствующей переменной Хр.

Пер-ю Хр нужно включить в базис, а одну из базисных пер-х перевести в свободное,

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

симплексные преобразования.

Все эти вычисления проводят в симплекс таблицах.

Перенесем ф-ию цели (17) в виде:

F+jm+1Xm+1+jm+2Xm+2..+jnXn=Jо и добавим это рав-во к сис-меогранич (15)

если Переменная F, входит только в одно ур-ние,то она всегда будет базисной

Базис	X1	X2	Xm	Xn+1	Xn
X1				d1.m+1	d1n	B1
X2				d2.m+1	d2n	B2
Xm				dm.m+1	dmn	Bm
F				jm+1	jn	jo

Cимплекс-таблица для нового опорного плана, получают симплпреобр-м данной табл, где в качестве

разреш столбца берут столбец соотв-й отрицательной оценке замещения.

Алгоритм:

1)проверяют выполнение критериев оптимальности при решение задачи на max-наличие в последней строке отриц. Коэффициентов ji<0 если все значения j≥0, то решение оптимально допустимо Fmax=j₀

(В₁,В₂,В_m,0,0,0)-оптимреш

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

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

3)Вычисляют оценочные отношения т.е. отношение элемента столбца свободных членов и соответственно положит. Элементам разреш столбца

4)строим следующее таблицу по следующим правилам

А)первоначальная Х_рвводится в базис, а первоначальная Х_q становится свободным

Б) все элементы разрешающей строки делятся на разрешающий элемент.

В)все элементы разрешающего столбца кроме разреш элемента зануляются

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

Д)с полученной табл.повторяются пункты с 1-5

Теорема 8

Если после выполнеия очередной операции:

1) найдется хотя бы одна отриц. Оценка и в каждой таблице с такой оценкой окажется хотя бы один один положительный то можно можно улучшить решение

2)если найдется хотя бы одна отрицательная оценка, столбец который не содержит который не содержит положительных эл-ов, то функция не ограничена сверху в области доп решений т.е. не существует конечного max.

3)все оценки окажутся не отрицательными, ji≥0, то достигнуто оптимальное решение.

Транспортная задача. Постановка задачи. Закрытая и открытая ТЗ. Приведение открытой ТЗ к закрытой. Число положительных компонентов опорного плана.

Пусть некоторый однородный продукт имеется у m поставщиков А₁,А ₂…А_m. Его необходимо доставить n-потребителям В_1, В ₂….В_n

Известна стоимость Cijперевозки ед. груза.

Необходимо составить оптимальный план перевозок Xij

Пусть запасы и потребности сбалансированы

Составим матем. модель.

Общие транспортные расходы.

F=

Дата добавления: 2015-08-20