Методы принятия управленческих решений (стр. 4 )

Получим симплексную таблицу для II итерации.

Б			9	5	4	3	2	0
	4	3	1/2	-1	1	0	0	1/2	-
	3	21	1/2	3	0	1	0	-1/2	7
	2	42	4	-3	0	0	1	2	-
	159	5/2	-6	0	0	0	9/2

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

Определим номер вектора, выводимого из базиса. Для этого вычислим параметр для второго столбца, он равен 7. Следовательно, из базиса выводим вектор . Выполним преобразование Жордана с элементом =3:

Б			9	5	4	3	2	0
	4	10	2/3	0	1	1/3	0	1/3
	5	7	1/6	1	0	1/3	0	-1/6
	2	63	9/2	0	0	1	1	3/2
	201	7/2	0	0	2	0	7/2

Получаем третье опорное решение с базисом . Это единственное оптимальное решение, так как для всех векторов, не входящих в базис, оценки разложений по базису опорного решения положительны:

.

Ответ: при .

в) Оптимальное решение двойственной задачи находим по формуле:

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

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

Пусть имеется m поставщиков А1, А2, ..., Аm однородного груза в количествах соответственно а1, а2, .., .аm единиц и n потребителей В1, В2, ..., Вn этого груза, потребность которых составляет соответственно b1, b2 ..., bn единиц.

Известны стоимости перевозок (тариф) единицы груза от i-го поставщика к j-му потребителю - сij (i=1,m; j=1,n).

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

Возможны три ситуации:

1) количество груза у всех поставщиков равно потребности в данном грузе всех потребителей:

или .

2) количество груза у всех поставщиков больше потребности в данном грузе всех потребителей:

или .

3) количество груза у всех поставщиков меньше потребности в данном грузе всех потребителей:

или .

В первом случае модель задачи называется закрытой, во втором и третьем – открытой.

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

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

Аналогично вводится фиктивный (m + 1)-й пункт отправления с запасом груза и тарифы полагаются равными нулю. Этим задача сводится к закрытой транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи.

Решение транспортной задачи включает следующие этапы:

1. Нахождение первоначального опорного плана (метод северо-западного угла, метод минимальной стоимости). При этом число заполненных клеток должно быть равно m+n-1.

При нахождении опорного плана методом северо-западного угла запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего используются запасы следующего по номеру поставщика.

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

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

2. Проверка опорного плана на оптимальность, например, методом потенциалов.

Пример. Четыре предприятия используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырьё сосредоточено в трёх пунктах, а запасы соответственно равны 160, 140 и 170 ед. Тарифы перевозок заданы матрицей