golunova_l_v_matematicheskie_modeli_v_transportnyh_raschetah

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

21.Хлебозавод производит два типа торта «БИС» и «КВИТ». Для производства 1 т «БИТ» требуется 0,3 ч работы оборудования, а для «КВИТ» – 0,5 ч. Расход специального ингредиента на них составляет 0,4 и 0,1 т на 1 т соответственно. Ежедневно в распоряжении завода 12 т специального ингредиента и 15 ч работы оборудования. Доход от продажи 1 т торта «БИС» составляет 20 тыс. руб., а «КВИТ» – 31 тыс. руб. Определите ежедневный план производства тортов каждого вида, обеспечивающий максимальный доход от их продажи.

22.Фирма производит две модели шкафов – А и В. Их производство ограничено наличием сырья (высококачественных до-

сок) и временем машинной обработки. Для каждого изделия модели A требуется 3 м2 досок, а для изделия модели B – 4 м2. Фирма может получать от своих поставщиков до 1700 м2 досок в неделю. Для каждого изделия модели A требуется 12 мин машинного времени, а для изделия модели B – 30 мин. В неделю можно использовать 160 ч машинного времени. Сколько изделий каждой модели следует выпускать фирме в неделю, если каждое изделие модели A приносит 2 руб. прибыли, а каждое изделие модели B – 4 руб. прибыли?

23.Издательский дом «Садовод» издает два журнала: «Пчеловод» и «Сад и огород», которые печатаются в трех типографиях: «Типография МК», «Полиграф» и «Труд», где общее количество часов, отведенное для печати, и производительность печати одной тысячи экземпляров ограничены и представлены в таблице. Спрос на журнал «Пчеловод» составляет 12 тыс. экз. а на журнал «Сад и огород» – не более 14 тыс. экз. в месяц. Определите, какое оптимальное количество журналов надо изда-

111

вать, чтобы обеспечить максимальную выручку от продажи.

24. Для изготовления двух видов продукции Р1 и Р2 используют следующие ресурсы: S1, S2, S3, S4. Запасы ресурсов и затраты каждого на единицу продукции приведены в таблице. Прибыль, получаемая от единицы продукции P1 и P2, – соответственно 2 и 5 руб. Составьте такой план производства продукции, при котором прибыль от её реализации будет максимальной.

25. Автотранспортному предприятию (АТП) необходимо освободить из-под груза складские помещения клиента. Вывоз груза следует осуществить в два рейса колоннами автомобилей. Условия перевозки требуют, чтобы в составе каждой колонны, предназначенной для вывоза груза в первый район, было 8 автомобилей ЗИЛ-131 и 8 автомобилей ЗИЛ-130; в колоннах второго рейса 8 автомобилей ЗИЛ-130 и 16 – МАЗ-500. Каждая из колонн может сделать за сутки одинаковое количество поездок. Парк подвижного состава АТП состоит из 32 автомобилей ЗИЛ-131 грузоподъемностью 3 т, 48 автомобилей ЗИЛ-130 грузоподъемностью 4 т, 48 автомобилей МАЗ-500 грузоподъемностью 7,5 т. Определите количество колонн, которое нужно направить в каждый район, чтобы перевезти наибольшее количество груза.

112

3.5.2. Графический метод решения задач

Найдите графическим методом решение следующих задач линейного программирования.

113

114

4. РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

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

-прикрепления потребителей ресурсов к производителям;

-привязки пунктов отправления к пунктам назначения;

-взаимной привязки грузопотоков прямого и обратного направлений;

-отдельных задач оптимальной загрузки промышленного оборудования и др.

Общим для всех транспортных задач является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов.

4.1. ПОСТАНОВКА ЗАДАЧИ

Рассмотрим математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются m пунктов отправления груза и объемы отправления по каждому пункту а1, а2, ..., аm. Известна потребность в грузах b1, b2, ..., bn по каждому из n пунктов назначения. Задана матрица стоимостей доставки по каждому варианту cij, i = 1, m, j = 1, n . Необходимо

115

рассчитать оптимальный план перевозок, то есть определить, сколько груза xij должно быть отправлено из каждого i-го пункта отправления (от поставщика) в каждый j-й пункт назначения (до потребителя) с минимальными транспортными издержками. В общем виде исходные данные представлены в таблице 4.1.

Таблица 4.1

Исходные данные

Транспортная задача называется закрытой, если суммар-

m

ный объем отправляемых грузов (∑ ai) равен суммарному объ-

i=1

n

ему потребности в этих грузах по пунктам назначения (∑ bj):

Если такого равенства нет (потребности выше запасов или наоборот), задачу называют открытой, то есть:

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

1) Все грузы из i-х пунктов должны быть отправлены:

j=1

2)Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме:

i=1

116

3) Суммарные объемы отправления должны быть равны суммарным объемам назначения:

4)Должно выполняться условие неотрицательности переменных:

В модели (4.3)–(4.6) вместо матрицы стоимостей перевозок cij могут быть заданы матрицы расстояний. В таком случае в качестве целевой функции рассматривается минимум суммарной транспортной работы.

Согласно выражению (4.5) уравнение баланса является обязательным условием решения транспортной задачи. Поэтому, когда в исходных условиях дана открытая задача, то её необходимо привести к закрытой форме. В случае если

-потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;

-запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.

Варианты, связывающие фиктивные пункты с реальными,

имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая.

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

-нахождение исходного опорного решения;

-проверка этого решения на оптимальность;

-переход от одного опорного решения к другому.

117

4.2. АЛГОРИТМ МЕТОДА ПОТЕНЦИАЛОВ

Наиболее распространенным методом решения транспортных задач является метод потенциалов. Алгоритм этого метода рассмотрим на примере решения конкретной задачи: прикрепление пунктов отправления i = 1, 3 к пунктам назначения j = 1, 4 . В соответствии с принятыми выше обозначениями исходные данные задачи приведены в таблице 4.2.

Для транспортной задачи существует несколько способов нахождения исходного опорного решения:

-метод северо-западного угла;

-метод минимальной стоимости;

-метод двойного предпочтения и т. д.

Рассмотрим один из них – метод северо-западного угла.

Согласно этому методу распределение объемов пунктов отправления по пунктам назначения начинается с верхней левой клетки («северо-западная» часть таблицы) и продолжается вниз и вправо (по диагонали). Распределение начинаем с клетки (i–j) = (1–1) на основании следующего условия:

x11 = min{a1; b1} = min{60; 40} = 40.

Таким образом, первый пункт назначения загружен, а первый пункт отправления имеет остатки груза ∆a1 = 60 – 40 = 20,

Процесс распределения всегда продолжают до тех пор, по-

118

ка все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены.

В процессе решения после каждого этапа (в том числе и после получения допустимого решения) по загруженным клеткам проверяется выполнение следующего условия:

N = m + n – 1. (4.7)

В нашем примере m = 3, n = 4, а число загруженных клеток равно 6, то есть соответствует условию (4.7): N = 3 + 4 – 1 = 6. Если условие (4.7) не выполняется, план называется вырожденным. В этом случае недостающее число загруженных клеток дополняется клетками с нулевыми поставками, которые называются условно занятыми, таким образом, чтобы выполнялось условие (4.7).

Результаты начального плана и расчета потенциалов представлены в таблице 4.3.

Таблица 4.3

Исходное опорное решение

Стоимость перевозки при исходном опорном решении составляет:

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

αi + βj = cij, (4.8)

где αi – потенциал i-ой строки; βj – потенциал j-го столбца.

Для первой строки принимаем αi=0. Рассматривая загру-

119

женные клетки (i–j) = (1–1), (1–2), получаем:

α1 + β1 = c11 = 0 + β1 = 1; β1 = 1.

α1 + β2 = c12 = 0 + β2 = 2; β2 = 2.

Далее по загруженным клеткам (2–2), (2–3) определяем другие потенциалы:

α2 + β2 = 3; α2 + 2 = 3; α2 = 1;

α2 + β3 = 2; 1 + β3 = 2; β3 = 1 и т. д.

Найденные значения потенциалов заносим в таблицу 4.3. По незагруженным клеткам проверяем, является ли реше-

Если условие (4.9) для незагруженных клеток выполняется, то найденное решение является оптимальным. По таблице 4.3 осуществляем проверку начального плана на оптимальность:

(∆cij) говорит о том, что полученное решение не оптимально и для уменьшения значения целевой функции надо перейти к другому опорному решению. При этом надо перераспределить грузы, перемещая их из загруженных клеток в незагруженные.

Характеристики ∆сij показывают размер экономии транспортных издержек на 1 ед. перевозимого груза. В нашем примере наибольшую экономию можно получить по клетке (i–j) = (3–1), где ∆с31 = 2 > {∆с24; ∆с32}. Следовательно, клетку (3–1) необходимо загрузить за счет перераспределения ресурсов из других загруженных клеток. В таблице 3 клетку (3–1) помечаем знаком «+», так как здесь в исходном опорном решении находится вершина максимальной неоптимальности, которая будет одной из вершин контура. Далее, начиная с клетки (3–1), строим контур по следующим правилам:

1)контур представляет собой замкнутый многоугольник с вершинами в загруженных клетках (за исключением клетки с

120