Транспортная задача с ограничениями на пропускную способность
Пусть требуется при решении транспортной задачи ограничить перевозки от поставщика с номером l к потребителю с номером k. Возможны ограничения двух типов: 1) xlk≥a; 2) xlk≤b, где a и b – постоянные величины. 1. Если xlk≥a, то необходимо прежде, чем решать задачу, сократить запасы l-го поставщика и запросы k-го потребителя на величину а (зарезервировать перевозку xlk≥a). После решения задачи в оптимальном решении следует увеличить объем перевозки xlk на величину a.. 2. Если xlk≤b, то необходимо вместо k-го потребителя с запросами bk ввести двух других потребителей. Один из них с номером k должен иметь запросы bk=b, а другой с номером n+1 – запросы bn+1=bk-b. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости cl(n+1), которая принимается равной сколь угодно большому числу М (М>>1). После получения оптимального решения величины грузов, перевозимых к (n+1)-му потребителю, прибавляются к величинам перевозок k-го потребителя. Так как cl(n+1)=M – самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l,n+1) останется пустой, xl(n+1)=0 и объем перевозки xlk не превзойдет b. Пример. Решить транспортную задачу, исходные данные которой приведены в табл. 5.3.1, при дополнительных условиях: объем перевозки груза от l-го поставщика 2-му потребителю должен быть не менее 100 единиц (x12≥100), а от 3-го 1-му не более 200 единиц (x31≤200).
Таблица 5.3.1
Р е ш е н и е. Для того чтобы в оптимальном решении объем перевозки x12 был не менее 100 единиц, при решении задачи будем предполагать, что запасы 1-го поставщика а1 и запросы 2-го потребителя b2 меньше фактических на 100 единиц. После получения оптимального решения объем перевозки x12 увеличим на 100 единиц. Для того чтобы удовлетворить требованию x31≤200, вместо 1-го потребителя введем двух других. Один из них под прежним первым номером имеет запасы b1=200 единиц и прежние стоимости перевозок единиц груза. Другому присвоим четвертый номер. Его запросы равны b4=500-200=300 единиц и стоимости перевозок единиц груза те же, что и у 1-го потребителя за исключением с34, которую примем равной сколь угодно большому числу М, т.е. с34=М. После нахождения оптимального решения задачи объемы перевозок для 4-го потребителя необходимо прибавить к соответствующим объемам перевозок для 10го потребителя. В результате указанных преобразований таблица исходных данных задачи будет иметь вид, представленный в табл. 5.3.2. Таблица 5.3.2
Далее задачу решаем обычным методом потенциалов. Проверяем выполнение необходимого и достаточного условия существования решения задачи. Находим суммарные запасы поставщиков и запросы потребителей: а1+а2+а3=100+300+500=900; b1+b2+b3+b4=200+300+300+300=1100. Задача с неправильным балансом. Вводим фиктивного поставщика с запасами а4=1100-900=200. Составляем начальное опорное решение X1 методом минимальной стоимости. Записываем матрицу стоимостей С: С= 2 4 6
Кружочками в матрице С отмечены минимальные элементы, а цифрами рядом со строками и столбцами – порядок исключения из рассмотрения поставщиков и потребителей. Таблица 5.3.3 X1 v1=1 v2=0 v3=1 v4=1
u1=0
u2=1
u3=7
u4 = -1
Полученное решение X1 имеет m+n-1=4+4-1=7 базисных переменных. Вычисляем значение целевой функции на этом опорном решении: Z(X1)=100·1+100·2+200·2+300·7+200·8+100·0+100·0=4400. Для проверки оптимальности опорного решения находим потенциалы. Записываем систему уравнений для нахождения потенциалов и решаем ее: Система состоит из семи уравнений и имеет восемь переменных. Так одно число неизвестных на единицу больше числа уравнений, то одному из потенциалов можно задать значение произвольно: пусть u1=0. Остальные потенциалы однозначно находятся из системы уравнений : u1=0; v1=1-u=1-0=1; u2=2-v1=2-1=1; v4=2-u2=2-1=1; u4=0-v4=0-1=-1; v3=0-u4=0-(-1)=1; u3=8-v3=8-1=7; v3=7-u3=7-7=0. Находим оценки для свободных клеток таблицы: Δ12=0+0-5= -5 <0; Δ13=0+1-6= -5<0; Δ14=0+1-1=0; Δ22=1+0-6= -5<0; Δ23=1+1-7= -5<0; Δ31=7+1-3=5>0; Δ34=7+1-M<0; Δ41=-1+1-0=0; Δ42=-1+0-0= -1<0. Опорное решение неоптимальное, так как имеется положительная оценка Δ31=5 для клетки (3,1). Отмечаем эту клетку знаком «+». Находим цикл для улучшения опорного решения (см. табл. 5.3.3). Определяем величину груза для перераспределения по циклу 0=min{11, 200, 100}=100. Осуществляем сдвиг по циклу на величину 0=100. Получаем второе опорное решение X2 (табл. 5.3.4)
Таблица 5.3.4 X2 v1=1 v2=5 v3=6 v4=1
u1=0
u2=1
u3=2
u4= -6
В табл. 5.3.4 также записаны потенциалы и оценки для свободных клеток. Решение X2 оптимальное, так как все оценки неположительные. Запишем оптимальное решение исходной задачи. Для этого увеличим объем перевозки x12 на 100 единиц и объединим объемы перевозок 4-го потребителя с объемами перевозок 1-го потребителя. Получим X*= • Вычислим значение целевой функции на этом решении: Z(X*)=100·1+100·5+300·2+100·3+300·7+100·8=4400. Ответ: min Z(X)=4400 при X*= • В некоторых задачах требуется запретить перевозки от отдельных поставщиков отдельным потребителям. В таких случаях либо зачеркивают клетку таблицы транспортной задачи, либо назначают соответствующую этой клетке стоимость перевозки единицы груза сколь угодно большой, равной М>>1. В остальном задача решается обычным способом. Для разрешимости данной задачи необходимо существование начального опорного решения.
Популярное: Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... ©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1180)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |