Материал: 5462

6

то транспортная задача называется закрытой.

Если условие баланса не выполняется, то задача называется открытой и приводится к закрытой введением фиктивного поставщика с мощностью

Для фиктивного поставщика или потребителя Сij = 0.

Приведем необходимые для решения формулировки основных теорем транспортной задачи.

Теорема 1. (О разрешимости транспортной задачи). Транспортная задача при условии выполнения баланса всегда имеет оптимальное решение.

Система ограничений математической модели (1.1) – (1.2) имеет (m + n) уравнений и m · n неизвестных.

Доказано, что одно из уравнений является линейной комбинацией остальных, то есть является линейно зависимой и число базисных переменных системы равно (m + n -1).

Теорема 2. (О числе базисных переменных). Система ограничений транспортной задачи (1.1) – (1.3) содержит (m +n -1) линейно независимых уравнений.

Из этой теоремы следует, что невырожденный план транспортной задачи (все базисные переменные xij отличны от нуля) содержит (m + n –

1) базисных переменных, которым соответствуют занятые клетки в таблице решения.

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

Метод наименьшего элемента матрицы С

Строительный песок добывается в четырех карьерах и доставляется на пять строительных площадок. Производительность карьеров за день составляет А1 – 100, А2 – 120, А3 – 80, А4 – 120 т песка. Потребность строительных площадок в песке В1 – 60, В2 – 100, В3 – 95, В4 – 125, В5 – 40 т. Затраты на добычу и доставку песка из карьеров до строительных площадок представлены матрицей

7

70 50 30 20 10

С

30 40 80 40 50

20 20 50 60 90

10 30 60 50 80

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

Решение. Карьеры представим поставщиками, строительные площадки

– потребителями. Проверим условие баланса

Условие баланса выполняется, следовательно, задача закрытого типа. Данные задачи представим в таблице

Первой в таблице заполняется клетка (i,j) с наименьшим Сij по правилу xij min ai , b j . Затем заполняются клетки в порядке возрастания Сij с

учетом предыдущих поставок. В нашем случае наименьший тариф имеют клетки (1,5) и (4,1). Выбираем любую, например (4,1), и ставим в неё

Следующими заполняются клетки в порядке возрастания Сij с учетом предыдущих поставок:

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

оптимальным планом транспортной задачи (1.1) – (1.3), то ему соответствует система из (m + n) чисел ui* и v*j , удовлетворяющим условиям

10

Затем величину θ прибавляем к поставкам в вершинах со знаком плюс и отнимаем от поставок со знаком минус. Получаем новый опорный план

Система уравнений содержит 8 линейно независимых уравнений и 9 неизвестных, поэтому одно из неизвестных задаем произвольно, остальные рассчитываем из системы уравнений.

Полагаем u4 0 (по наибольшему числу занятых клеток в четвертой строке). Получаем

Для свободных клеток вычисляем характеристики Еij Cij (ui v j ) и записываем их в левых нижних углах.