Транспортная задача линейного программирования, ее математическая модель
Под названием транспортная задача объединяется широкий круг задач ЛП с единой математической моделью, т.к. это задача ЛП, то для ее решения может применятся один из уже известных методов( симплексный, двойственный, искусственный базис) Однако, в силу специфики мат. модели для их решения был разработан специальный метод- метод потенциала. Данный метод, как и симплексный, начинается с поиска начального решения, затем найденное решение проверяется на оптимальность и при необходимости осуществляется построение более оптимального плана. Постановка задачи: Однородный груз сосредоточен у m поставщиков А1, А2…..Am в объемах а1, а2…аm. Данный груз необходимо доставлять n потребителям В1, В2…Вn, которые формируют заявки на груз в объемах в1, в2…вn. Известны затраты (тарифы) на перевозку единицы груза от i-го поставщика J-му потребителю. Сij( i=1,m , j=1,n)- затраты на перевозку. Требуется составить такой план перевозки, при котором запасы всех поставщиков будут вывезены, заявки всех потребителей удовлетворены, а суммарные затраты на перевозку всех грузов будут минимальны. Занесем все условия задачи в специальную транспортную таблицу Математическая модель транспортной задачи: Пусть Х= х11 х12… х1n х21 х22… х2n ……………………… xm1 xm2…xmn - это план перевозки грузов от каждого поставщика к каждому потребителю хij≥0 (i=1,m; j=1,n) Суммарные затраты на перевозку грузов будут составлять ∑∑сij xij. Поскольку эти затраты нужно минимизировать, то имеем целевую функцию F(X)= ∑∑cij xij->min Груз, выводимый от одного поставщика, определяется суммой всех переменных по строке ∑ xij( j=1,n). И так как весь груз должен быть выведен, то эта сумма должна равняться запасам поставщика ∑xij=ai( j=1,n) i=1,m. Груз, направляемый одному потребителю, т.е. сумма переменных по столбцу должен полностью удовлетворять его потребностям ∑xij= bj (i=1,n) J=1,n Т.о. математическая модель задачи принимает вид: найти оптимальный план перевозки грузов от поставщиков к потребителям, минимизирующие затраты на перевозку F(x)= ∑∑cij xij->min при ограничениях: ∑хij=ai(j=1,n) ∑xij=bj(i=1,m) xij≥0 32)Открытая и закрытая модели транспортной задачи. Приведение открытой модели к закрытой. Модель ТЗ называется закрытой(задача с правильным балансом), если суммарные запасы поставщиков совпадают с суммарным спросом потребителей. Если данное условие не выполняется, т.е. ∑ai≠∑bj (i=1,m, j=1,n) , то модель открытая, а задача с неправильным балансом. Открытую модель необходимо привести к закрытому виду, при этом возможно 2 случая: 1) ∑ai>∑bj (i=1,m. j=1,n) запасов больше, чем заявок. В этом случае вводят фиктивного потребителя Вn+1, который формирует спрос на груз в объеме bn+1=∑ai-∑bj( i=1,m j=1,n). Тарифы данного потребителя считаем равными нулю. 2) ∑ai< ∑ bj( i=1, m j=1,n) спрос превышает имеющиеся запасы, в этом случае вводят фиктивного поставщика Am+1,запасы которого составляют am+1= ∑bj- ∑bi( j=1,n i=1,m). Тарифы для данного поставщика равны нулю. После того, как задача приведена к закрытому виду можно приступать к поиску начального опорного решения. Построение начального опорного решения ТЗ методом наименьших тарифов.
1. Приведём задачу к закрытому виду. Заполнение начинаем с клетки с наименьшим тарифом. 2. Занесём в эту клетку максимально возможный груз, который можно направить от 1-го поставщика 1-му потребителю. X=min{a1, b1} 3. Определяем остатки запасов и заявок. Вычёркиваем из рассмотрения поставщика или потребителя с нулевыми остатками. ЗАМЕЧАНИЕ. На каждом шаге алгоритма вычёркивать можно только одного участника. Одновременно строку и столбец вычёркивать нельзя. На свой выбор вычёркиваем. Если вычеркнут поставщик, то у потребителя ставиться ставим базисный ноль. Он участвует в дальнейшем рассмотрении груза. 4. Среди оставшихся не вычеркнутых клеток вновь находим клетку с наименьшим тарифом. И снова распределяем груз, но уже туда. Алгоритм повторяем до тех пор пока весь груз не распределим и свободных клеток не останется. ЗАМЕЧАНИЕ. Фиктивные поставщики и потребители с тарифами=0 рассматриваются в последнюю очередь. 5. Выписываем матрицу начального решения Х1 и находим значение целевой функции. Построение начального опорного решения ТЗ методом северо-западного угла. 1. Приведём задачу к закрытому виду. Заполнение начинаем с левого верхнего угла Трансп. Табл. 2. Занесём в эту клетку максимально возможный груз, который можно направить от 1-го поставщика 1-му потребителю. X=min{a1, b1} 3. Определяем остатки запасов и заявок. Вычёркиваем из рассмотрения поставщика или потребителя с нулевыми остатками. ЗАМЕЧАНИЕ. На каждом шаге алгоритма вычёркивать можно только одного участника. Одновременно строку и столбец вычёркивать нельзя. На свой выбор вычёркиваем. Если вычеркнут поставщик, то у потребителя ставиться ставим базисный ноль. Он участвует в дальнейшем рассмотрении груза. 4. Среди оставшихся не вычеркнутых клеток вновь находим левую верхнюю. И снова распределяем груз, но уже туда. Алгоритм повторяем до тех пор пока весь груз не распределим и свободных клеток не останется. 5. Выписываем матрицу начального решения Х1 и находим значение целевой функции.
Популярное: Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (640)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |