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

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

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

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

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

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

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

bj ai

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

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

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

bj ai
				М

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

а ₁ + а ₂ + а ₃ = 100 + 300 + 500 = 900;

b ₁ + b ₂ + b ₃ + b ₄ = 200 + 300 + 300 + 300 = 1100.

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

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

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

v ₁=1 v ₂=0 v ₃=1 v ₄=1

	bj ai
u 1=0			-	-
u 2=1			-	-
u 3=7					М   -
u 4=-1			-

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

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

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

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

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

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

v ₁=1 v ₂=5 v ₃=6 v ₄=1

	bj ai
u 1=0
u 2=1
u 3=2					М   -
u 4=-6		-	-

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

Получим Х ^*=.

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

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

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

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

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

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

Т (Х) = → min,

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

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

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

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

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

bj ai
		6
	2
	15

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

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

bj ai	20

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

bj ai

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

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. Груз, находящийся в пунктах А ₁: А ₆, соответственно в количестве а ₁: а ₆, требуется перевести в пункты В ₁: В ₆ соответственно в количестве b ₁: b ₆. Известны тарифы с_ij ―стоимость перевозки единицы груза из пункта А _i в пункт В _j.

bj ai

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

Ответы: 1. F _min=510 ден.ед.; х ₁₁=30, х ₁₂=60, х ₂₁=30, х ₂₃=60.

2. F _min=280 ден.ед. Оптимальный план: х ₁₂= х ₂₄= х ₃₃=60, х ₂₃=20, х ₃₁=40.

3. F _min=395 ден.ед. Оптимальный план: х ₁₁=25, х ₁₃= х ₃₂=20, х ₁₂= х ₂₁=5, х ₂₃=35;

4. F _min=140 ден.ед. Оптимальный план: х ₁₄= х ₂₂=10, х ₂₃= х ₃₁= х ₃₄=5, х ₃₃=15.

5. F _min=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