2.3 Алгоритм метода искусственного базиса

Шаг 1. Приводим задачу ЛП к канонической форме

(2.3.1)

с неотрицательными правыми частями .

Шаг 2. В каждую i-ю строку ограничений вводим искусственную неотрицательную переменную x_i и строим вспомогательную задачу ЛП вида:

(2.3.2)

Эта задача имеет допустимое базисное решение . Для этого целевую функцию необходимо выразить через свободные переменные :

Шаг 3. Для построенной вспомогательной задачи строим симплексную таблицу:

	b		…
			…
			…
.	.	…
			…

и находим оптимальное решение вспомогательной задачи с помощью симплекс-метода.

Шаг 4. Если и все переменные являются небазисными, то m переменных из войдут в базис и система ограничений, соответствующих симплексной таблице, будет иметь вид:

(2.3.3)

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

Шаг 5. Если , но в базисе остались искусственные переменные , для которых , то проводим для каждой искусственной переменной из базиса следующее преобразование симплексной таблицы: выбираем ведущим столбцом столбец такой переменной , для которой элемент индексной строки , а элемент столбца . В этом случае строка искусственной переменной будет ведущей и после стандартного преобразования симплексной таблицы (Шаг 6 из прямого симплекс-метода) искусственная переменная выведется из базиса. В результате получим симплексную таблицу, соответствующую Шагу 4.

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

3 Расчетная часть

Рассмотрим пример:

Пусть количество сырья Х=10 у.е. При этом количество видов сырья m = 3, и число видов вырабатываемой продукции n также равно 3.

Зададим таблично цену реализации единицы каждого вида продукта P_i :

P1 (у.д.е)	P2 (у.д.е)	P3 (у.д.е)
2	2	3

Зададим произвольно матрицу затрат q:

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

Рассмотрим Вариант №1, когда вектор имеет вид (5,2,3):

Подставим имеющиеся данные в математическую модель (1.5).

Тогда задача примет вид:

Таким образом, получаем задачу линейного программирования, которая может быть решена с использованием Симплекс-метода на минимум.

Для этого минимизируем целевую функцию и запишем полученную задачу ЛП в канонической форме:

Перепишем полученную ЗЛП в специальной форме:

Очевидно, что в данном случае в исходной ЗЛП присутствует базис, поэтому использование метода искусственного базиса не требуется.

Д ля полученной задачи строим Симплекс-таблицу:

	b	y1	y2	y3
L	0	2	2	3
t1	5	1	2	3
t2	2	1	2	1
t 3	3	1	2	2

	b	y1	y2	t3
L	-9/2	1/2	-1	-3/2
t1	1/2	-1/2	-1	3/2
t 2	1/2	1/2	1	-1/2
y3	3/2	1/2	1	1/2

	b	t1	y2	t3
L	-5	-1	-2	-1
t1	1	1	-1	1
y 2	1	1	2	-1
y3	1	-1	0	1

Так как среди элементов индексной строки симплекс-таблицы нет положительных элементов, то симплекс-таблица оптимальна.

Оптимальное решение при x=(5,2,3)

Это означает, что при распределении сырья по трем видам в количестве 5, 2, и 3 соответственно, наиболее выгодно будет производить только продукцию второго вида в количестве, указанном в оптимальном решении.

Ниже приведена Таблица 1, в которой представлены дальнейшие вычисления способа распределения продукции при различных вариантах вектора х.

Все вычисления производились в среде MatLab 6.5.

Таблица 1

№ варианта
1
2
3
4
5
6
7
8
9
10
11
12

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

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

Ответ: