[Список тем] [Вступление к этой теме] страницы темы: [1] [2]

Решение задачи.

Решить задачу об использовании ресурсов, приведенную в разд. 1.2, с помощью симплексных таблиц.
F=2х₁ + 3х₂→max
х₁+ 3х₂ ≤ 18,
2х₁ + х₂ ≤ 16,
х₂ ≤ 5,
3х₁ ≤ 21
Решение. Расширенная система задачи имеет вид:
х₁+ 3х₂ + х₃ = 18,
2х₁ + х₂ + х₄ = 16,
х₂+ х₅ = 5,
3 х₁+ х₆ = 21.
Линейную функцию представим в виде F - 2х₁ - 3х₂= 0. Заполняем первую симплексную таблицу (табл. 5.1), в которой переменные х₃, х₄, х₅, х₆основные. Последняя строка заполняется коэффициентами линейной функции с противоположным знаком (см. п. II алгоритма).

Таблица 5.1

Базис	Свободный член	Переменные						Оценочное отношение
		x1	x2	x3	х4	x5	x6
x3	18	1	3	1	0	0	0	18/3
х4	16	2	1	0	1	0	0	16
x5	5	0	1	0	0	1	0	5 ¬
x6	21	3	0	0	0	0	1
F	0	-2	-3	0	0	0	0

В соответствии с п. III алгоритма проверяем критерий оптимальности. В последней строке имеются отрицательные коэффициенты. Выбираем из них наибольший по модулю (-3); второй столбец разрешающий, переменная х₂перейдет в основные (этот столбец зеленый). В соответствии с п. IV находим оценочные отношения и х₂ =min{l8/3; 16; 5; }= 5. Третья строка является разрешающей. На пересечении разрешающих строки и столбца стоит разрешающий элемент а₃₃= 1.
Строим табл. 5.2 по правилам п. V алгоритма:
а) в новом базисе основные переменные: х₃, х₄, х₂, х₆,
б) расставляем нули и единицы; например, в клетке, соответствующей основной переменной х₃по столбцу и строке, ставим 1, а в клетке, соответствующей основной переменной х₃по строке, а основной переменной х₂ -по столбцу, ставим 0 и т.п. В последней строке против всех основных переменных ставим 0. Третья строка получается делением на разрешающий элемент а₃₃ =1.
Остальные клетки заполняем по правилу прямоугольника. Например b'₁ = 18 - (3*5/1) = 3,
a₁₁ = 1 - 3*0/1 = 1
Получим вторую симплексную таблицу (табл. 5.2 )

Таблица 5.2

Базис	Свободный член	Переменные						Оценочное Отношение
		x1	x2	x3	х4	x5	x6
x3	3	1	0	1	0	-3	0	3 ¬
х4	11	2	0	0	1	-1	0	11/2
x2	5	0	1	0	0	1	0
x6	21	3	0	0	0	0	1	7
F	15	-2	0	0	0	3	0

Критерий оптимальности вновь не выполнен. Теперь первый столбец разрешающий; x₁ -переходит в основные, min{3/1; 11/2; ; 7}= 3; первая строка разрешающая, a₁₁- разрешающий элемент.
Новая симплексная таблица примет вид табл. 5.3.

Таблица 5.3

Базис	Свободный член	Переменные						Оценочное отношение
		x1	x2	x3	х4	x5	x6
x1	3	1	0	1	0	-3	0
x4	5	0	0	-2	1	5	0	5/5¬
X2	5	0	1	0	0	1	0	5/1
x6	12	0	0	-3	0	9	1	12/9
F	21	0	0	2	0	-3	0

И на этот раз критерий оптимальности не выполнен; пятый столбец и вторая строка разрешающие, a₂₅= 5 - разрешающий элемент.
Переходим к табл. 5.4

Критерий оптимальности выполнен, значит Fmax =24, оптимальное базисное решение (6; 4; 0; 0; 1; 3) совпадает с ранее полученным симплексным методом.

[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [В начало страницы]