Методы оптимизации в экономике (стр. 3 )

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

.

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

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

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

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

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

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

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

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

То есть:

строка а3:

; ; ; ; .

строка а4:

; ; ; ; .

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

; ; ; ; .

Таблица 3

Базис	C	b	с1=-4	с2=-6	с3=0	с4=0	с5=0
a1	a2	a3	a4	a5
a3	0	532	124/9	0	1	0	-4/9
a4	0	111	37/9	0	0	1	-7/9
a2	-6	63	5/9	1	0	0	1/9
Zj-Cj	-378	2/3	0	0	0	-2/3

Получили второе базисное решение: x1=0; x2=63; x3=532; x4=111; x5=0 и -Z2=-378(значение -378 находится на пересечении индексной строки и столбца из свободных членов). Это решение не оптимально, т. к. в индексной строке имеется положительный коэффициент .

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

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

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

.

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

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

Таблица 4

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

Получили третье базисное решение: x1=27; x2=48; x3=16; x4=0; x5=0; -Z=-396.

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

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

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

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

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

Имеется m баз (пунктов отправления) A1, A2,...,Am, в которых сосредоточены запасы однородного груза в количествах соответственно. Груз необходимо перевезти n потребителям (магазинов) B1, B2,..., Bn в количествах соответственно. Известна стоимость перевозки единицы груза с базы Ai потребителю Bj. Требуется спланировать перевозки грузов так, чтобы их общая стоимость была минимальная.

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

. (9)

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

Таблица 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

1.4.1. Математическая модель и анализ транспортной задачи

Обозначим xij - величина груза, перевозимого с базы Ai потребителю Bj.

Так как стоимости перевозок (тарифы) известны, запишем функцию общих затрат на перевозку:

. (10)

Величина перевозимых грузов не может быть отрицательна:

. (11)

Если задача с выполненным балансом, т. е. выполняется условие (9), то количество вывозимого с i-ой базы груза должно совпадать с запасами на этой базе:

, (12)

количество привозимого j-ому потребителю груза должно совпадать с его потребностями

. (13)

Математическая модель задачи: требуется минимизировать функцию затрат (функцию цели) Z:

(14)

При наличии ограничений:

(15)

Отметим следующие особенности транспортной задачи:

1. Все коэффициенты в системе ограничений равны единице.

2. Не все m + n уравнений являются независимыми. В силу условия одно из ограничений можно исключить и тогда для общего числа m´n переменных будет m + n - 1 ограничений. То есть опорный план должен содержать не более m + n - 1 компонент. В этом случае план называется невырожденным. В случае вырожденного опорного плана число компонент будет меньше, чем m + n - 1. Если план оказывается вырожденным, то в клетку следует ввести пустую поставку (груз, равный 0) и считать ее заполненной.

При решении транспортной задачи выделяются следующие шаги.

1. Составление начального плана перевозок.

2. Проверка плана на оптимальность и его пошаговое уточнение.

Задача 2 (транспортная задача)

На трех базах А1, А2, А3  находится однородный груз в количестве 50, 90 и 60 т соответственно. Этот груз необходимо развести пяти потребителям В1, В2, В3, В4, В5, потребности которых в данном грузе составляют 20, 60, 30, 50 и 40 т соответственно. Стоимость перевозок пропорциональна расстоянию и количеству перевозимого груза. Матрица тарифов и значения приведены в таблице 6. Требуется спланировать перевозки так, чтобы их общая стоимость была минимальной.

Таблица 6

Базы	Потребители	Запасы
B1	B2	B3	B4	B5
A1	20	22	9	6	13	50
A2	5	13	7	4	10	90
A3	30	18	15	12	8	60
Потребности	20	60	30	50	40	200

1.4.2. Составление начального плана перевозок