Математические методы в экономике

I случай. Пусть в системе ограничений имеется единичный неотрицательный базис. Например, он имеет вид:

 

Тогда, очевидно, первые m переменных  х₁,…,х_m выбираются в качестве базисных переменных, а остальные – свободные. Приравнивая свободные переменные к нулю, получаем начальный опорный план.

 

 

 

Пример 2.

 

f(x) = -5x₁+x₃ min

2x₁-2x₃+x₄ = 2

 

2x₁+x₂-x₃ = 3

 

x_j ≥ 0, j = 1, 2, 3, 4.

 

В первом ограничении базисной переменной является x₄, а во втором x_2. Система приведения к положительному единичному базису.

Свободные переменные  x₁ и x₃ приравнивают к нулю. Получим невырожденный начальный опорный план х⁰ = (x₁; x₂; x₃;x₄) = (0; 3; 0; 2)

В этом случае f(x⁰) = 0.

 

II случай. Пусть система ограничений имеет вид:

 

Сведем задачу к каноническому  виду, добавив к левым частям системы  ограничений добавочные переменные x_n+i ≥ 0, i = 1, 2, …,m. Получим эквивалентную исходной систему ограничений, имеющую базисный вид:

 

 

 

Отсюда получаем начальный  опорный план:

х⁰ = (x₁;…, x_n; x_n+1;..., x_n+m) = (0;…,0, b₁; …; b_m)

 

Замечание. В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю.

 

Пример 3.

 

f(x) = 10x₁-7x₂-5x₃ min

6x₁+15x₂+6x₃ ≤ 9 + x₄

 

14x₁+42x₂+16x₃ ≤ 21 + x₅

 

2x₁+8x₂+2x₃ ≤ 4 + x₆

 

x_j ≥ 0, j = 1, 2, 3

 

Вводим добавочные переменные в первое, второе и третье ограничения, получим:

 

f(x) = 10x₁-7x₂-5x₃ +0*x₄+0*x₅+0*x₆

6x₁+15x₂+6x₃+ x₄ = 9

 

14x₁+42x₂+16x₃ + x₅ = 21

 

2x₁+8x₂+2x₃ + x₆ = 4

 

x_j ≥ 0, j = 1, 2,…, 6

 

Система ограничений имеет  базисный вид. Начальный опорный  план получаем,  как и ранее, приравнивая  к нулю свободные переменные x₁, x₂, x₃:

х⁰ = (x₁; x₂; x₃;x₄; x₅; x₆) = (0; 0; 0; 9; 21; 4); f(x⁰) = 0

 

III случай. Пусть система ограничений имеет вид:

 

     

Перейдем к каноническому  виду путем введения дополнительных переменных

x_n+i ≥ 0, i = 1, 2, …,m.

Система ограничений не имеет базисного вида, т.к. коэффициенты или x_n+1, x_n+2,.., x_n+m равны – 1. В этом случае вводят искусственный базис путем перехода к М-задаче. Для этого в каждое ограничение канонической формы, не имеющее базисный вид вводят искусственные переменные w_i, а к целевой функции прибавляют (задача на минимум) или от нее вычитают (задача на максимум ) сумму всех искусственных переменных, умноженных на большое число М:

где w_i – искусственные переменные.

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

Начальный опорный  план М-задачи имеет вид:

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

 

Пример 4.

 

f(x) = -5x₁+4x₂+3x₃+6x₄ min

x₁+21x₂+x₃+2x₄ ≤ 3 + x₅

 

-x₁-14x₂-2x₃+3x₄ ≥ 2 - x₆+w₁

 

x₁-6x₂+x₃-x₄ ≥ 1 - x₇+w₂

 

x_j ≥ 0, j = 1, 2, 3, 4

Вводя дополнительные переменные x₅, x_6, x₇ и искусственные переменные w₁ и w_{2 ,} переходим к задаче в каноническом виде и к М-задаче.

x₁+21x₂+x₃+2x₄ +x₅ = 3

                      -x₁-14x₂-2x₃+3x₄ - x₆+w₁ = 2

                       x₁-6x₂+x₃-x₄- x₇+w₂ = 1

 

x_j ≥ 0, j = 1, 2,.., 7; w_i≥0, I = 1,2

Начальный опорный план имеет вид:

х⁰ = (0; 0; 0; 0; 3; 0; 0; 2; 1).

 

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

Приведя модель ЗЛП  к базисному  виду, ее записывают в так называемую симплекс-таблицу.

Симплекс – таблица.

 

Базисные переменные	Свободный член уравнения	Все переменные				Оценочные отношения
		x1	x2	…	xn
xi	b1
xi+1	b2
…
xi+m	bn
f(x)	0

 

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

Последняя строка симплекс – таблицы  содержит коэффициенты целевой функции, взятые с противоположным знаком.

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

Алгоритм решения  ЗЛП с помощью симплекс-таблицы:

1. Привести ЗЛП  к каноническому виду.
2. Привести систему ограничений к базисному виду.
3. Приравнять нулю свободные переменные и определить начальный опорный план.
4. Занести условия задачи в симплекс-таблицу. Если все элементы последней строки симплекс-таблицы неотрицательные (или неположительны при поиске min целевой функции f(x)), то начальный опорный план оптимален и ЗЛП решена. Если существуют отрицательные элементы в последней строке симплекс-таблицы (положительное при поиске min), то план неоптимален и его можно улучшить. Перейти к п.5.
5. Среди элементов последней строки симплекс-таблицы найти максимальный по абсолютной величине (наименьший при поиске max и наибольший при поиске min). Столбец симплекс-таблицы, отвечающий этому элементу, будет разрешающим столбцом. Переменную, отвечающую разрешающему столбцу нужно ввести в базис.
6. Для определения переменной, выводимой из базиса, составить оценочные отношения (отношения свободных членов к элементам разрешающего столбца). При этом, если элемент разрешающего столбца равен нулю или отрицателен, то оценочное отношение считают равным ∞. Строка, отвечающая наименьшему оценочному отношению, называется разрешающей, а элемент стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим элементом.
7. Перейти к новому опорному плану, для чего составляют новую симплекс-таблицу по следующему правилу:

а) разрешающую строку старой симплекс-таблицы  делят на разрешающий элемент  и записывают в новой симплекс-таблице;

б) в столбцах «Все переменные», соответствующих  новым базисным переменным один элемент  будет равен 1 (в строке соответствующей  этой переменной), а все остальные  элементы равны 0.

в) все остальные элементы новой  симплекс-таблицы пересчитывает  по правилу прямоугольника. Для пересчета, например,  элемента с старой симплекс-таблицы, строится воображаемый прямоугольник из соответствующих элементов таблицы:

 

 

 

 

 

 

где а – разрешающий элемент, а b и d -  элементы таблицы, расположенные в вершинах воображаемого прямоугольника. Тогда соответствующий элемент с’ новой симплекс-таблицы равен:

Если все элементы последней  строки новой симплекс-таблицы неотрицательны при поиске max ЦФ f(x), то опорный план оптимален и ЗЛП решена.

В противном случае перейти к  п. 5.

 

Особые случаи симплекс-процедуры.

 

1. Признак зацикливания.

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

2. Признак бесконечного множества оптимальных планов.

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

3. Признак неограниченности целевой функции.

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

4. Признак несовместимости системы ограничений.

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

 

Пример 5. Пусть требуется найти максимум линейной функции f(x) = 2x₁ + 3x₂ при следующих условиях:

 

Решение

 

Добавим в левые части неравенства  неотрицательные переменные x₃, x₄, x₅ и запишем полученную систему ограничений в следующем виде:

 

 

Возьмем в качестве базисных переменные x₃, x₄, x₅, а в качестве свободных - переменные x₁ и x₂. При x₁ = x₂ = 0 получим x₃ = 18, x₄ = 16, x₅ = 5. Набор (0; 0; 18; 16; 5), очевидно,  является допустимым базисным решением системы уравнений.

 

Шаг 1. Составим первую симплекс-таблицу:

 

Базисные переменные	Свободный член уравнения	Все переменные					Оценочное отношение
		x1	x2	x3	x4	x5
x3	18	1	3	1	0	0
x4	16	2	1	0	1	0
x5	5	0	1	0	0	1
f(x)	0	-2	-3	0	0	0

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

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

Значение переменной x₂ (она перейдет в базисные) увеличится до 5, а значение переменной x₅ (она перейдет в свободные) уменьшится до 0.

 

Базисные переменные	Свободный член уравнения	Все переменные					Оценочное отношение
		x1	x2	x3	x4	x5
x3	18	1	3	1	0	0	18/3 = 6
x4	16	2	1	0	1	0	16/1 = 16
x5	5	0	1	0	0	1	5/1 = 5
f(x)	0	-2	-3	0	0	0