Гурский Д., Турбина Е. - Вычисления в MathCad 12 (1077322), страница 96
Текст из файла (страница 96)
Найти условный экстремум функции f(x,y)=sin(x)-sin(y)при х+у=0f(x,y):=sin(x)-sin(y)х:=1у:=1Givenх+ у = 0Minimize(f,x,y) =-1.57111.571В заключение еще раз повторю, что к результату работы функций Maximize и Minimizeследует относиться предельно осторожно и по возможности проводить проверку, иначе частые ошибки практически неизбежны.13.4. Линейное программирование(решение задач оптимизации)Линейным программированием называется раздел математики, который занимаетсяпроблемами минимизации линейной функции конечного количества переменных,428 *Глава 13.
Исследование функций и оптимизацияудовлетворяющих набору ограничений в виде линейных уравнений или неравенств. Линейное программирование является основным аппаратом в теории оптимального принятия решений в первую очередь в задачах экономического планирования.Впервые задачи линейного программирования сформулировал советский математикЛ. В. Канторович, за что впоследствии получил Нобелевскую премию по экономике.В настоящее время для решения задач данного типа разработано сложнейшее программное обеспечение, позволяющее эффективно анализировать входные данныебольших объемов и получать достоверный результат.В общем виде задача линейного программирования формулируется следующим образом: необходимо определить неизвестные величины х,, х2,...хп, при которых функцияf(x) = c, -х, + с 2 -х2 + ...
+ с п - х пназываемая целевой, принимает минимальное значение при условии принадлежностипеременных некоторой области, определяемой системой линейных равенствan.x1a+mfxia12.x2+...+ a+m 2 x 2 + ••ainxn=bl+ amn"xn- b mи их неотрицательности:Y > 0Y > ПY> ООписанная формулировка задачи линейного программирования называется канонической. Именно к такому виду должна быть приведена задача, чтобы для ее решения можнобыло применить один из численных методов оптимизации. На практике же ограничения для переменных могут быть представлены в форме равенств, неравенств различныхзнаков и даже комбинации равенств и неравенств.
Однако все они путем несложных приемов сводятся к ограничениям двух видов: равенствам и условиям неотрицательности.Наиболее распространенным и универсальным методом решения задач оптимизацииявляется так называемый симплекс-метод, позволяющий найти оптимальное решениеза (2-3)т итерации, где m — количество равенств-ограничений.Решение задач линейного программирования в Mathcad имеет несколько тонкостей, связанных прежде всего с заданием условия. В остальном же проблемы, которые могутвозникнуть при работе с ними, связаны со слабостями функций экстремумов Maximizeи Minimize и будут характерны для всех задач, в которых функции эти используются.Поэтому останавливаться на них, ввиду того, что способы разрешения таких трудностей были весьма подробно рассмотрены в двух предыдущих подразделах, мы не будем.Следуя избранному стилю, изучим решение задач линейного программирования, просто найдя условие оптимизации конкретной практической задачи.Одним из самых распространенных типов задач линейного программирования являются задачи, связанные с минимизацией транспортных или складских расходов, максимизацией прибыли за счет удачного распределения товара.
Типичная задача оптимизации ставит условие приблизительно следующим образом.Пусть в районе есть три свинофермы (в колхозе «Путь Ильича», в совхозе «Подольский»и у фермера Забутько). Предприниматель Иванов хочет купить у них мясо и перерабо-13.4. Линейное программирование (решение задач оптимизации)* 429тать его в тушенку для последующей продажи службам армии. Сделать это можнона двух мясокомбинатах, расположенных в соседних районах. Мясокомбинаты государственные, поэтому и цена переработки одинакова. И совхоз, и колхоз, и фермерсогласны продать свинину по одной и той же цене. Проблема выбора переработчикав том, что один из них, расположенный ближе к производителям, может принять оченьограниченный заказ (всего 20 т). Другой же, хоть и может переработать любое количество мяса, находится довольно далеко.
Перевозка же свиней на 1 км увеличивает стоимость сырья на $1,2 на каждую тонну. Задача состоит в том, чтобы распределитькупленных свиней между перерабатывающими предприятиями так, чтобы транспортные расходы были минимальными.Информацию о количестве мяса, купленного у каждого производителя, и расстоянииот последних до каждого из мясокомбинатов можно узнать из табл. 13.1.Таблица 13.1. Данные о поставщиках и переработчикахПоказателиКолхозСовхозФермерКуплено мяса, тонн121924Расстояние до первогомясокомбината, км321254Расстояние до второгомясокомбината, км160144199Итак, попробуем найти для предпринимателя оптимальный путь распределения сырьяс помощью Mathcad.1. Для начала представим исходные данные в наиболее приемлемом для обработкипрограммой виде — как матрицы или векторы.
В первую очередь зададим вектор Fраспределения сырья и вектор МК объемов возможной приемки данного сырьямясокомбинатами. Очевидно, что, так как первый мясокомбинат ближе ко всемпроизводителям, то везти на него сырье выгоднее, поэтому загрузить его следует помаксимуму.
То мясо, которое не сможет взять первый мясокомбинат, придется везти на второй.F:=F19I =МК:=55ЪЪМК=552. Далее зададим матрицу расстояний, в строках которой будут расположены соответствующие расстояния от производителей до данного мясокомбината. На этом жеэтапе определим коэффициент транспортных расходов, равный увеличению стоимости продукции при перевозке тонны сырья на 1 км:TR:=1.2RasP :=321254160 144 199.4 3 0 • Глава 13. Исследование функций и оптимизация3.
Когда все исходные данные определены, нужно задать функцию, минимизация которой будет производиться. Функция эта, исходя из условий задачи, должна определять транспортные расходы. Ее переменные, очевидно, должны быть определеныкак объемы сырья, перевезенные от каждого производителя к каждому переработчику. Нетрудно догадаться, что переменных таких будет 6 (с каждой из трех фермсвиньи могут быть перевезены на два мясокомбината). Сумма же произведений ихзначений и величин стоимости перевозки 1 т по данному маршруту определит полные транспортные расходы:last(MK) last(F)f(x):= £RasPZi=0ijV T Rj=04. Далее создаем вычислительный блок введением ключевого слова Given. В нем требуется определить все условия распределения переменных. Так, первые три уравнения устанавливают связь между двумя переменными, соответствующими объемамсырья, отправленным каждому из производителей, с общим количеством купленного мяса:*0,0 +xl,0=F0XXl)l=Fl0,l+*о,2 + К,гiЕще два уравнения связывают количество сырья, которое предстоит переработатькаждому из мясокомбинатов, с переменными, отвечающими за долю каждого из производителей в этом количестве:Также при определении условий требуется ввести ограничение на отрицательныезначения переменных.
Если этого не сделать, то почти наверняка матрица решенийбудет содержать отрицательные элементы, что делает такое решение заведомо неверным:^.О^0V-0*1,2* 05. Как вы помните, обязательным условием работы вычислительного блока являетсяопределение начальных значений переменных. Однако в случае работы с системами подобного рода совсем не нужно приближать все шесть переменных. Достаточно это сделать для одной (выражаясь более корректно, для одного элемента матрицыпеременных) — с наибольшими значениями индексов. Это поможет одновременнои определить порядок неизвестных, и задать размерность матрицы ответа.
Так,в случае данной задачи выше ключевого слова Given указываем:13.4. Линейное программирование (решение задач оптимизации)• 4316. Далее, используя функцию Minimize, определяем матрицу, содержащую информацию о наиболее выгодном распределении сырья:S := Minimize(f, x)О 0 20"" .12 19 4Проверим для начала, соответствует ли такое распределение имеющемуся реальносырью:Да, это действительно так. Определим теперь сумму транспортных расходов.
Наиболее просто это можно сделать, перемножив соответствующие друг другу элементы матрицы решения и матрицы расстояний, и умножив это произведение на коэффициенттранспортных расходов. Очевидно, что такие перемножения нельзя задать с помощьютрадиционного перемножения матриц. Для того чтобы произвести эту операцию нужным нам образом, воспользуемся специальным оператором векторизации (Vectorize)панели Matrix (Матричные) (подробнее об этом операторе вы можете прочитать в гл. 3):Pay :=((RasP-S))-TRО.2.304x1001.296 хЮ 33.283x10955.2SumPay :=SumPay = 7.838x10 3Анализируя матрицу ответа, нельзя не согласиться, что распределить сырье по такомупринципу было бы весьма разумно.При решении задач линейного программирования принципиальным условием успехаявляется то, какой численный алгоритм вы используете. Впрочем, правильный выборсделать совсем не сложно. Само прилагательное «линейное» подсказывает, какой изметодов следует выбрать в контекстном меню функции Minimize: Linear.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
