|
Ранее сформулирована задача по перевозке грузов, которая называется транспортной задачей и заключается в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления A1 A2, ..., Ат в n пунктов потребления В1 В2, ...., Вn.
Рассмотрим транспортную задачу, где критерием оптимальности является стоимость перевозок всех грузов, которая должна быть минимальной.
Экономико-математическая модель транспортной задачи содержит системы линейных уравнений, условие неотрицательности переменных xij и целевую функцию .
Следует иметь в виду, что:
1. Всякое неотрицательное решение системы линейных уравнений, определяемое матрицей; называется допустимым планом транспортной задачи.
2. Ранг матрицы, составленный из коэффициентов при неизвестных системы линейных уравнений транспортной задачи, на единицу меньше числа уравнений, т. е. равен (m + п - 1). Следовательно, число линейно независимых уравнений равно (m + n - 1), они образуют базис, а соответствующие им (m + n - 1) переменных будут являться базисными.
3. Допустимый план транспортной задачи, имеющий не более (m + n - 1) отличных от нуля величин xij, называется опорным.
4. Если в опорном плане число отличных от нуля компонент равно в точности (т + п - 1), то план является невырожденным, если меньше, то план называется вырожденным.
5. План, при котором функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.
6. Для решения транспортной задачи необходимо и достаточно, чтобы суммарные запасы груза в пунктах отправления были равны сумме заявок пунктов назначения.
7. Модель транспортной задачи, удовлетворяющая условию, называется закрытой. Если же указанное условие не выполняется, то модель называется открытой.
8. Наилучшим элементом матрицы тарифов С называется наименьший тариф, если задача поставлена на минимум, наибольший тариф - если задача поставлена на максимум целевой функции.
Рассмотрим один из методов построения первого опорного плана - метод наименьших тарифов (стоимости).
Алгоритм построения первого опорного плана методом наименьшей стоимости включает следующие этапы:
а) среди тарифов находится наименьший;
б) клетка с выбранным тарифом заполняется величиной, равной максимально возможному объему груза с учетом ограничений по строке и столбцу. При этом либо весь груз вывозится от соответствующего поставщика, либо полностью удовлетворяется заявка потребителя. Строка или столбец таблицы вычеркивается и в дальнейшем распределении не участвует;
в) из оставшихся тарифов вновь находится наилучший (наименьший), и процесс продолжается до тех пор, пока не будет распределен весь груз.
Если модель транспортной задачи открытая и введены фиктивный поставщик или потребитель, то распределение осуществляется сначала для действительных поставщиков и потребителей, и в последнюю очередь нераспределенный груз направляется от фиктивного поставщика или к фиктивному потребителю.
9. Дальнейшее улучшение первого опорного плана и получение оптимального плана производим методом потенциалов, который основан на теории двойственности.
План X = (xij) транспортной задачи будет являться оптимальным, если существует система т + п чисел ai bj, называемых потенциалами, удовлетворяющая условиям:
Потенциалы аi и bj являются переменными двойственной транспортной задачи и обозначают оплату за перевозку единицы груза в пунктах отправления (поставщиками) и назначения (потребителями) соответственно, поэтому их сумма равна транспортному тарифу аi + bj = cij, а условия, получены на основании второй теоремы двойственности.
Введем обозначение оценки свободной клетки таблицы
ij = аi + bj-сij.
Если среди оценок ij нет положительных (задача поставлена на минимум), то опорный план является оптимальным.
|
