Построение опорного плана
Рассмотрим ТЗ, где критерием оптимальности является стоимость перевозок всех грузов, которая должна быть минимальной.
Экономико-математическая
модель ТЗ содержит системы линейных
уравнений (4.1) и (4.2), условие неотрицательности
переменных
(4.3) и целевую функцию (4.4).
Следует иметь в виду, что:
1. Всякое
неотрицательное решение системы линейных
уравнений, определяемое матрицей
называется допустимым планом ТЗ.
2. Ранг матрицы,
составленный из коэффициентов при
неизвестных системы линейных уравнений
ТЗ, на единицу меньше числа уравнений,
т.е. равен (
).
Следовательно, число линейно независимых
уравнений равно (
),
они образуют базис, а соответствующие
им (
)
переменные будут являться базисными.
3. Допустимый план
ТЗ, имеющий не более (
)
отличных от нуля величин
и где
,
называется опорным.
4. Если в опорном плане число отличных от нуля компонент равно в точности ( ), то план является невырожденным, если меньше, то план называется вырожденным.
5. План
,
при котором функция (4.4) принимает свое
минимальное значение, называется
оптимальным
планом ТЗ.
6. Для решения ТЗ необходимо и достаточно, чтобы суммарные запасы груза в пунктах отправления были равны сумме заявок пунктов назначения:
7. Модель ТЗ, удовлетворяющая условию (5), называется закрытой. Если же указанное условие не выполняется, то модель называется открытой.
В случае превышения запаса над заявками
вводится фиктивный
(
)
пункт назначения с потребностью
и соответствующие
тарифы считаются равными нулю:
В случае превышения заявок над запасом
вводится фиктивный
(
)
пункт отправления с запасом груза
и соответствующие
тарифы принимаются равными нулю:
8. Наилучшим элементом матрицы тарифов С называется наименьший тариф, если задача поставлена на минимум, наибольший тариф – если задача поставлена на максимум целевой функции.
Метод наименьшей стоимости (тарифов)
Рассмотрим один из методов построения первого опорного плана – метод наименьшей стоимости (тарифов).
Алгоритм построения первого опорного плана методом наименьшей стоимости включает следующие этапы:
среди тарифов находится наименьший;
клетка с выбранным тарифом заполняется величиной, равной максимально возможному объему груза с учетом ограничений по строке и столбцу. При этом либо весь груз вывозится от соответствующего поставщика, либо полностью удовлетворяется заявка потребителя. Строка или столбец таблицы вычеркиваются и в дальнейшем распределении не участвуют;
из оставшихся тарифов вновь находится наилучший (наименьший), и процесс продолжается до тех пор, пока не будет распределен весь груз.
Если модель ТЗ открытая и введены фиктивный поставщик или потребитель, то распределение осуществляется сначала для действительных поставщиков и потребителей и в последнюю очередь нераспределенный груз направляется от фиктивного поставщика или к фиктивному потребителю.
Метод северо-западного угла (диагональный)
Рассмотрим другой метод построения первого опорного плана – метод северо-западного угла (диагональный).
Алгоритм построения первого опорного плана методом северо-западного угла включает следующие этапы:
среди тарифов выбирается тот, который расположен в левом верхнем углу распределительной таблицы (на северо-западе, отсюда и название метода);
клетка с выбранным тарифом заполняется величиной, равной максимально возможному объему груза с учетом ограничений по строке и столбцу. При этом либо весь груз вывозится от соответствующего поставщика, либо полностью удовлетворяется заявка потребителя. Строка или столбец таблицы вычеркиваются и в дальнейшем распределении не участвуют;
из оставшихся тарифов вновь выбирается тот, который расположен в левом верхнем углу распределительной таблицы, и процесс продолжается до тех пор, пока не будет распределен весь груз.
Если модель ТЗ открытая и введены фиктивный поставщик или потребитель, то распределение осуществляется сначала для действительных поставщиков и потребителей и в последнюю очередь нераспределенный груз направляется от фиктивного поставщика или к фиктивному потребителю.
Дальнейшее улучшение первого опорного плана и получение оптимального плана производим методом потенциалов, который основан на теории двойственности.