Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Задачи для самостоятельного решения. Транспортная задача по критерию времени


Транспортная задача по критерию времени

Транспортная задача с ограничениями на пропускную способность

 

Пусть требуется при решении транспортной задачи ограничить перевозки от поставщика с номером l к потребителю с номером k. Возможны ограничения двух типов: 1) хlk ≥ а; 2) хlk b, где а и b — постоянные величины.

1. Если хlk ≥ а, то необходимо прежде, чем решать задачу, сократить (уменьшить) запасы l -го поставщика и запросы k -го потребителя на величину а (зарезервировать перевозку хlk = а). После решения задачи в оптимальном решении следует увеличить объем перевозки хlk на величину а.

2. Если хlk b, то необходимо вместо k -го потребителя с запросами bk, ввести двух других потребителей. Один из них с номером k должен иметь запросы b'k = b, а другой с номером п + 1 - запросы bn+1 = bk- b. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости сl(n+1), которая принимается равной сколь угодно большому числу М (М>>1). После получения оптимального решения величины грузов, перевозимых к (п+1)-му потребителю, прибавляются к величинам перевозок k-го потребителя. Так как сl(n+1)= М -самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l,n+1) останется пустой, хl(n+1) = 0 и объем перевозки хlk не превзойдет b.

Пример.Решить транспортную задачу, исходные данные которой приведены в таблице, при дополнительных условиях: объем перевозки груза от 1-го поставщика 2-му потребителю должен быть не менее 100 единиц 12 ≥100), а от 3-го 1-му не более 200 единиц (х31 ≤ 200).

bj ai

Решение. Для того чтобы в оптимальном решении объем перевозки х12 был не менее 100 единиц, при решении задачи будем предполагать, что запасы 1-го поставщика а1 и запросы 2-го потребителя b2 меньше фактических на 100 единиц. После получения оптимального решения объем перевозки х12 увеличим на 100 единиц.



Для того чтобы удовлетворить требованию х31 ≤ 200, вместо 1-го потребителя введем двух других. Один из них под прежним первым номером имеет запросы b1 = 200 единиц и прежние стоимости перевозок единиц груза. Другому присвоим четвертый номер. Его запросы равны b4 = 500 — 200 = 300 единиц и стоимости перевозок единиц груза те же, что и у 1-го потребителя, за исключением с34, которую примем равной сколь угодно большому числу М, т.е. с34=М. После нахождения оптимального решения задачи объемы перевозок для 4-го потребителя необходимо прибавить к соответствующим объемам перевозок для 1-го потребителя.

В результате указанных преобразований таблица исходных данных задачи будет иметь вид, представленный в таблице:

 

bj ai
М

Далее задачу решаем обычным методом потенциалов. Проверяем выполнение необходимого и достаточного условия существования решения задачи. Находим суммарные запасы поставщиков и запросы потребителей:

а1 + а2 + а3= 100 + 300 + 500 = 900;

b1 + b2 + b3 + b4 = 200 + 300 + 300 + 300 = 1100.

Задача с неправильным балансом. Вводим фиктивного поставщика с запасами а4 = 1100 - 900 = 200.

Составляем начальное опорное решение Х1 методом минимальной стоимости. Записываем матрицу стоимостей С:

Кружочками в матрице С отмечены минимальные элементы, а цифрами рядом со строками и столбцами ― порядок исключения из рассмотрения поставщиков и потребителей.

v1=1 v2=0 v3=1 v4=1

bj ai
u1=0   -   -  
u2=1   -   -  
u3=7       М   -
u4=-1     -    

Полученное решение X1 имеет т + n — 1=4 + 4— 1 = 7 базисных переменных. Вычисляем значение целевой функции на этом опорном решении:

F(X1) = 100·1+100·2+200·2+300·7+200·8+100·0+100·0=4400.

Для проверки оптимальности опорного решения находим потенциалы. Записываем систему уравнений для нахождения потенциалов и решаем ее:

Система состоит, из семи уравнений и имеет восемь переменных. Так как число неизвестных на единицу больше числа уравнений, то одному из потенциалов можно задать значение произвольно: пусть и1 =0. Остальные потенциалы однозначно находятся из системы уравнений:

Значения потенциалов приведены в таблице. Находим оценки для свободных клеток таблицы:

Опорное решение неоптимальное, так как имеется положительная оценка Δ31 = 5 для клетки (3, 1). Отмечаем эту клетку знаком «+». Находим цикл для улучшения опорного решения. Определяем величину груза для перераспределения по циклу θ={100, 200, 100} = 100. Осуществляем сдвиг по циклу на величину θ=100. Получаем второе опорное решение Х2.

v1=1 v2=5 v3=6 v4=1

  bj ai
u1=0      
u2=1      
u3=2     М   -
u4=-6   -   -    

В таблице также записаны потенциалы и оценки для свободных клеток. Решение Х2 оптимальное, так как все оценки неположительные. Запишем оптимальное решение исходной задачи. Для этого увеличим объем перевозки х12 на 100 единиц и объединим объемы перевозок 4-го потребителя, с объемами перевозок 1-го потребителя.

Получим Х*=.

Вычислим значение целевой функции на этом решении:

F (X*) =100·1+100·5+300·2+100·3+300·7+100·8=4400.

Ответ: min F(X) = 4400 при X* =.

В некоторых задачах требуется запретить перевозки от отдельных поставщиков отдельным потребителям. В таких случаях либо зачеркивают клетку таблицы транспортной задачи, либо назначают соответствующую этой клетке стоимость перевозки единицы груза сколь угодно большой, равной М >> 1. В остальном задача решается обычным способом. Для разрешимости данной задачи необходимо существование начального опорного решения.



 

Задача по критерию времени возникает при перевозке срочных грузов. Как и в обычной транспортной задаче, имеется т поставщиков с запасами однородного груза в количестве а1, а2, …, ат и п потребителей, которым этот груз должен быть доставлен в объеме b1, b2, ... , bn. Известно tij, i = 1, 2, ..., m, j = 1, 2, ..., n — время, за которое груз доставляется от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок груза, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и наибольшее время доставки всех грузов является минимальным.

Составим математическую модель этой задачи. Обозначим хijобъем перевозимого груза от i-го поставщика j-му потребителю. Система ограничений задачи не отличается от системы ограничений обычной транспортной задачи. Пусть X = (xij), i = 1, 2, ..., т, j = 1, 2, ..., п — некоторое опорное решение задачи. Запишем целевую функцию задачи. Обозначим через Т(Х) наибольшее значение элементов матрицы Т=(tij), i= 1,2, ..., m, j = 1, 2, ..., п, соответствующих клеткам таблицы, занятым опорным решением: Т(Х) = . Таким образом, за время Т(Х) план перевозок будет выполнен полностью. Математическая модель имеет вид

Т(Х) = → min,

, i=1,2, ..., т,

, j= 1, 2, ..., п.

хij ≥ 0, i=1,2, ..., т, j= 1, 2, ..., п.

Задача решается в следующем порядке. Находится начальное опорное решение Х1. Определяется значение целевой функции Т(Х1) ==. Все свободные клетки, которым соответствуют значения tij > Т(Х1), исключаются из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, так как повысится значение целевой функции. Чтобы понизить ее значение, необходимо освободить клетку (l1 , k1), в которой tij достигает максимума. Для этого строят так называемые разгрузочные циклы, которые могут включать в свой состав несколько свободных клеток. В каждом разгрузочном цикле, начиная с разгружаемой клетки (l1 , k1), расставляются поочередно знаки «—» и «+» и осуществляется сдвиг на величину θ={ хij }. Если удается эту клетку разгрузить, то она исключается из рассмотрения (зачеркивается). Получается новое опорное решение Х2, на котором значение целевой функции меньше, чем на Х1. Далее снова пытаются разгрузить клетку, соответствующую Т(Х2)= ==. Процесс продолжается до тех пор, пока возможность разгрузить соответствующую клетку не исчезнет.

Пример.Найти минимальное время на осуществление всех перевозок для задачи, исходные данные которой приведены в таблице:

bj ai
6
2  
  15

Решение. Составим начальное опорное решение Х1 по методу северо-западного угла (см. табл.). Базисные нули не записываем. Максимум целевой функции Т(Х1)={10, 8, 5, 12, 4} = 12 достигается в клетке (3, 4). Перечеркнем клетку (4, 1), в которой время доставки груза t41 = 15 больше Т(Х1)= 12.

Для улучшения решения разгрузим клетку (3, 4) с помощью цикла (3, 4), (2, 4), (2, 2), (3, 2). Означим цикл, найдем θ={10, 30} = 10. Осуществив сдвиг по циклу, получим второе опорное решение Х2:

 

 

bj ai 20
 
 

Максимум целевой функции на этом опорном решении Т(Х2)={10,8,4,5,4}=10 достигается в клетке (1, 1). Перечеркнем клетку (3, 4), так как время t34=12 больше, чем Т(Х2)=10. Разгрузим клетку (1, 1) с помощью цикла (1, 1), (1, 2), (2, 2), (2, 1). Означим цикл, найдем θ={20,20}=20. Осуществив сдвиг по циклу, получим третье опорное решение Х3. Максимум целевой функции на этом опорном решении Т(Х3)={6,5,4,4,5,4}=6 и достигается в клетке (1, 2). Перечеркнем клетки (1,1), (2,2), (2,3) и (4,3): в них время t11=10, t22=8, t23=7 и t43=9 больше, чем Т(Х3)=6. Разгрузим клетку (1, 2) с помощью цикла (1, 2), (1, 3), (3, 3), (3, 2). Означим цикл, найдем θ={20, 20}=20.

bj ai
 
 
 
 

Осуществив сдвиг по циклу, получим четвёртое опорное решение Х4. Максимум целевой функции на этом опорном решении Т(Х4)={5,4,4,5,4}=5 и достигается в клетках (2, 1) и (3, 3). Перечеркнем клетки (1, 2), и (4, 2), в которых время перевозок не менее t21 =5. С помощью оставшихся невычеркнутых клеток разгрузить клетки (2, 1) и (3, 3) не удаётся, поэтому Х4 является оптимальным решением.

bj ai
 
 
 
 

Ответ: min Т(X) = 5 при X* = .

1.На двух складах А и В находится по 90 т горючего. Перевозка одной тонны горючего со склада А в пункты 1, 2, 3 соответственно стоит 1, 3 и 5 ден. ед., а перевозка одной тонны со склада В в те же пункты — соответственно 2,5 и 4 ден. ед. В каждый пункт надо доставить по одинаковому количеству тонн горючего. Составить такой план перевозки горючего, при котором транспортные расходы будут наименьшими.

2. В резерве трех железнодорожных станций А, В и С находятся соответственно 60, 80 и 100 вагонов. Составить оптимальный план перегона этих вагонов к четырем пунктам погрузки хлеба, если к пункту № 1 необходимо 40 вагонов, № 2 ― 60 вагонов, № 3 ― 80 вагонов и № 4—60 вагонов. Стоимости перегонов одного вагона со станции А в указанные пункты соответственно равны I, 2, 3, 4 ден. ед., со станции В — 4, 3,2,0 ден. ед. и со станции С — 0, 2, 2, 1 ден. ед.

3. Завод имеет три цеха А, В, С и четыре склада № 1, 2, 3, 4, Цех А производит 30 тыс, шт. изделий, цех В 40 тыс. шт., цех С—20 тыс. шт. Пропускная способность складов за то же время характеризуется следующими показателями: склад № 1—20 тыс, шт., склад № 2—30 тыс. шт., склад № 3 — 30 тыс. шт., склад № 4 —10 тыс. шт. Стоимости перевозки 1 тыс, шт изделий из цеха А в склады № 1, 2, 3, 4 соответственно равны 2, 3, 2, 4 ден. ед.; из цеха В — 3, 2, 5, 1 ден. ед., а из цеха С — 4, 3, 2, б ден. ед. Составить такой план перевозки изделий, при котором расходы на перевозку 90 тыс. шт. изделий были бы наименьшими.

4. На трех складах А, В, С находится сортовое зерно соответственно 10, 15, 25 т, которое надо доставить в четыре пункта: пункту № 1—5 т, № 2—10 т, № 3—20 т и № 4 — 15 т. Стоимости доставки одной тонны со склада А в указанные пункты соответственно равны 8, 3, 5, 2 ден ед.; со склада В — 4,1,6, 7 ден. ед. и со склада С — 1, 9, 4, 3 ден. ед. Составитьоптимальный план перевозки зерна в четыре пункта, минимизирующий стоимость перевозок.

5. Груз, находящийся в пунктах А1:А6, соответственно в количестве а1: а6, требуется перевести в пункты В1:В6 соответственно в количестве b1: b6. Известны тарифы сij ―стоимость перевозки единицы груза из пункта Аi в пункт Вj.

bj ai

Спланировать перевозки так, чтобы общая стоимость перевозок была наименьшей.

Ответы: 1. Fmin=510 ден.ед.; х11=30, х12=60, х21=30, х23=60.

2. Fmin=280 ден.ед. Оптимальный план: х12=х24=х33=60, х23=20, х31=40.

3. Fmin=395 ден.ед. Оптимальный план: х11=25, х13=х32=20, х12=х21=5, х23=35;

4. Fmin=140 ден.ед. Оптимальный план: х14=х22=10, х23=х31=х34=5, х33=15.

5. Fmin=148 ден.ед. Оптимальный план: Х*=.


СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

  1. Абрамов Л.M., Капустин В.Ф. Математическое программирование. ―Л., 1981.
  2. Акулич И.Л. Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986.
  3. Аронович А.Б., Афанасьев М.Ю., Суворов Б.П. Сборник задач по исследованию операций. — М.: Изд-во МГУ, 1997.
  4. Баумоль У. Экономическая теория и исследование операций. — М.: Прогресс, 1965.
  5. Вентцель Е.С. Исследование операций. — М: Советское радио, 1972. ― Гл. 5.
  6. Исследование операций / Под ред. Моудер Дж., Элмаграби С. — М.: Мир, 1981. ― Т. 1. ― Гл. 3.
  7. Калихман И.Л. Линейная алгебра и программирование. — М.: Высш. шк.,1967.
  8. Карасев А.И., Аксютина З.М., Савельева Т.И. Курс высшей математики для экономических вузов. Ч.II. Теория вероятностей и математическое программирование. Линейное программирование: Учеб. пособие для студентов вузов. ― М.: Высш. школа, 1982.
  9. Кремер Н.Ш. Исследование операций в экономике. — М.: Банки и биржи, 1997.
  10. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. ― М.: Высш. шк., 1980.
  11. Линейное и нелинейное программирование / Под ред. проф. И.Н. Ляшенко. —Киев: Выща шк., 1975.
  12. Линейное программирование: Учебно-методическое пособие. ― М.: Изд-во МГУ, 1992.
  13. Матвеев В.И., Сагитов Р.В., Шершнев В.Г. Курс линейного программирования для экономистов: Учеб. пособие. — М.: Менеджер, 1998.
  14. Монахов В.М., Беляева Э.С., Краснер М.Я. Методы оптимизации. ― М.: Просвещение, 1978.
  15. Муртаф Б. Современное линейное программирование. — М.: Мир, 1984.
  16. Общий курс высшей математики для экономистов :Учебник / Под ред. В.И. Ермакова. ― М.: ИНФА-М, 2002.
  17. Gass S.I. Linear Programming: Methods and Applications. — N.Y.: McGraw-Hill, 1985.
  18. Hadley G. Linear Programming. Reading, Mass: Addison-Weslcy Pub. Co, 1962.

 

 

<== предыдущая лекция | следующая лекция ==>
Алгоритм решения транспортной задачи методом потенциалов | Поставка конструкций

Дата добавления: 2014-01-04; Просмотров: 1043; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.012 сек.