Орлов А.И. Менеджмент (2003) (1142166), страница 57
Текст из файла (страница 57)
Остаетсявзять максимальные границы по каждой переменной. Если многогранник,задаваемый ограничениями, неограничен, как было в задаче о диете, можнопохожим, но несколько более сложным образом выделить его "обращенную" кначалу координат часть, содержащую решение, и заключить ее в многомерныйпараллелепипед.Проведем перебор точек параллелепипеда с шагом 1/10n последовательнопри n=2,3,…, вычисляя значения целевой функции и проверяя выполнениеограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, вкоторой целевая функция максимальна. Решение найдено! (Более строговыражаясь, найдено с точностью до 1/10n.)Направленный перебор.
Начнем с точки, удовлетворяющей ограничениям(ее можно найти простым перебором). Будем последовательно (или случайно – спомощью т.н. метода случайного поиска) менять ее координаты на определеннуювеличину ∆, каждый раз в точку с более высоким значением целевой функции.Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну изкоординат по уравнению ограничения). Затем движение по ребру (когда дваограничения-неравенства переходят в равенства)… Остановка - в вершинелинейного многогранника.
Решение найдено! (Более строго выражаясь, найдено сточностью до ∆. Если необходимо, в окрестности найденного решения проводимнаправленный перебор с шагом ∆/2 , ∆/4 и т.д.)Симплекс-метод. Этот один из первых специализированных методовоптимизации, нацеленный на решение задач линейного программирования, в товремя как методы простого и направленного перебора могут быть применены длярешения практически любой задачи оптимизации. Симплекс-метод былпредложен американцем Г. Данцигом в 1951 г.
Основная его идея состоит впродвижении по выпуклому многограннику ограничений от вершины к вершине,при котором на каждом шаге значение целевой функции улучшается до тех пор,пока не будет достигнут оптимум. Разберем пример на основе данных табл.2.Рассмотрим задачу линейного программирования, сформулированнуювыше при рассмотрении оптимизации номенклатуры и объемов выпуска:F = 15 Х1 + 12 Х2 + 14 Х3 → max .Х1 / 200 + Х2 / 300 + Х3 / 120 ≤ 100 ,Х1 / 300 + Х2 / 100 + Х3 / 100 ≤ 100 ,Х3 / 80 ≤ 100 .Неотрицательность переменных не будем специально указывать, поскольку взадачах линейного программирования это предположение всегда принимается.В соответствии с симплекс-методом введем т.н.
"свободные переменные"Х4, Х5, Х6, соответствующие недоиспользованным мощностям, т.е. от системынеравенств перейдем к системе уравнений:Х1 / 200 + Х2 / 300 + Х3 / 120 + Х4 = 100 ,Х1 / 300 + Х2 / 100 + Х3 / 100 + Х5 = 100 ,Х3 / 80 + Х6 = 100 ,15 Х1 + 12 Х2 + 14 Х3 = F .У этой системы имеется очевидное решение, соответствующее одной из вершинмногогранника допустимых значений переменных:Х1 = Х2 = Х3 = 0, Х4 = Х5 = Х6 = 100, F = 0.В терминах исходной задачи это означает, что ничего не надо выпускать.
Такоерешение приемлемо только на период летних отпусков.В соответствии с симплекс-методом выбираем переменную, которая входитв целевую функцию F с самым большим положительным коэффициентом. Это Х1.Сравниваем частные от деления свободных членов в первых трехуравнениях на коэффициенты при только что выбранной переменной Х1:100 / (1/200) = 20000, 100 / (1/300) =30000, 100/0 = + ∞ .Выбираем строку из системы уравнений, которой соответствует минимальное извсех положительных отношений.
В рассматриваемом примере - это первая строка,которой соответствует отношение 20000.Умножим первую строку на 200, чтобы получить Х1с единичнымкоэффициентом:Х1 + 2/3 Х2 + 2/1,2 Х3 + 200 Х4 = 20000 .Затем умножим вновь полученную строку на (-1/300) и сложим со второй строкой,чтобы исключить член с Х1, получим7/900 Х2 + 4/900 Х3 - 2/3 Х4 + Х5 = 100/3.Ту же преобразованную первую строку умножим на (-15) и сложим со строкой, вправой части которой стоит F, получим:2 Х2 - 11 Х3 - 3000 Х4 = F - 300000.В результате система уравнений преобразуется к виду, в котором переменная Х1входит только в первое уравнение:Х1 + 2/3 Х2 + 2/1,2 Х3 + 200 Х4 = 20000 ,7/900 Х2 + 4/900 Х3 - 2/3 Х4 + Х5 = 100/3,Х3 / 80 + Х6 = 100 ,2 Х2 - 11 Х3 - 3000 Х4 = F - 300000.Очевидно, у новой системы имеется улучшенное по сравнению с исходнымрешение, соответствующее другой вершине выпуклого многогранника вшестимерном пространстве:Х1 = 20000, Х2 = Х3 = Х4 = 0, Х5 = 100/3, Х6 = 100, F = 300000.В терминах исходной задачи это решение означает, что надо выпускать толькокухни.
Такое решение приемлемо, если допустимо выпускать только один видпродукции.Повторим описанную выше операцию. В строке с F имеется еще одинположительный коэффициент - при Х2 (если бы положительных коэффициентовбыло несколько - мы взяли бы максимальный из них). На основе коэффициентовпри Х2 (а не при Х1, как в первый раз) образуем частные от делениясоответствующих свободных членов на эти коэффициенты:20000 / (2/3) = 30000, (100/3) / (7/900) = 30000/7, 100/0 = + ∞.Таким образом, нужно выбрать вторую строку, для которой имеем наименьшееположительное отношение 30000/7. Вторую строку умножим на 900/7 (чтобыкоэффициент при Х2 равнялся 1).
Затем добавим обновленную строку ко всемстрокам, содержащим Х2, предварительно умножив их на подходящие числа, т.е.такие, чтобы все коэффициенты при Х2 стали бы после сложения равны 0, заисключением коэффициента второй строки, который уже стал равняться 1.Получим систему уравнений:= 120000/7 ,Х1 + 9/7 Х3 + 1800/7 Х4 - 600/7 Х5Х2 + 4/7 Х3 - 600/7 Х4 + 900/7 Х5= 30000/7,Х3 / 80+ Х6 = 100 ,- 85/7 Х3 - 19800/7 Х4 - 1800/7 Х5= F - 308571.Поскольку все переменные неотрицательны, то из последнего уравнения следует,что прибыль F достигает своего максимального значения, равного 308571, при Х3= Х4 = Х5 = 0.
Из остальных уравнений следует, что при этом Х1 = 120000/7 =17143, Х2 = 30000/7 = 4286, Х6 = 100. Поскольку в строке с F не осталось ниодного положительного коэффициента при переменных, то алгоритм симплексметода закончил свою работу, оптимальное решение найдено.Практические рекомендации таковы: надо выпустить 17143 кухни,вчетверо меньше, т.е. 4286, кофемолок, самоваров не выпускать вообще. При этомприбыль будет максимальной и равной 308571.
Все производственноеоборудование будет полностью загружено, за исключением линии по сборкесамоваров.Транспортнаязадача.Различныетехнико-экономическиеиэкономические задачи менеджмента, от оптимальной загрузки станка и раскройкистального листа или полотна ткани до анализа межотраслевого баланса и оценкитемпов роста экономики страны в целом, приводят к необходимости решения техили иных задач линейного программирования.
В книге [1] приведен обширныйперечень публикаций, посвященный многочисленным применениям линейногопрограммирования в металлургии, угольной, химической, нефтяной, бумажной ипрочих отраслях промышленности, в проблемах транспорта и связи, планированияпроизводства, конструирования и хранения продукции, сельском хозяйстве, внаучных исследованиях, в том числе экономических, и даже при регулированииуличного движения.В качестве очередного примера рассмотрим т.н.
транспортную задачу.Имеются склады, запасы на которых известны. Известны потребители и объемыих потребностей. Необходимо доставить товар со складов потребителям. Можнопо-разному организовать "прикрепление" потребителей к складам, т.е. установить,с какого склада какому потребителю и сколько вести. Кроме того, известнастоимость доставки единицы товара с определенного склада определенномупотребителю.
Требуется минимизировать издержки по перевозке.Например, может идти речь о перевозке песка - сырья для производствакирпичей. В Москву песок обычно доставляется самым дешевым транспортом водным. Поэтому в качестве складов можно рассматривать порты, а в качествезапасов - их суточную пропускную способность. Потребителями являютсякирпичные заводы, а их потребности определяются суточным производством (всоответствии с имеющимися заказами). Для доставки необходимо загрузитьавтотранспорт, проехать по определенному маршруту и разгрузить его. Стоимостьэтих операций рассчитывается по известным правилам, на которых не имеетсмысла останавливаться.
Поэтому затраты на доставку товара с определенногосклада тому или иному потребителю можно считать известными.Рассмотрим пример транспортной задачи, исходные данные к которойпредставлены в табл. 3. В ней, кроме объемов потребностей и величин запасов,приведены стоимости доставки единицы товара со склада i, i = 1,2,3, потребителюj, j = 1,2,3,4. Например, самая дешевая доставка - со склада 2 потребителям 1 и 3, атакже со склада 3 потребителю 2. Однако на складе 2 имеется 80 единиц товара, апотребителям 1 и 3 требуется 50+70 =120 единиц, поэтому к ним придется веститовар и с других складов.
Обратите внимание, что в табл.3 запасы на складахравны суммарным потребностям. Для примера с доставкой песка кирпичнымзаводам это вполне естественное ограничение - при невыполнении такогоограничения либо порты будут засыпаны горами песка, либо кирпичные заводы невыполнят заказы.Склад 1Склад 2Склад 3ПотребностиПотребитель 121350Таблица 3.Исходные данные к транспортной задаче.ПотребиПотребиПотребиЗапасы натель 2тель 3тель 4складах555602148015260407040200Надо спланировать перевозки, т.е. выбрать объемы Хij поставок товара со склада iпотребителю j , где i = 1,2,3; j = 1,2,3,4. Таким образом, всего в задаче имеется 12переменных.
Они удовлетворяют двум группам ограничений. Во-первых, заданызапасы на складах:X11 + Х12 + Х13 + Х14 = 60 ,X21 + Х22 + Х23 + Х24 = 80 ,X31 + Х32 + Х33 + Х34 = 60 .Во-вторых, известны потребности клиентов:X11 + Х21 + Х31 = 50 ,X12 + Х22 + Х32 = 40 ,X13 + Х23 + Х33 = 70 ,X14 + Х24 + Х34 = 40 .Итак, всего 7 ограничений типа равенств. Кроме того, все переменныенеотрицательны - еще 12 ограничений.Целевая функция - издержки по перевозке, которые необходимоминимизировать:F = 2 X11 + 5 Х12 + 4 Х13 + 5 Х14 + X21 + 2 Х22 + Х23 + 4 Х24 ++ +3 X31 + Х32 + 5 Х33 + 2 Х34 → min .Кроме обсуждаемой, рассматриваются также различные иные вариантытранспортной задачи. Например, если доставка производится вагонами, то объемыпоставок должны быть кратны вместимости вагона.Количество переменных и ограничений в транспортной задаче таково, чтодля ее решения не обойтись без компьютера и соответствующего программногопродукта.Линейное программирование имеет дело с числовыми переменными.
Есливспомнить общую постановку оптимизационной задачи, приведенную в началеглавы, то Х – вектор в конечномерном линейном пространстве, А – многогранникв таком пространстве. Рассмотрим несколько задач оптимизации, в которых Х и Аимеют иную математическую природу.3.2.2. Целочисленное программированиеЗадачи оптимизации, в которых переменные принимают целочисленныезначения, относятся к целочисленному программированию. Рассмотрим несколькотаких задач.Задача о выборе оборудования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
