Транспортная задача - Линейное программирование

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

Имеется ряд пунктов производства с объемами производства в единицу времени (месяц, квартал), равными соответственно и пункты потребления потребляющие за тот же промежуток времени соответственно продукции. В случае, если решается закрытая (сбалансированная) задача, сумма объемов производства на всех пунктах-поставщиках равна сумме объемов потребления на всех пунктах-получателях:

Кроме того, известны затраты по перевозке единицы продукта от каждого поставщика к каждому получателю -- эти величины обозначаются В качестве неизвестных величин выступают объемы продукта, перевозимого из каждого пункта производства в каждый пункт потребления, соответственно обозначаемые.

Тогда наиболее рациональным прикреплением поставщиков к потребителям будет такое, при котором суммарные затраты на транспортировку будут наименьшими:

При этом каждый потребитель получает нужное количество продукта:

И каждый поставщик отгружает весь произведенный им продукт:

Как и во всех подобных случаях, здесь также оговаривается неотрицательность переменных: поставка от какого-то пункта производства тому или иному пункту потребления может быть равна нулю, но отрицательной, т. е. следовать в обратном направлении, быть не может.

Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта ai), а столбцы -- пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем -- значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (xi, j=0), называют свободными, а ненулевые -- занятыми (xi, j>0).

В1

В2

......

Вn

Всего

C1, 1

C1, 2

......

C1, n

А1

A1

C2, 1

C2, 2

......

C2, n

А2

A2

....

....

....

....

....

...

...

...

....

....

Am

Cm, 1

Cm, 2

......

Cm, n

Аm

B1

B2

Bn

Несбалансированную (открытую) транспортную задачу приводят к виду, показанному выше, искусственно: в модель вводятся так называемые фиктивный поставщик или фиктивный потребитель, которые балансируют спрос и потребление.

В настоящее время разработано множество различных алгоритмов решения транспортной задачи: распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, различные сетевые методы и т. д.

Производственно-транспортная задача

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

Такие задачи математически могут быть представлены в двух видах: в сетевой и в матричной постановке. Будучи основанными на принципах транспортной задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов.

II. Практический раздел

Задача №1

Для производства двух видов изделий А и В предприятие использует три вида сырья. Другие условия задачи приведены в таблице 1.1.

Вид сырья

Нормы расхода сырья на одно изделие, кг А В

Общее количество сырья, кг

I

12 4

300

II

4 4

120

III

3 12

252

Прибыль от реализации одного изделия, ден. ед

30 40

?

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

Решение.

Обозначим через х1 и х2 количество единиц продукции соответственно А и В, запланированных к производству. Для их изготовления потребуется (12 х1 +4х2 ) единиц ресурса I, (4х1 +4х2 ) единиц ресурса II, (3х1 +12х2 ) единиц ресурса III. Так как, потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

    4х1 +4х2 ? 120; х1 + х2 ? 30; 3х1 +12х2 ? 252. х1 +4х2 ? 84.

По смыслу задачи переменные

Х1 ? 0, х2 ?0. (1, 1)

Конечную цель решаемой задачи - получение максимальной прибыли при реализации продукции - выразим как функцию двух переменных х1 и х2.

Суммарная прибыль А составит 30х1 от реализации продукции А и 40х 2 от реализации продукции В, то есть:

F = 30х1 +40х 2. (1, 2)

Изобразим многоугольник решений данной задачи.

В ограничениях задачи поменяем знаки неравенства на знаки равенства.

Проведем оси: на горизонтальной будут указываться значения переменной х1, а на вертикальной -- х2.Далее рассмотрим условие неотрицательности переменных: x1 ? 0 и х2 ? 0. Эти два ограничения показывают, что пространство допустимых решений будет лежать в первом квадранте (т. е выше оси x1 и правее оси х2 ).

Чтобы учесть оставшиеся ограничения, проще всего заменить неравенства на равенства, в результате чего получится система уравнений прямых:

3х1 + х2 = 75;

Х1 + х2 = 30;

Х1 +4х2 = 84.

А затем на плоскости провести эти прямые.

Например, неравенство 3х1 + х2 ? 75 заменяется уравнением прямой 3х1 + х2 = 75. Чтобы провести эту линию, надо найти две различные точки, лежащие на этой прямой Можно положить х1 = 0, тогда х2 = 75/1 = 75.. Аналогично для х2 = 0 находим x1 = 75/3 = 25. Итак, наша прямая проходит через две точки (0, 75) и (25;0). Аналогично найдем остальные точки и запишем их в таблицу 1.2.

Заштрихованная область, изображенная на рисунке, является областью допустимых значений функции F. Т. к. целевая функция F стремиться к max, то идя по направлению вектора n, получим точку B с оптимальным решением. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:

Х1 + 4х2 ? 84, х2 = 16, 09., т. е. B(16, 09; 19, 64)

Максимальное значение линейной функции равно:

FMax = 30*16, 09 + 40*19, 64 = 1232, 80.

Итак, FMax = 1232, 80 при оптимальном решении х1 = 16, 09, х2 = 19, 64, т. е. максимальная прибыль в 1232, 80 ден. ед. может быть достигнута при производстве 16, 09 единиц продукции А и 19, 64 единиц продукции В.

Ответ: FMax = 1232, 80.

Задача № 2

Для изготовления двух видов продукции Р1 и Р2 используют три вида сырья: S1, S2, S3. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2.1.

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

Решение.

Обозначим через х1 количество единиц продукции Р1, а через х2 - количество единиц продукции Р2. Тогда, учитывая количество единиц сырья, расходуемое на изготовление продукции, а так же запасы сырья, получим систему ограничений:

    2х1 + 5х2 ? 20 8х1 + 5х2 ? 40 5х1 + 6х2 ? 30

Которая показывает, что количество сырья, расходуемое на изготовление продукции, не может превысит имеющихся запасов. Если продукция Р1 не выпускается, то х1 =0; в противном случае x1 = 0. То же самое получаем и для продукции Р2. Таким образом, на неизвестные х1 и х2Должно быть наложено ограничение неотрицательности: х1 ? 0, х2 ? 0.

Конечную цель решаемой задачи - получение максимальной прибыли при реализации продукции - выразим как функцию двух переменных х1 и х2. Реализация х1 единиц продукции Р1 и х2 единиц продукции Р2 дает соответственно 50х1 и 40х2 руб. прибыли, суммарная прибыль Z = 50х1 + 40х2 (руб.)

Условиями не оговорена неделимость единица продукции, поэтому х1 и х2 (план выпуска продукции) могут быть и дробными числами.

Требуется найти такие х1 и х2, при которых функция Z достинает максимум, т. е. найти максимальное значение линейной функции Z = 50х1 + 40х2 при ограничениях

    2х1 + 5х2 ? 20 8х1 + 5х2 ? 40 5х1 + 6х2 ? 30

Х1 ? 0, х2 ? 0.

Изобразим многоугольник решений данной задачи.

В ограничениях задачи поменяем знаки неравенства на знаки равенства.

Построим в программе Excelтаблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).

Заштрихованная область, изображенная на рисунке, является областью допустимых значений функции Z. Т. к. целевая функция Z стремиться к max, то идя по направлению вектора n, получим точку C с оптимальным решением. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:

5х1 + 6х2 ? 30, х2 = 1, 74., т. е. C(3, 91; 1, 74)

Максимальное значение линейной функции равно:

ZMax = 50*3, 91 + 40*1, 74 = 265, 10.

Итак, ZMax = 265, 10 при оптимальном решении х1 = 3, 91, х2 = 1, 74, т. е. максимальная прибыль в 1232, 80 ден. ед. может быть достигнута при производстве 3, 91единиц продукции P1 и 1, 74 единиц продукции P2.

Ответ: ZMax = 265, 10.

Задача № 3

Имеется два вида корма. A и B, содержащие вещества(витамины) S1, S2, S3. Содержание числа единиц питательных веществ в одном кг каждого вида корма и необходимый минимум самих питательных веществ даны в таблице:

Решение:

Пусть х1 и х2 - количество кормоввида А и В соответственно. В одном килограмме каждого вида корма содержится (3х1 + х2 ) единиц питательного вещества S1, (x1 + 2x2 ) - S2 и (x1 + 6x2 ) - S3. Так количество питательных веществ не должно быть меньше необходимого минимума, то запишем следующую систему неравенств:

3х1 + х2 ? 8,

X1 + 2x2 ? 9,

X1 + 6x2 ? 12,

X1, x2 ? 0.

Минимальную стоимость витаминов за 1 кг корма, выразим следующей функцией:

F = 4x1 + 6x2 => min.

Изобразим многоугольник решений данной задачи.

В ограничениях задачи поменяем знаки неравенства на знаки равенства.

Построим в программе Excel таблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).

Выделенная область, изображенная на рисунке, является областью допустимых значений функции F. Точка В - оптимальное решение. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:

X1 + 2x2 = 9, x1 = 7, 50,

X1 + 6x2 = 12, x2 = 0, 75.

Минимальное значение линейной функции равно:

FMin = 4*7.5 + 6*0.75 = 34.50.

Итак, FMin = 34.50 при оптимальном решении х1 = 7.50, х2 = 0.75.

Ответ: FMin = 34, 50.

Задача № 4

Трикотажная фабрика использует для производства свитеров и кофточек шерсть, силикон и нитрон, запасы которых составляют 820, 430 и 310 кг. Количество пряжи каждого вида (в кг), необходимой для изготовления одного изделия, а также прибыль, получаемая от их реализации, приведены в таблице.

Определить план выпуска изделий, максимизирующий прибыль.

Решение.

Пусть х1 и х2 - норма расхода пряжи для свитеров и кофточек соответственно. Количество пряжи каждого вида (в кг), необходимой для изготовления одного изделия запишем в следующую систему неравенств:

    0, 4х1 + 0, 2х2 ? 820, 0, 2x1 + 0, 1x2 ? 430, 0, 1x1 + 0, 1x2 ? 310,

X1, x2 ? 0.

Максимальная прибыль от реализации свитеров и кофточек выразим следующей функцией:

F = 7, 8x1 + 5, 6x2 => max.

Изобразим многоугольник решений данной задачи.

В ограничениях задачи поменяем знаки неравенства на знаки равенства.

Построим в программе Excel таблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).

Выделенная область, изображенная на рисунке, является областью допустимых значений функции F. Точка В - оптимальное решение. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:

    0, 4x1 + 0, 2x2 = 820, x1 = 1000, 0, 1x1 + 0, 1x2 = 310, x2 = 2100.

Максимальное значение линейной функции равно:

FMax = 7.8*1000 + 5.6*2100 = 19560.

Итак, FMax = 19560 при оптимальном решении х1 = 1000, х2 = 2100.

Ответ: FMax = 19560.

Задача № 5

На звероферме могут выращиваться черно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используются три вида кормов. Определить, сколько лисиц и песцов следует выращивать на звероферме, чтобы прибыль от реализации их шкурок была максимальной.

Решение:

Пусть х1 и х2 - количество единиц корма, которые должны получать лисиа и песец, соответственно. Количество единиц каждого вида корма, необходимого для выращивания одного животного запишем в следующую систему неравенств:

    2х1 + 3х2 ? 180, 4x1 + 1x2 ? 240, 6x1 + 7x2 ? 426,

X1, x2 ? 0.

Максимальная прибыль от реализации шкурок выразим следующей функцией:

F = 16x1 + 12x2 => max.

Изобразим многоугольник решений данной задачи.

В ограничениях задачи поменяем знаки неравенства на знаки равенства.

Построим в программе Excel таблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).

Выделенная область, изображенная на рисунке, является областью допустимых значений функции F. Точка С - оптимальное решение. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:

X2 = 0, x1 = 60,

4x1 + x2 = 240, x2 = 0.

Максимальное значение линейной функции равно:

FMax = 16*60 + 12*0 = 960.

Итак, FMax = 960 при оптимальном решении х1 = 60, х2 = 0.

Ответ: FMax = 960.

Похожие статьи




Транспортная задача - Линейное программирование

Предыдущая | Следующая