Содержание
-
Транспортная задача
-
Постановка задачи: Имеется т пунктов отправления (поставщиков) грузов: на которых сосредоточены запасы какого-либо однородного груза в объемах соответственно: Величины at определяют максимально возможные размеры вывоза груза с пунктов отправления. Суммарный запас груза поставщиков составляет Кроме того, имеется п пунктов назначения: которые подали заявки на поставку грузов в объемах соответственно: Суммарная величина заявок составляет .
-
Стоимость перевозки одной единицы груза от поставщика At к потребителю Bj обозначим через cij (транспортный тариф). Общая стоимость перевозок составляет матрицу транспортных издержек С. В качестве критерия оптимальности выбираем суммарные издержки по перевозке грузов. Тогда транспортная задача формулируется следующим образом: необходимо составить оптимальный план, т. е. найти такие значения объема перевозок грузов от поставщиков Аiк потребителям Вj, чтобы вывести все грузы от поставщиков; удовлетворить заявки каждого потребителя и обеспечить минимальные транспортные расходы на перевозку груза.
-
Все исходные данные транспортной задачи можно записать в виде таблице, которая называется транспортной: С и X.
-
Задача заключается в определении плана перевозок - матрицы X, которая удовлетворяет условиям: ∑xij=ai ∑xij=bj F=∑∑cij*xij→min
-
Рассмотрим транспортную задачу, где критерием оптимальности является стоимость перевозок всех грузов, которая должна быть минимальной. Экономико-математическая модель транспортной задачи содержит системы линейных уравнений, условие неотрицательности переменных xij и целевую функцию. Следует иметь в виду, что: 1. Всякое неотрицательное решение системы линейных уравнений, определяемое матрицей X = (хij), i = 1, k; j = 1, л; называется допустимым планом транспортной задачи. 2. Ранг матрицы, составленный из коэффициентов при неизвестных системы линейных уравнений транспортной задачи, на единицу меньше числа уравнений, т. е. равен (т + п - 1). Следовательно, число линейно независимых уравнений равно (т + п - 1), они образуют базис, а соответствующие им (т + п - 1) переменных будут являться базисными. 3. Допустимый план транспортной задачи, имеющий не более (т + п - 1) отличных от нуля величин xij,называется опорным.
-
4. Если в опорном плане число отличных от нуля компонент равно в точности (т + п - 1), то план является невырожденным, если меньше, то план называется вырожденным. 5. План X = (хij) (i = l, т; j= 1, п), при котором функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи. 6. Для решения транспортной задачи необходимо и достаточно, чтобы суммарные запасы груза в пунктах отправления были равны сумме заявок пунктов назначения: 7. Модель транспортной задачи, удовлетворяющая условию, называется закрытой. Если же указанное условие не выполняется, то модель называется открытой.
-
В случае превышения запаса над заявками вводится фиктивный (п + 1) пункт назначения с потребностьюbn+1=∑ai-∑bj и соответствующие тарифы считаются равными нулю ci,n+1=0. При вводится фиктивный (m + 1) пункт отправления с запасом груза и соответствующие тарифы принимаются равными нулю:
-
Наилучшим элементом матрицы тарифов С называется наименьший тариф, если задача поставлена на минимум, наибольший тариф - если задача поставлена на максимум целевой функции. Алгоритм построения первого опорного плана методом наименьшей стоимости включает следующие этапы: а) среди тарифов находится наименьший; б) клетка с выбранным тарифом заполняется величиной, равной максимально возможному объему груза с учетом ограничений по строке и столбцу. При этом либо весь груз вывозится от соответствующего поставщика, либо полностью удовлетворяется заявка потребителя. Строка или столбец таблицы вычеркивается и в дальнейшем распределении не участвует; в) из оставшихся тарифов вновь находится наилучший (наименьший), и процесс продолжается до тех пор, пока не будет распределен весь груз.
-
Замечание: Если модель транспортной задачи открытая и введены фиктивный поставщик или потребитель, то распределение осуществляется сначала для действительных поставщиков и потребителей, и в последнюю очередь нераспределенный груз направляется от фиктивного поставщика или к фиктивному потребителю. Дальнейшее улучшение первого опорного плана и получение оптимального плана производим методом потенциалов, который основан на теории двойственности.
-
План X = (xij) транспортной задачи будет являться оптимальным, если существует система т + п чисел αi, βj называемых потенциалами, удовлетворяющая условиям: 1. F(X) →min ai+bj = cijдля занятых клеток, где xij>0 ai+bj ≤ cijдля занятых клеток, где xij=0 2. F(X) →max ai+bj = cijдля занятых клеток, где xij>0 ai+bj≥ cijдля занятых клеток, где xij=0 Потенциалы ai и bj являются переменными двойственной транспортной задачи и обозначают оплату за перевозку единицы груза в пунктах отправления (поставщиками) и назначения (потребителями) соответственно, поэтому их сумма равна транспортному тарифу аi+ bj= cij,а условия получены на основании второй теоремы двойственности.
-
Введем обозначение оценки свободной клетки таблицы Если среди оценок нет положительных (задача поставлена на минимум), то опорный план является оптимальным. Алгоритм оценки оптимальности плана методом потенциалов включает следующие этапы. а. Построение первого опорного плана. б. Проверка вырожденности плана. Потенциалы aiи bj могут быть рассчитаны только для невырожденного плана. Если число занятых клеток в опорном плане меньше, чем (т + п - 1), то не хватит количества уравнений для определения потенциалов, поэтому вносим нуль в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным (т + п - 1). Нуль вводят в клетку с наименьшим тарифом, например в клетку одновременно вычеркиваемых строки и столбца таблицы при составлении нового плана. При этом фиктивно занятая нулем клетка не должна образовывать замкнутого прямоугольного контура с другими клетками таблицы.
-
в. Определение значения функции цели путем суммирования произведений тарифов (удельных затрат) на объем перевозимого груза по всем занятым клетками таблицы. г. Проверка условия оптимальности. Определяем потенциалы ai и bj. Для каждой занятой клетки таблицы записываем уравнение Получим систему (т + п - 1) уравнений с (т + п) переменными. Так как число переменных больше числа уравнений, то система является неопределенной и имеет бесконечное множество решений. Поэтому одному из неизвестных потенциалов аi, bj задают произвольное значение, например, для простоты вычислений полагаем a1 = 0. Тогда остальные потенциалы определяются из приведенных соотношений. В транспортную таблицу добавляются дополнительная строка и столбец, куда заносятся потенциалы. Определяем оценки свободных клеток
-
Если все (задача решается на минимум целевой функции) либо все (задача решается на максимум целевой функции), то оптимальный план найден. Если хотя бы одна оценка свободной клетки (задача поставлена на минимум) или (задача поставлена на максимум), план не является оптимальным, его можно улучшить, осуществив перераспределение груза. д. Построение нового опорного плана. Из всех положительных оценок свободных клеток выбираем наибольшую (если задача поставлена на минимум), из отрицательных — наибольшую по абсолютной величине (если задача поставлена на максимум). Клетку, которой соответствует наибольшая оценка, следует заполнить, т. е. направить груз. Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других занятых и связанных с заполняемой так называемым циклом.
-
Циклом, или прямоугольным контуром, в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, другое - в столбце. Если ломаная линия, образующая цикл, пересекается, то точки пересечения не являются вершинами. Для каждой свободной клетки таблицы можно построить единственный цикл. Вершинам цикла, начиная от вершины, находящейся в свободной клетке, присваиваем поочередно знаки « + » и «-». Из объемов груза, стоящих в минусовых клетках, выбираем наименьшее и обозначим его γ. Перераспределяем величину γпо циклу, прибавляя γк соответствующим объемам груза, стоящим в плюсовых клетках и вычитая у из объемов груза, находящихся в минусовых клетках таблицы. В результате клетка, которая ранее была свободной, становится занятой, а одна из занятых клеток цикла становится свободной. Полученный новый опорный план проверяется на оптимальность, т. е. возвращаемся к четвертому этапу алгоритма.
-
Примечания: Если в минусовых клетках построенного цикла находятся два (или несколько) одинаковых минимальных значения то при перераспределении объемов груза освобождаются две (или несколько) клеток, и план становится вырожденным. Для продолжения решения необходимо одну или несколько освобождающихся клеток таблицы занять нулем, причем предпочтение отдается клетке с наилучшим тарифом. Нулей вводится столько, чтобы во вновь полученном опорном плане число занятых клеток было равно (т + п - 1). Если в оптимальном плане транспортной задачи оценка свободной клетки равна нулю , то задача имеет множество оптимальных планов. Для клетки с нулевой оценкой можно построить цикл и перераспределить груз. В результате полученный оптимальный план будет иметь такое же значение целевой функции.
-
Значение целевой функции на каждой итерации можно рассчитать следующим образом: (задача поставлена на минимум); (задача поставлена на максимум), где - величина перемещаемого по циклу объема груза; - оценка свободной клетки, в которую направляется груз при переходе к новому плану; значение целевой функции на к-й итерации; значение целевой функции на предыдущей итерации.
-
Пример 1. На три базы А1, А2, А3 поступил однородный груз в количествах, соответственно равных 6, 8, 10 ед. Этот груз требуется перевезти в четыре магазина Вх, В2, В3, В4 соответственно в количествах 4, 6, 8, 8 ед. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов (тыс. руб. за ед. груза): 1 2 4 3 С = 4 3 8 5 2 7 6 3 i =1,2,3 j= 1,2,3,4 ∑ai = 6+8+10=24 ∑bj=4+6+8+8=26 Отсюда следует, что транспортная задача является открытой. Введем дополнительную базу А4 с запасом груза 26-24=2 ед. Тарифы перевозки полагаем равными нулю.
-
Второй план
-
F(X1) = 4-1 + 2- 2 + 4- 3 + 4- 8 + 2- 6 + 8- 3 + 2- 0 = 88 тыс. руб,
-
Опорный план 3
-
-
Опорный план 4
-
-
Поскольку все оценки неположительны, меньше или равны нулю, то план IV является оптимальным, что можно представить в виде матрицы: Анализ плана. С первой базы необходимо весь груз направить в третий магазин, со второй базы направить в первый и второй магазины в количестве 2 ед. и 6 ед., а груз с третьей базы следует вывозить в первый и четвертый магазины в количестве 2 и 8 ед. соответственно. При этом потребность третьего магазина В3 остается неудовлетворенной в объеме 2 ед. Общая стоимость доставки груза потребителям будет минимальной и составляет 78 тыс. руб. Так как оценка свободной клетки Δ24 = О, то задача имеет множество оптимальных планов.
-
Пример выполнения задачи в Excel. Задача организации оптимального снабжения. Три фермерских хозяйства Л1,Л2,Л3ежедневно могут доставлять в город соответственно 60, 60 и 50 ц молока для обеспечения пяти торговых точек: В1 В2,В3, В4, В5. Стоимость перевозки 1 ц молока и потребности торговых точек в молоке указаны в таблице: Определить оптимальный план поставки молока в каждую точку для удовлетворения потребностей, чтобы суммарные транспортные издержки были минимальными.
-
Экономико-математическая модель задачи Переменные: хij(i = 1,3; j = 1,5) — количество молока, поставляемое фермерским хозяйством Jв I-ю торговую точку. Целевая функция — суммарные транспортные издержки, которые необходимо минимизировать:
-
1. Указать адреса ячеек, в которые будет помещен результат решения. Изменяемые ячейки — В11: F13. В эти ячейки в результате решения задачи будут записаны оптимальные значения Хij. 2. Ввести исходные данные. 3. Ввести зависимости для ограничений. Поместите курсор в ячейку G11. Выберите функцию СУММ. Выделите необходимые для суммирования ячейки B11:F11. Нажмите кнопку ОК для подтверждения ввода формулы для суммирования
-
Аналогичные действия выполните для ячеек С14 и F14.
-
Для вычисления значения целевой функции, соответствующей минимальным суммарным затратам на доставку груза, зарезервируйте ячейку и введите формулу для ее вычисления: Запустите Мастер функций (значок fx). В окне Категория выберите Математические. В окне Функциявыберите СУММПРОИЗВ. Нажмите кнопку ОК. Вокне СУММПРОИЗВ укажите адреса массивов, элементы которых обрабатываются этой функцией В нашей задаче целевая функция представляет собой произведение затрат на доставку молока (ячейки B3:F5) и объемов поставок для каждого потребителя (содержимое ячеек В11 :F13). В поле Массив1 укажите адреса B3:F5. В поле Массив2 укажите адреса B11:F13. Нажмите кнопку ОК. В поле ячейки G14 появится некоторое числовое значение, равное произведению поставок на коэффициенты затрат по доставке грузов
-
-
Запустить команду Поиск решений.
-
Ввести ограничения. Поместите указатель мыши на кнопку Добавить. Появится диалоговое окно Добавление ограничения. Первая запись в поле В соответствии с ограничениямипредставляет собой ограничения по уровню спроса, вторая запись — ограничения по уровню запасов. После ввода всех ограничений нажмите кнопку ОК. Ввести параметры для решения ЗЛП. Установите флажок:Сделать переменные без ограничений неотрицательными. В окне Выберите метод решения укажите Поиск решения линейных задач симплекс-методом. Нажмите кнопку Найти решение — на экране появится диалоговое окно Результаты поиска решения
-
-
Ответ: Общие затраты на перевозку продукции составят 785 ден. ед. Спрос торговых точек удовлетворен полностью — они получат 150 ц молока. У первого фермерского хозяйства останется нереализованным 20 ц молока. Следует иметь в виду, что при решении задач в Excel результаты иногда выдаются в экспоненциальной форме записи. Данный формат используется для отображения и вывода очень больших (45 ООО ООООООООО, в Excel это 4.5Е+13) или очень малых чисел (0,000 000 002 1, в Excel это 2.1Е-09). Надстройка Поиск решения при заданной точности решения такие числа (например, 2.1Е-09) не отличает от нуля.
-
Задача о назначениях — это распределительная задача, в которой для выполнения каждой работы требуется один и только один ресурс (один человек, одна автомашина и т.д.) и каждый ресурс может быть использован на одной и только одной работе, т.е. ресурсы неделимы между работами, а работы неделимы между ресурсами. Таким образом, задача о назначениях является частным случаем транспортной задачи. Задача о назначениях имеет место при распределении людей на должности или работы, автомашин на маршруты, водителей на машины, групп по аудиториям, научных тем по научно-исследовательским лабораториям и т.п.
-
Экономико-математическая модель задачи По сравнению с транспортной задачей процесс приведения задачи о назначениях к сбалансированному виду имеет свои особенности (принимают значение «0» или «1»). Для этого необходимо при вводе ограничений указать тип переменных Двоичное . При добавлении ограничений на целочисленность справа вводят адреса изменяемых ячеек.
Нет комментариев для данной презентации
Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.