golunova_l_v_matematicheskie_modeli_v_transportnyh_raschetah

творных узлов до строительных объектов указано в таблице. Определите, в каком объеме, с каких растворных узлов и куда должен доставляться раствор, чтобы транспортные издержки по его доставке автотранспортом были минимальными.

12. На складах A, B, C находится сортовое зерно 100, 150, 250 т, которое нужно доставить в четыре пункта. Пункту 1 необходимо поставить 50 т, пункту 2 – 100, пункту 3 – 200, пункту 4 – 150 т сортового зерна. Стоимость доставки 1 т зерна со склада A в указанные пункты соответственно равна 80, 30, 50, 20 д. е.;

со склада B – 40, 10, 60, 70 д. е.; со склада C – 10, 90, 40, 30 д. е.

Составьте оптимальный план перевозки зерна из условия минимума стоимости перевозки.

13. Торговая фирма «Весна и осень» включает четыре предприятия и шесть складов в различных регионах страны. Каждый месяц предприятия фирмы производят 100, 15, 90 и 55 ед. продукции. Вся производимая продукция направляется на склады, вместимость которых следующая: 30, 40, 55, 80, 45 и 10 ед. продукции. Издержки транспортировки продукции от предприятий до складов указаны в таблице в д. е. Распределите план перевозок из условия минимизации ежемесячных расходов на транспортировку.

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

141

шт. изделий. Стоимость перевозки 1 тыс. шт. изделий из цеха A на склады 1, 2, 3, 4 – соответственно (д. е.): 20, 30, 40, 40, из цеха B – соответственно 30, 20, 50, 10, а из цеха C – соответственно 40, 30, 20, 60. Составьте такой план перевозки изделий, при котором расходы на перевозку 90 тыс. шт. изделий были бы наименьшими.

15. Груз, хранящийся на трех складах и требующий для перевозки 60, 80, 106 автомашин соответственно, необходимо перевезти в четыре магазина. Первому магазину требуется 44 машины груза, второму – 70, третьему – 50 и четвертому – 82 машины. Стоимость пробега одной автомашины за 1 км составляет 10 д. е. Расстояния от складов до магазинов указаны в таблице. Составьте оптимальный по стоимости план перевозки груза от складов до магазинов.

16. Потребность области в азотных удобрениях составляет 180 тыс. тонн в год. Поставку азотных удобрений могут осуществлять три завода со следующими мощностями: 200, 175 и 225 тонн удобрений в квартал. Потребителями азотных удобрений в области являются 5 агропромышленных фирм. Их потребности в удобрениях следующие: 100, 130, 80, 190 и 100 тонн в квартал. Транспортные затраты на поставку удобрений с заводов в агрофирмы представлены в таблице. Найдите оптимальный план поставки удобрений с минимальными транспортными издержками.

17. Три завода выпускают грузовые автомобили, которые отправляются четырем потребителям. Первый завод поставляет 90 платформ грузовиков, второй – 30 платформ, третий – 40

142

платформ. Требуется поставить платформы следующим потребителям: первому – 70 шт., второму – 30, третьему – 20, четвертому – 40 шт. Стоимость перевозки одной платформы от поставщика до потребителя указана в таблице (д. е.). Составьте оптимальный план доставки грузовых автомобилей.

18. Строительство магистральной дороги включает задачу заполнения имеющихся на трассе выбоин до уровня основной дороги и срезания в некоторых местах дороги выступов. Срезанным грунтом заполняются выбоины. Перевозка грунта осуществляется грузовиками одинаковой грузоподъемности. Расстояние от срезов до выбоин и объем работ указаны в таблице (км). Составьте план перевозок, минимизирующий общий пробег грузовиков.

19. Промышленный концерн имеет два завода и пять складов в различных регионах страны. Каждый месяц первый завод производит 40, а второй – 70 ед. продукции. Вся продукция, производимая заводами, должна быть направлена на склады. Вместимость первого склада равна 20 ед. продукции; второго – 30; третьего – 15; четвертого – 27; пятого – 28 ед. Издержки транспортировки продукции от завода до склада приведены в таблице (ед.). Распределите план перевозок из условия минимизации ежемесячных расходов на транспортировку.

143

распределения пяти продавцам. Стоимость перевозки в расчете на один километр пути, пройденного трайлером, равна 60 д. е. Один трайлер может перевозить до 15 автомобилей. Стоимость перевозок не зависит от того, насколько полно загружается трайлер. В приведенной ниже таблице указаны расстояния между центрами распределения и продавцами, а также величины, характеризующие ежемесячный спрос и объемы поставок, исчисляемые количеством автомобилей. Определите минимальные затраты на доставку автомобилей.

21. Четыре бензохранилища с суточным объемом хранения 60, 40, 100 и 50 тыс. т авиационного бензина снабжают пять аэропортов, спрос на бензин у которых составляет 30, 80, 65, 35 и 40 тыс. т бензина в сутки. Бензин транспортируется в аэропорты одинаковыми по вместимости бензозаправщиками. Стоимость провоза бензина бензозаправщиком на расстояние 1 км составляет 7 д. е. Бензохранилище 2 не связано с аэропортом 5, а 3-е бензохранилище не связано с 1-м аэропортом. Расстояние от бензохранилищ до аэропортов указано в таблице. Найдите оптимальный план поставки бензина с минимальными транспортными издержками. Рассчитайте стоимость доставки бензина от каждого аэропорта до хранилища.

22. Четыре растворных узла потребляют в сутки 170, 190, 230 и 150 т песка, который отгружается с трех песчаных карьеров. Суточная производительность карьеров равна соответственно 280, 240 и 270 т песка. Карьеры взимают плату за погрузку песка каждые сутки не с количества отгруженного материала, а «с

144

факта» его отгрузки, куда входит стоимость погрузки, цена песка и транспортные расходы доставки потребителю при закреплении его за карьером. Стоимость перевозки 1 т песка от карьеров до растворных узлов приведены в таблице. Найдите оптимальный вариант закрепления растворных узлов за карьерами.

23. Имеются две станции технического обслуживания (СТО), выполняющие ремонтные работы для трех автопредприятий. Производственные мощности СТО, стоимость ремонта в различных СТО, затраты на транспортировку от автопредприятий на СТО и обратно и прогнозируемое количество ремонтов в планируемом периоде на каждом автопредприятии приведены в таблице. Определите, какое количество автомашин из каждого автопредприятия необходимо отремонтировать на каждой СТО, чтобы суммарные расходы на ремонт и транспортировку были минимальными.

24. Три молочных фермы с суточным производством 40, 25 и 35 тыс. л молока снабжают четыре молокозавода, спрос у которых: 15, 40, 30 и 15 тыс. л молока в сутки. Молоко доставляется на заводы молоковозами, одинаковыми по вместимости. Стоимость провоза молока молоковозом на расстояние 1 км составляет 3 д. е. Ферма 2 не связана с молокозаводом 4. Расстояние

145

от ферм до молокозаводов указано в таблице. Найдите оптимальный план поставки молока с ферм на молокозаводы с минимальными транспортными издержками. Рассчитайте стоимость доставки молока от каждой фермы до молокозавода.

25. Три нефтеперерабатывающих завода с суточной производительностью 10; 8 и 6 млн. галлонов бензина снабжают три бензохранилища, спрос которых составляет 6; 11 и 7 млн. галлонов. Бензин транспортируется в бензохранилища по трубопроводу. Стоимость перекачки бензина на 1 км составляет 5 д. е. на 100 галлонов. Первый завод не связан с третьим хранилищем. Расстояние от заводов до бензохранилищ указано в таблице. Сформулируйте соответствующую транспортную задачу и решите на минимум транспортных затрат.

146

5. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ

5.1. ОБЩАЯ ИДЕЯ СИМПЛЕКС-МЕТОДА

Одним из наиболее эффективных универсальных вычислительных методов решения любых задач линейного программирования является симплекс-метод (метод последовательного улучшения). Его основы были разработаны в 1947 г. американским математиком Данцигом. Суть симплекс-метода заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательное улучшение планов задачи по определенному критерию до тех пор, пока не будет получено оптимальное решение. Иначе говоря, необходимо, чтобы задача линейного программирования была представлена в каноническом виде. В этой системе ограничений должны быть выделены базисные неизвестные. На каждом шаге от данного базиса Б переходят к другому, новому базису Б1 с таким расчетом, чтобы при значение функции Z уменьшалось, то есть ZБ1 ≤ ZБ. Для перехода к новому базису из старого базиса удаляется одна из переменных и вместо нее вводится другая из числа свободных. После конечного числа шагов находится некоторый базис БК, для которого ZБК есть искомый минимум для линейной функции Z, а соответствующее базисное решение является оптимальным либо выясняется, что задача не имеет решения.

5.2. АЛГОРИТМ СИМПЛЕКС-МЕТОДА

Рассмотрим систему ограничений и линейную форму вида:

147

Используя метод Жордана-Гаусса, приведем записанную систему к виду, где выделены базисные переменные. Введем условные обозначения: x1, x2, …, xn – свободные переменные; xr+1, xr+2, …, xr+n – базисные переменные.

Таблица 5.1 называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменением содержания этой таблицы.

Алгоритм симплекс-метода сводится к следующему:

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

2.Вычисляют отношение свободных членов к положительным элементам разрешающего столбца (симплекс-отношение). Находят наименьшее из этих симплекс-отношений, оно со-

148

ответствует разрешающей строке.

3.На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

4.Если имеется несколько одинаковых по величине симплексотношений, то выбирают любое из них. То же самое относится к положительным элементам последней строки табли-

цы 5.1.

5.После нахождения разрешающего элемента переходят к таблице 5.2. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Таблица 5.1 преобразуется в таблицу 5.2.

6.Элемент таблицы 5.2, соответствующий разрешающему элементу таблицы 5.1, это обратная величина разрешающего элемента.

7.Элементы строки таблицы 5.2, соответствующие элементам разрешающей строки таблицы 5.1, получаются путем деления соответствующих элементов таблицы 5.1 на разрешающий элемент.

8.Элементы столбца таблицы 5.2, соответствующие элементам разрешающего столбца таблицы 5.1, получаются путем деления соответствующих элементов таблицы 5.1 на разрешающий элемент и берутся с противоположным знаком.

149

9.Остальные элементы вычисляются по правилу прямоугольника: мысленно вычерчиваем прямоугольник в таблице 5.1, одна вершина которого совпадает с разрешающим элементом, а другая – с элементом, образ которого мы ищем; остальные две вершины определяются однозначно. Тогда искомый элемент из таблицы 5.2 будет равен соответствующему элементу таблицы 5.1 минус дробь, в знаменателе которой стоит разрешающий элемент, а в числителе – произведение элементов из двух неиспользованных вершин прямоугольника.

10.Как только получится таблица, в которой в последней строке все элементы отрицательны, считается, что минимум найден. Минимальное значение функции равно свободному члену в строке целевой функции, а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные в этом случае равны нулю.

11.Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений, то есть минимум не достигается.

Пример 5.1. Задана целевая функция Zmin = –3x1 + х2 + 3x3 при ограничениях

2x1 + х2 + x3 ≤ 5;

–x1 + 3x2 – x3 ≤ 4; x1 + 2x2 + x3 ≤ 8;

xi ≥ 0, i = 1,3 .

Решение:

Запишем задачу в каноническом виде. Для этого в уравнения ограничений введем дополнительные переменные х4 ≥ 0, х5 ≥ 0 и x6 ≥ 0. Тогда задача линейного программирования будет иметь вид:

Zmin = –3x1 + х2 + 3x3;

2x1 + х2 + x3 + х4 = 5;

–x1 + 3x2 – x3 + х5 = 4; x1 + 2x2 + x3 + x6 = 8;

xi≥ 0, i = 1,6.

Здесь базисные переменные – х4, х5, x6; свободные – х1, x2, х3. Запишем в симплекс-таблицу (таблица 5.3) исходные данные. Приравняем свободные переменные к нулю и получим координаты начальной вершины многоугольника:

х1 = 0, x2 = 0, х3 = 0, х4 = 5, х5 = 4, x6 = 8.

150