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

 

Шаг 2.

Применяя правила вычисления новых  элементов таблицы, получим:

 

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

Так как в последней строке присутствует отрицательный коэффициент при  свободной переменной x₁, то столбец с этой переменной будет разрешающим.

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

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

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

Шаг 3.

Применяя правила  вычисления новых  элементов таблицы, получим:

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

В последней строке присутствует отрицательный  коэффициент при свободной переменной x₅, столбец с этой переменной будет разрешающим.

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

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

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

Обратите внимание! В первой строке оценочному отношению приписываем значение  ∞, так как свободный член в этой строке (3) и элемент разрешающего столбца (-3) имеют разные знаки.

Шаг 4.

Применяя правила вычисления новых  элементов таблицы, получим:

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

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

Проверим полученные результаты.

Первая строка таблицы соответствует  уравнению 

,

откуда

Третья строка таблицы соответствует  уравнению 

,

откуда

Подставляя выражения для x₁ и x₂ в выражение для функции f(x) из условия задачи, получим

 f(x)= 2x₁ + 3x₂ 

Это уравнение в точности соответствует  последней строке полученной нами симплекс-таблицы. Подставляя значения x₃ = x₄ = 0, получим

 

f (x₃ = 0; x₄ = 0) = 24.

Если же вернуться к переменным x₁ и x₂, то при x₃ = x₄ = 0 получим x₁ = 6, x₂ = 4, и опять-таки

f(x₁ = 6; x₂ = 4) = 2∙6 + 3∙4 = 24.

Проверка закончена.

Замечание. Решение можно проиллюстрировать на чертеже. Каждому шагу решения соответствует выбор некоторой вершины многоугольника, причем на следующем шаге происходит переход в соседнюю вершину, в которой значение функции способом f(x) больше (не меньше), чем в предыдущей. Шагу 1 соответствует вершина с координатами (0; 0), шагу 2 - вершина с координатами (0; 5),  шагу 3 - вершина с координатами (3; 5),  последнему шагу 4 - вершина с координатами (6; 4).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пример 6. (метод искусственного базиса).

 

Пусть требуется найти min f(x) = x₁+3x₂ при следующих ограничениях:

 

2x₁+x₂ = 3

 

4x₁+8x₂ ≥ 8

 

x₁+2x₂ ≤ 5

 

x₁ ≥ 0; x₂ ≥ 0

 

Приводим ЗЛП к каноническому виду:

 

f(x) = x₁+3x₂

2x₁+x₂ = 3

 

4x₁+8x₂-x₃ = 8

 

x₁+2x₂+x₄ = 5

 

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

 

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

Введем искусственные переменные w₁ и w₂ в первое и второе уравнения системы ограничений:

2x₁+x₂+w₁= 3

 

4x₁+8x₂-x₃+w₂= 8

 

x₁+2x₂+x₄ = 5

 

Поскольку решается задача на min, то ЦФ М-задачи будет иметь вид:

 

= x₁+3x₂+М (w₁+w₂)

 

Для того, чтобы воспользоваться симплекс-таблицей, выражаем w₁ и w₂ из первого и второго уравнений и подставляем в ЦФ :

w₁ = 3-2x₁-x₂

w₂ = 8-4x₁-8x₂+x₃

 

= x₁+3x₂+М((3-2x₁-x₂)+( 8-4x₁-8x₂+x₃)) = (1-6м)* x₁+(3-9м)* x₂+М* x₃+11*М

Положив x₁=0, x₂=0, x₃=0, получим x₃=5, w₁=3, w₂=8

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

x⁰ = (0, 0,0, 5, 3, 8).

 

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

 

Базисные переменные	Свободные члены ур-я	Все переменные						Оценочное отношение
		x1	x2	x3	x4	w1	w2
w1	3	2	1	0	0	1	0	3/1 = 3
w2	8	4	8	-1	0	0	1	8/8 = 1
x4	5	1	2	0	1	0	0	5/2 = 2,5
	11М	(6М-1)	(9М-3)	-М	0	0	0

 

Т.к. в последней строке присутствуют положительные элементы, то начальный  опорный план неоптимален и его  можно улучшить.

Выбираем максимальный по абсолютной величине элемент. Это (9М-3), значит, столбец, отвечающий переменной x₂ , является разрешающим. Составляем оценочные отношения и выбираем наименьшее. Оно отвечает строке с базисной переменной w₂.

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

 

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

 

Базисные переменные	Свободные члены ур-я	Все переменные						Оценочное отношение
		x1	x2	x3	x4	w1	w2
w1	2	3/2	0	1/8	0	1	-1/8	4/3
w2	1	½	1	-1/8	0	0	1/8	1/1/2 = 2
x4	3	0	0	1/4	1	0	-1/4	3/0 = ∞
	3+2М	(1+3М)/2	0	(М-3)/8	0	0	(3-9М)/8

 

Т.к. в последней строке присутствуют положительные элементы, то полученное решение не оптимально и его можно улучшить.

Выбираем максимальный по абсолютной величине элемент. Это (1+3М)/2, значит столбец, отвечающий переменной x₁ , является разрешающим.

 

Составляем оценочные отношения  и выбираем наименьшее. Оно отвечает строке с базисной переменной w₁. Следовательно, переменную w₁ нужно вывести из базы, а x₁ – ввести.