ТРАНСПОРТНАЯ ЗАДАЧА
Как организовать перевозку грузов из одних пунктов в другие, чтобы общая стоимость перевозок была минимальной? ЭКОНОМИЧЕСКАЯ ПОСТАНОВКА И МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ Пусть имеем m пунктов производства, пронумерованных по i, т.е. Допустим, что выполняется баланс: общее количество единиц товара, сосредоточенных в пунктах производства, совпадает с общим количеством единиц товара, которые требуются в пунктах потребления. Запишем задачу в виде таблицы:
Сформулируем задачу таким образом, чтобы:
Из таблицы видно, что количество товара, перевезенного из первого, второго,... m -го пунктов производства, соответственно, удовлетворяют условиям: Количество товара, который ввозится в первый, второй, третий,... n -й пункт потребления удовлетворяет, соответственно, условиям: Общая стоимость всех перевозок выражается формулой: Таким образом, математическая модель этой задачи имеет вид: нужно найти минимальное значение функции при условиях
Пример 4. Для удовлетворения потребностей трех районов города хлебом работает два хлебозавода. Первый район ежедневно потребляет 26 тонн хлеба, второй 14 тонн, а третий – 10 тонн хлеба. Хлебозавод № 1 ежедневно выпекает 30 тонн хлеба, а хлебозавод № 2 – 20 тонн. Стоимость доставки каждому району одной тонны хлеба из каждого хлебозавода приведено в таблице: Таблица 4.1
Необходимо составить наиэкономнейший план перевозки хлеба. Решение. Обозначим через x – количество тонн хлеба, перевезенного из хлебозавода № 1 в первый район, y – количество тонн хлеба, перевезенного из этого же завода в другой район. Тогда в третий район из хлебозавода № 1 будет перевезено 30-x-y тонн. Поскольку первый район ежедневно потребляет 26 тонн хлеба, то со второго хлебозавода необходимо доставить 26-x тонн. Аналогично из хлебозавода № 2 необходимо доставить в другой район 14-y тонн, а в третий район x+y-20 тонн хлеба. Таким образом, ежедневный план перевозки хлеба можно представить в виде таблицы: Таблица 4.2
Стоимость всех перевозок z равняется сумме попарных произведений чисел из таблице 4.1 на соответствующие числа таблицы 4.2: z=3x+4y+6(30-x-y)+3(26-x)+5(14-y)+2(x+y-20) или z=288-4x-5y. Поскольку количество хлеба, который перевозят в данный район города, не может быть отрицательным, то все числа второй таблицы должны быть положительными: Стоимость z можно рассматривать как функцию точки М, координаты которой удовлетворяют системе неравенств. Построим в системе координат систему этих неравенств. Множество всех этих точек есть замкнутый многоугольник ABCDE. Функцию z называют целевой функцией.
1) неравенству 2) неравенству 3) неравенству 4) неравенству 5) неравенству 6) неравенству Таким образом, всем неравенствам удовлетворяют точки, которые расположены в замкнутом многоугольнике ABCDE. Целевая функция достигает максимального и минимального значений в вершинах многоугольника ABCDE, потому что в середине его частные производные
Из рисунка видно, что D(26; 0), E(20; 0). Определим значение z в каждой вершине: Из полученных значений видно, что наименьшее значение z равно 154 и достигается в вершине В, т.е. при x=16, y=14. Следовательно, наиболее экономным планом перевозок хлеба является план, который задан следующей таблицей:
Следует обратить внимание, что наибольшее значение z равно 208 и отвечает точке E(20; 0). Соответствующий план перевозок является самым дорогим. По сравнению с ним наиболее экономный план дает экономию 54 грн. ежедневно. Это пример наиболее простой транспортной задачи.
|