Вопросы к лабораторной работе: 5

1. Определение двойственного базисного плана

2. Определение коплана

3. Определение псевдоплана

4. Критерий оптимальности

5. Достаточное условие пустоты множества допустимых планов

6. Алгоритм двойственного симплекс-метода

РЕШЕНИЕ МАТРИЧНОЙ ТРАНСПОРТНОЙ ЗАДАЧИ МЕТОДОМ ПОТЕНЦИАЛОВ

Лабораторная работа 6

Постановка задачи. Имеется пунктов производства определенного вида продукции с заданным объемом производства и пунктов потребления этой продукции в объемах Известна стоимость перевозки, единицы продукции из i -го пункта производства в j -й пункт потребления –

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

(1)
Запросы всех пунктов потребления были удовлетворены

(2)

И транспортные расходы были минимальными

(3)

Здесь - количество продукции, перевозимое из i -го пункта производства в j -й пункт потребления. Ясно, что

(4)

Задача (1) - (4) является специальной задачей линейного программирования. Для существования ее решения необходимо и достаточно выполнение условия общего баланса: (количество производимой продукции равно количеству потребляемой) и в этом случае применим метод потенциалов.

Алгоритм. При решении задач (1) – (4) используют транспортные таблицы с множеством клеток

	b1	b2	…	bn
a1	c11 x11	c12 x12	…	c1n x1n	u1
a2	c21 x21	c22 x22	…	c2n x2n	u2
…	…	…	…	…	…
am	cm1 xm1	cm2 xm2	…	cmn xmn	um
	v1	v2	…	vn

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

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

2. Решение задачи (1)-(4) методом потенциалов.

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

(5)

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

2. Вычисляем оценки для небазисных клеток

3. Проверяем критерий оптимальности базисного плана:

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

б) если , то переходим к п.4.

4. Находим максимальную оценку

5. Начиная из клетки с использованием клеток строим цикл.

6. Помечаем клетки цикла знаками “+” и “−” попарно, начиная с клетки .

7. Среди перевозок, помеченных знаком “−” выбираем наименьшую .

8. Строим новую транспортную таблицу с базисным множеством

Для нее базисный план получается из предыдущего, если изменить в нем лишь перевозки по циклу следующим образом: к перевозкам в клетках, помеченных знаком “+” прибавляем , а из перевозок, помеченных знаком “−” вычитаем . Переходим к п.1.