Пример 2.1.1

Построение начального базисного плана. Найдем оптимальный план выпуска продукции для примера 1.1.1. Запишем каноническую форму задачи:

(1.1.10)

при ограничениях

, (1.1.11)

, (1.1.12)

. (1.1.13)

Пусть x₁,x₂– свободные переменные (т.е.x₁=x₂=0). Тогда базисные переменныеs₁=1000 иs₂=25. Двойственные переменные, соответствующие этому плану, будут равныy₁=0,y₂=0, а величины:

₁ = 5y₁+ 0,1y₂- 40= -40,

₂ = 10y₁+ 0,3y₂-100 = -100 (см. пример 1.3.1 п.1).

В симплекс-методе удобно использовать симплекс-таблицы. Рассмотрим построение первой симплекс-таблицы для выбранного начального базисного решения (табл.2.1.1). В первом столбце симплекс-таблицы поместим обозначения базисных переменных s₁иs₂, а во втором – их числовые значения 1 000 и 25. Остальные столбцы состоят из коэффициентов перед переменнымиx_jв левых частях ограничений (1.1.11), (1.1.12). Последняя строка симплекс-таблицы состоит из значения целевой функцииZ = 0 и величинy₁= 0,y₂= 0, Δ₁ = -40, Δ₂ = -100.

Таблица 2.1.1

базис	значение	x1	x2	s1	s2
s1	1000	5	10	1	0
s2	25	0,1	0,3	0	1
z	0	-40	-100	0	0
		Δ1	Δ2	y1	y2

Переход от одного базисного плана к другому сопровождается преобразованием симплексных таблиц. Такой переход называется итерацией. Каждая итерация состоит из нескольких действий.

Итерация 1

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

2. Определение новой базисной переменной. Отрицательные значения в последней строке показывают, что производства обоих продуктов являются прибыльными и единица первого продукта увеличивает выручку на 40, а единица второго продукта – на 100. Поэтому следует вводить в базис одну из переменных x₁ или x₂. Выберем x₂ в качестве новой базисной переменной, т.е. вводим в базис производство второго продукта. Соответствующий переменной x₂ столбец назовем ведущим столбцом (в таблице этот столбец выделен).

3. Определение новой свободной переменной. Для определения новой свободной переменной составим отношения столбца значений базисных переменных (второго столбца) к положительным элементам ведущего столбца и найдем среди них минимальное:

.

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

4. Пересчет симплекс- таблицы. Теперь для нового базиса s₁, x₂ составим новую симплекс-таблицу (табл.2.1.2). Ее можно получить из старой симплекс-таблицы следующим образом. Все элементы ведущей (второй) строки, разделенные на ведущий элемент 0,3, образуют вторую строку новой таблицы. Например, элементу второй строки 25 первой симплекс-таблицы будет соот-ветствовать элемент второй строки новой симплекс- таблицы .

Остальные элементы новой таблицы получаются из соответствующих элементов старой таблицы. Каждому элементу соответствует один элемент в ведущей строке и один элемент в ведущем столбце. Используя эти элементы, формулы для пересчета можно сформулировать следующим образом:

новый элемент	= старый элемент-	(элемент ведущего столбца)·(элемент ведущей строки)
		ведущий элемент

Приведем пример пересчета элемента 1 000 в первой строке. Заметим, что пересчитываемому элементу 1000 соответствуют элемент 10 ведущего столбца и элемент 25 в ведущей строке. Тогда элементу 1 000 соответствует элемент в новой таблице:

.

Аналогично пересчитывается последняя строка. Например, первому элементу 0 последней строки соответствует элемент 25 в ведущей строке и элемент -100 в ведущем столбце. Тогда первый элемент последней строки новой таблицы будет равен:

.

Таблица 2.1.2

Базис	значение	x1	x2	s1	s2
s1=			0	1
x2=			1	0
z			0	0
		Δ1	Δ2	y1	y2

Симплекс-таблица определяет новый базисный план. Значения во втором столбце определяют значения базисных переменных s₁ =,x₂ =.

Все переменные, не входящие во второй столбец, являются свободными и поэтому равны 0: x₁ = s₂ = 0.

Таким образом, новое базисное решение прямой задачи имеет вид:

X₁={x₁=0,x₂=,s₁=,s₂=0}

Последняя строчка определяет:

• значение целевой функции прямой задачи Z =;

• значение Δ₁=в столбцеx₁означает, что производство первого продукта прибыльно;

• значение Δ₂ = 0 в столбцеx₂означает, что производство второго продукта рентабельно;

• значение 0 в столбце s₁означает, что теневая цена 1 кг сырья равнаy₁=0,

• значение в столбце определяетy₂теневую цену 1 часа работы оборудования.

Заметим, что значение целевой функции двойственной задачи

W= 1000∙0 + 25∙=равно значению целевой функции прямой задачи.

Итерация 2

1. Критерий оптимальности. Значение, расположенное в последней строке симплекс-таблицы в столбце переменной x_1, отрицательно. Поэтому эта таблица не определяет оптимального плана.

2. Определение новой базисной переменной. Отрицательное значение в последней строке показывает, что производство первого продукта является прибыльным и его единица увеличивает выручку на. Поэтому переменнуюx₁ нужно вводить в базис. Соответствующий столбец будет ведущим.

3. Определение новой свободной переменной. Для определения новой свободной переменной составим отношения столбца значений базисных переменных (второго столбца) к положительным элементам ведущего столбца и найдем среди них минимальное:

.

Так как минимальное значение достигается на первом отношении, то базисная переменная первой строки s₁переходит в свободные. Таким образом, переменныеx₁иx₂– базисные переменные, аs₁,s₂– свободные переменные.

В симплекс-таблице выделены: ведущий столбец (соответствующий переменной x₁) и первая строка – ведущая строка. Теперь для нового базиса x₁, x₂ вычислим новую симплекс-таблицу.

4. Пересчет симплекс-таблицы. Теперь для нового базиса x₁, x₂ составим новую симплекс-таблицу (табл. 2.1.3). Все элементы ведущей (первой) строки, разделенные на ведущий элемент, образуют первую строку новой таблицы. Остальные элементы новой таблицы вычисляются, как и на первой итерации.

Таблица 2.1.3

базис	значение	x1	x2	s1	s2
x1=	100	1	0	3/5	-20
x2=	50	0	1	-1/5	10
z=	9000	0	0	4	200
		Δ1	Δ2	y1	y2

Итерация 3

Критерий оптимальности. Среди значений последней строки симплекс- таблицы нет отрицательных. Поэтому эта таблица определяет оптимальные планы прямой и двойственной задач.