Файл: Учебнометодическое пособие по дисциплине Логистика производства для инженеров техники и технологий по специальности 230104 Системы автоматизированного проектирования.pdf

62 количестве должен поставлять руду соответствующим комбинатам, чтобы обеспечить полную загрузку их производственной мощности.
Пусть имеется 4 рудных карьера и 5 ГОК, мощности и схемы связей которых представлены на рис. 3.3. Необходимо организовать схему снабжения горно-обогатительных комбинатов рудой, которая добывается на этих рудниках. Слева на рисунке показаны мощности карьеров, справа – мощности горно-обогатительных комбинатов. Цифры на стрелках показывают объемы перевозок между рудниками и комбинатами, которые обеспечивают решение данной задачи.
Решение задач такого типа осуществляется методом «северо-западного угла», с помощью матрицы, показывающей связи рудных карьеров и горно- обогатительных комбинатов. Связи между рудниками и комбинатами отображает матрица, в которой строки соответствуют карьерам, столбцы – комбинатам, а элементы – маршрутам между ними:
ГОК
1 2
3 4
5
Рудник
200 300 800 700 200 1
400 200 200 2
500 100 400 3
1000 400 600 4
300 100 200
Если полагать, что верх матрицы – «север», слева «запад», справа –
«восток», а внизу «юг», то верхний левый элемент матрицы – это и есть
«северо-западный угол». Начинаем с него – пусть первый рудник поставит на первый
ГОК столько руды, чтобы загрузить максимально его

63 производительность (мощность). Можно видеть, что для загрузки мощности
ГОК-1 достаточно половины добычи Рудника-1, т.е. в первом элементе запишем 200. Это поток руды с Рудника-1, который полностью загрузит мощность на ГОК-1.
Тогда оставшуюся добычу Рудника-1 отправим на следующий ГОК-2, т.е. переходим к элементу в соседнем столбце, куда запишем 200. Это полностью заберет добычу Рудника-1, но не полностью загрузит мощность ГОК-2. Тогда по столбцу 2 спускаемся на строку 2 и заберем добычу Рудника-2, чтобы загрузить мощности ГОК-2. Нам не хватает здесь 100 единиц массы (допустим,
100 тыс. т) добытой руды. Мы их запишем в элемент матрицы связи Рудника-2 и ГОК-2, для которого получаем полную загрузку.
Но мощность Рудника-2 еще не полностью распределена, поэтому переходим в столбец 3, соответствующий ГОК-3. Этот комбинат заберет весь выпуск Рудника-2 (пишем в этот элемент матрицы значение 400), но этого ему не хватит. Тогда переходим вниз, на строку Рудника-3, где добираем недостающую руду для ГОК-3. И так продолжаем до тех пор, пока не распределим всю руду между комбинатами, т.е. пока не создадим логистическую цепь. Результаты этой работы представлены в элементах матрицы – от ее «северо-западного угла» до «юго-восточного угла» (стрелки показывают направление поиска), а также отображены в квадратах на стрелках связи рис. 3.3.
Это достаточно простая задача. Во-первых, она сбалансирована, т.е. суммарная мощность рудников равна суммарной мощности комбинатов. Во- вторых, мы не задали условий по маршрутам и способам транспортировки руды, а здесь затраты на единицу продукции могут существенно отличаться друг от друга. В рыночной экономике целью производства является увеличение прибыли, поэтому необходим выбор партнеров, поставщиков, маршрутов.
3.3. Оптимальный план транспортировки продукции
Задача перевозки руды (и аналогичные ей) существенно усложняется, если задана стоимость перевозки по каждому пути и необходимо минимизировать расходы на транспортировку продукции. Если такую задачу решить, то мы получим оптимальный по затратам план транспортировки продукции.
Транспортная задача оптимизации перевозки продукции может иметь следующую формулировку. Пусть несколько рудников (карьеров) отгружают добытую рудную продукцию на насколько горно-обогатительных комбинатов
(ГОК). Их связывают маршруты перевозки, по каждому из которых задана своя цена доставки тонны груза. Необходимо доставить всю руду, загрузить все мощности комбинатов и при этом выбрать такие маршруты перевозок, чтобы обеспечить минимальную стоимость доставки грузов.
Возможны другие варианты постановки данной задачи. Например, вся добыча руды меньше, чем суммарная мощность комбинатов. При этом цена получения единицы конечного продукта на разных комбинатах разная. Тогда надо определить маршруты доставки с минимальной стоимостью транспортировки с максимальной загрузкой тех комбинатов, на которых
PDF created with pdfFactory Pro trial version www.pdffactory.com

64 стоимость получения конечного продукта наименьшая. Или суммарная добыча руды превышает суммарную мощность комбинатов. Тогда надо вводить склад для запаса продукции или рассматривать варианты экспорта излишков руды.
Простой способ связать рудники и комбинаты, чтобы обеспечить всю руду мощностями по переработке (обогащению, выплавке металла), мы уже рассмотрели в предыдущем примере. Другие варианты транспортировки, поиск оптимального варианта и вообще расходы на перевозку там не рассматривали.
Теперь будем решать задачу оптимизации перевозок, а это один из видов задач линейного программирования.
Задача линейного программирования в классической постановке имеет следующий вид: надо максимизировать значение целевой функции, и при этом значения переменных должны удовлетворять ряду ограничений.
Целевая функция имеет вид:
Максимизировать
Σ c
j
x
j
=> max, (3.1) где i = 1, m; j = 1, n.
Система ограничений задана в виде совокупности неравенств:
Σ a
ij
x
j
< b
i
. (3.2)
Все переменные принимают только неотрицательные значения:
x
j
> 0. (3.3)
Рассмотрим простой пример постановки такой задачи. Пусть необходимо максимизировать целевую функцию (получение прибыли):
4 x
1
+ 5 x
2
+ 9 x
3
+ 11 x
4
=> max
При ограничениях, заданных системой неравенств: человеко-недели – 1 x
1
+ 1 x
2
+ 1 x
3
+ 1 x
4
< 15 материал А – 7 x
1
+ 5 x
2
+ 3 x
3
+ 2 x
4
< 120, материал Б – 3 x
1
+ 5 x
2
+ 10 x
3
+ 15 x
4
< 100, x
1
> 0, x
2
> 0, x
3
> 0, x
4
> 0.
Для решения этой задачи удобно использовать известный в линейном программировании симплекс-метод. Суть этого метода в том, что систему ограничений в виде неравенств можно представить многогранником в многомерном пространстве. Целевая функция задает гиперплоскость в этом пространстве. Переходя по граням многогранника (полиэдра) можно достичь его вершины, в которой целевая функция принимает максимальное (или минимальное – для двойственной постановки задачи) значение. Решение может не существовать, также возможно несколько оптимальных решений.
Допустим, что решение существует, причем оптимальное значение целевой функции конечное. Поскольку переменных больше, чем ограничений, то сначала выбирают базисное решение, в котором каждая переменная соответствует одному ограничению. Базисные переменные выбирают так,
PDF created with pdfFactory Pro trial version www.pdffactory.com

65 чтобы получить первоначальное допустимое решение. Примером такого решения могло бы служить решение, полученное методом «северо-западного угла». Все остальные переменные называют небазисными переменными; их значения полагают равными нулю. Затем улучшают базисное решение.
Алгоритм симплекс-метода
Алгоритм симплекс-метода для поиска оптимума применяет четыре шага и использует два критерия. Систему неравенств первоначально приводят к системе равенств путем введения так называемых свободных переменных.
Шаги алгоритма симплекс-метода
Шаг 1. Выбор исходного (пробного) базиса.
Шаг 2. Используется критерий 1. Если полученное решение не оптимально, то переходим к шагу 3. Иначе останов – решение получено.
Шаг 3. Выполняется процедура преобразования задачи по критерию 2.
Шаг 4. Производится смена базиса и переход к шагу 2.
Критерии алгоритма симплекс-метода
Симплекс-критерий 1 (максимизация). Если в строке 0, представляющей целевую функцию, есть небазисные переменные, при которых коэффициенты меньше нуля, то следует выбрать переменную с наибольшим абсолютным значением стоящего перед ней коэффициента (который обеспечивает наибольшее удельное приращение целевой функции).
Если все небазисные переменные в строке целевой функции имеют положительные или нулевые коэффициенты, то оптимальное решение можно считать полученным.
Симплекс-критерий 2. а) Рассмотрим отношения чисел, стоящих в правых частях системы ограничений, к соответствующим коэффициентам при новой базисной переменной (не обращая внимания на те, где знаменатель равен нулю или меньше нуля). б) Выберем среди них отношение с наименьшим значением – приравняем к нему новую базисную переменную в очередном пробном решении. Взамен этого выводим из базисного решения и полагаем равной нулю ту переменную из старого базисного решения, для которой отношение правой части уравнения и коэффициента при новой переменной имеет наименьшее значение.
Для реализации алгоритма симплекс-метода вводим в каждое ограничение так называемую свободную переменную, которая превращает неравенство в равенство. Таким образом, вместо системы неравенств получаем систему равенств. Решение задачи начинается с того, что именно эти свободные переменные включаем в исходный пробный базис.
Содержание шагов алгоритма симплекс-метода
Каждый пробный базис соответствует вершине выпуклого полиэдрального множества решений. Переход от одного базиса к другому геометрически
PDF created with pdfFactory Pro trial version www.pdffactory.com

66 выглядит как переход от одной экстремальной точки к другой (причем смежной) экстремальной точке. Таким образом, осуществляется переход, последовательное восхождение вдоль ребер многогранника от одной вершины к соседней. И так до достижения наиболее высокой точки, соответствующей оптимальному решению. Заметим еще раз, что возможно более одного оптимального решения.
Смысл выполнения этих шагов и применения критериев следующий.
Шаг 1. Для начала выбирают m переменных, задающих допустимое пробное решение задачи (примером является решение, полученное методом северо-западного угла). Это решение не противоречит ограничениям и дает какое-то (не всегда оптимальное) значение целевой функции. Выбранные для пробного решения переменные исключают из выражения для целевой функции.
Шаг 2. Необходимо проверить, можно ли за счет одной из переменных, приравненных к нулю, улучшить значение целевой функции? Применяется симплекс критерий 1.Для этого такой переменной придают положительные значения, наблюдая, как при этом меняется значение целевой функции.
Шаг 3. Применяется симплекс-критерий 2.Ищем предельное значение переменной, за счет которой можно улучшить значение целевой функции. Если это возможно, то выбирают новый базис, включающий эту переменную.
Увеличение значения этой переменной допустимо до тех пор, пока одна из переменных, вошедших в пробное решение, не обратится в нуль. Эту переменную исключаем из выражения для целевой функции. Вводим в пробное решение ту переменную, за счет которой результат можно улучшить.
Шаг 4. Разрешим систему m уравнений относительно переменных, вошедших в новое пробное решение. Последовательно исключим эти переменные из выражения для целевой функции. Вернемся к шагу 2.
Данный алгоритм приводит к оптимальному решению любой модели линейного программирования за конечное число итераций.
При решении задач логистического (организационного) управления с помощью линейного программирования бывает недостаточно знать численные значения переменных, при которых достигается оптимум. Обычно руководитель желает знать, в каком интервале можно менять входные параметры без существенного отклонения от найденного оптимума, и нарушения структуры базиса оптимального решения. Решение таких вопросов называется анализом модели на чувствительность. Например, к каким последствиям приведет снижение объема ресурсов? К чему приведет введение новой управляемой переменной? Изменится ли оптимальность при уменьшении удельного вклада в прибыль одной из базисных переменных и т.д.?
Для решения проблем чувствительности разработаны и применяются необходимые методы, включаемые в соответствующие пакеты прикладных программ. Например, классификационный анализ проводит ранжировку коэффициентов в целевой функции. Используются также специальные приемы вычислений, такие как метод присоединенной целевой функции (ряд линейных моделей с собственными критериями эффективности); параметрическое программирование (поиск решений при отклонениях в правых частях
PDF created with pdfFactory Pro trial version www.pdffactory.com