Решение производственной задачи симплексным методом

Требуется максимизировать функцию доходов:

Z = 4 x₁ + 6 x₂ max

При наличии системы ограничений:

Сведем задачу на минимум к задаче на максимум. Для этого умножим функцию цели на (-1).

-Z =-4 x₁ - 6 x₂ min

Для приведения задачи к каноническому виду (с ограничениями - равенствами), пригодному к решению симплекс - методом, вводим дополнительные переменные x₃, x₄, x₅ 0.

Имеем:

-Z = -4 x₁ -6 x₂ + 0 ×х₃+ 0 ×х₄+ 0 ×х₅ min.

Дополнительные переменные x₃, x₄, x₅ означают количество неиспользованного сырья (остаток) соответственно первого, второго и третьего вида.

Запишем задачу в векторной форме:

-Z = -4x₁-6x₂ +0×х₃+0×х₄+0×х₅ min.

.

Коэффициенты при x₃, x₄, x₅ образуют единичную матрицу. Принимаем вектора коэффициентов при x₃, x₄, x₅ за базис.

Составим первую симплекс-таблицу (табл.2.2).

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

В столбец b поставим ограничения по ресурсам. Коэффициенты в столбцах а₁, а₂,…а₅ – это коэффициенты, соответствующие переменным х₁, х₂,…х₅ в системе ограничений, записанной в векторной форме.

Последняя строка называется индексной. Ее заполняют следующим образом. Находят сумму попарных произведений столбца b на С, затем вычитают соответствующий коэффициент при целевой функции.

Строка Z_j-C_j: 0´784 + 0´552 + 0´567 = 0.

Столбец а₁: 0´16 + 0´8 + 0´5 – (-4) = 4.

Столбец а₂: 0´4 +0´7 + 0´6 – (-6) = 6.

Столбец а₃: 0´1 +0´0 + 0´0 – 0 = 0 и т.д.

Таблица 2.2

Первое базисное решение находится в столбце b: x₁ = 0; x₂ = 0; x₃ = 784; x₄ = 552; x₅ = 567. При этом Z = 0. В индексной строке имеются положительные числа 4, 6. Следовательно, план не оптимален.

Применяем алгоритм симплексного метода.

1. Выбираем максимальный по абсолютной величине элемент, стоящий в индексной строке. Этот элемент равен 6. Ему соответствует столбец а₂. Этот столбец будем называть направляющим. Выделим его в симплексной таблице.

2. Выбираем направляющую строку. Для этого делим элементы столбца b на соответствующие числа направляющего столбца и находим минимальное частное. Т.е.

.

Минимальное частное соответствует третьей строке. Таким образом, направляющей строкой будет строка а₅. Выделим ее.

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

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

4. Строим вторую симплексную таблицу. Для этого переменную, соответствующую разрешающему столбцу а₂ введем в базис на место переменной а₅.

5. Элементы направляющей строки делим на разрешающий и результаты вносим в соответствующую строку второй симплекс-таблицы. То есть в третьей строке второй симплексной таблицы (табл.2.3) получим:

(63; 5/9; 1; 0; 0; 1/9).

6. Элементы направляющего столбца, кроме разрешающего, равного теперь единице, заменяем нулями. Результат вносим в соответствующий столбец новой таблицы.

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

То есть:

строка а₃:

; ; ; ; .

строка а₄:

; ; ; ; .

индексная строка:

; ; ; ; .

Таблица 2.3

Получили второе базисное решение: x₁= 0; x₂= 63; x₃= 532; x₄ =111; x₅ =0 и -Z₂ =-378(значение -378 находится на пересечении индексной строки и столбца из свободных членов). Это решение не оптимально, т.к. в индексной строке имеется положительный коэффициент .

Повторяем процедуру симплексного метода.

Выбираем направляющий столбец (положительное число в индексной строке соответствует а₁). Вводим в базис а₁ в новой симплекс - таблице.

Выбираем направляющую строку, то есть находим:

.

Направляющей строкой будет строка а₄. Разрешающий элемент .

Составим третью симплекс-таблицу (табл.2.4).

Таблица 2.4

Базис	C	b	с1 =-4	с2 =-6	с3= 0	с4= 0	с5= 0
a1	a2	a3	a4	a5
a3
a1	-4
a2	-6
Zj-Cj	-396				-	-

Получили третье базисное решение: x₁= 27; x₂= 48; x₃= 16; x₄= 0; x₅= 0; -Z=- 396.

В индексной строке нет положительных коэффициентов. Решение оптимально.

Вывод. Максимальный суммарный доход равен Z_max =396 руб. Следует произвести 27 единиц продукции A и 48 единиц продукции вида В. При этом сырье первого вида останется неизрасходованным в количестве x₃= 16 кг, а сырье второго и третьего вида будет израсходовано полностью x₄= 0; x₅= 0.

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

2.4 Транспортная задача

Транспортная задача является специальной задачей линейного программирования.

Имеется m баз (пунктов отправления) A₁, A₂,...,A_m, в которых сосредоточены запасы однородного груза в количествах соответственно. Груз необходимо перевезти n потребителям (магазинов) B₁, B₂,..., B_n в количествах соответственно. Известна стоимость перевозки единицы груза с базы A_i потребителю B_j . Требуется спланировать перевозки грузов так, чтобы их общая стоимость была минимальная.

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

. (2.9)

Рассмотрим закрытую модель транспортной задачи с матрицей перевозок, заданной в таблице 2.5.

Таблица 2.5

Базы	Потребители	Запасы
B1	B2	.................	Bn
A1	c11	c12	. .................	c1 n	a1
A2	c21	c22	. .................	c2 n	a2
................	. .............	. ................	. .................	. ........	. ..................
Am	cm1	cm2	. ..................	cm n	am
Потребности	b1	b2	. ................	bm