Этюд 2.
Оптимизация, или Поэма о пожарном ведре
Рис. 2.1. Задача о пожарном ведре:
схема решения
Рис. 2.2. Решение задачи о пожарном
ведре
Рис. 2.3. Решение задачи о двух
пожарных ведрах
Рис. 2.4. Решение задачи о коробке
Рис. 2.5. Решение задачи о коробках
I
Рис. 2.6. Решение задачи о коробках
II
Рис. 2.7. Решение задачи о коробках
III
Рис. 2.8. Решение задачи о трех
пожарных ведрах (начало) (середина) (конец)
2.2. Задача об оптимальном плане выпуска стульев
2.3. Задача об оптимальных перевозках
Рис. 2.10. Транспортная задача
У автора есть ряд любимых задач, решение которых
«размазано» по всей книге. Эти задачи довольно просты (если не примитивны) и,
можно сказать, не достойны такой современной математической программы, как
Mathcad. Но автор исходит из того, что читателю (студенту или инженеру – см.
название книги) нельзя давать одновременно и сведения о новой программной
среде, и новые, незнакомые ему задачи. Автор надеется, что, разобрав решение в
среде Mathcad простой, но типовой задачи, читатель ее усложнит – перейдет к
решению реальной задачи из своей профессиональной области или из разряда хобби.
Первую «любимую» задачу,
задачу о купце и сукне, мы решили в этюде 1. А вот вторая задача такого рода.
2.1. Гремим пожарными ведрами
Из круглой жестянки по несложной технологии
изготавливается пожарное ведро (см. пункт 1 на рис. 2.1):
вырезается сектор, затем полученная выкройка сворачивается в конус (точка a подтягивается к точке c), а шов сваривается
(паяется).
Рис. 2.1. Задача о пожарном ведре: схема решения
Требуется найти угол вырезки a
(альфа), при котором объем ведра будет максимальным.
Эту оптимизационную задачу можно решить аналитически: см. пункт 3.3 на рис. 2.1. Но, как понимает читатель, далеко не всякую
математическую задачу можно решить аналитически. Иначе бы не было таких научных
дисциплин, как «Прикладная математика», «Программирование», «Численные методы»
и др. Поэтому мы рассмотрим численное
решение задачи.
И при численном,
и при аналитическом решении задачи мы должны вывести зависимость объема ведра V от угла вырезки a.
Далее при аналитическом решении можно взять первую производную от этой функции,
приравнять ее к нулю и найти корень полученного уравнения. Не обойтись тут и
без второй производной, если нужно убедиться, что найденное решение – максимум,
а не минимум или точка перегиба, где, как помнит читатель из курса матанализа,
первая производная также равна нулю. Жестянщик, которому поручат сделать
пожарное ведро, скорее всего, незнаком с дифференциальным счислением, азы
которого мы только что изложили. Но в среде Mathcad поставленная задача вполне
окажется по плечу «компьютеризированному» жестянщику.
Рисунок заготовки
ведра и самого ведра в пункте 1 на рис. 2.1
сделан с помощью графического редактора Paintbrush и перенесен в
Mathcad-документ через буфер обмена Clipboard.
В пункт 2 на рис.
2.1 скопированы данные о геометрии конуса из стандартного справочника Mathcad, который удобен тем, что входит в
состав пакета и всегда находится под рукой. Справочник открывается командой Open Book… в меню Help. Перенос данных из
справочника в Mathcad-документ также автоматизирован, что исключает их
искажение – списывая формулу из книги немудрено и ошибиться.
Пункт 3 на рис.
2.1 – это «воспоминание о будущем». Там записаны операторы
символьных (аналитических) преобразований (см. этюд 7).
В пункте 3.1 оператором solve решается алгебраическое уравнение, позволяющее сформулировать функции
пользователя с именами r, h и V (см. пункт 3.2). Зависимости выводятся из
несложной геометрии круга и конуса: длина дуги выкройки (2×p×R-2×p×R×a/360) становится длиной
окружности в основании конуса (2×p×r), а высота конуса h, радиус его основания r и радиус заготовки R ¾ это стороны прямоугольного
треугольника, длины которых связаны теоремой Пифагора (см. пункт 3.2 на рис.
2.1). Оператор substitude позволяет заменять в выражениях подвыражение на
другое и вывести еще одну формулу V(a) без вызова вспомогательных
функций r(a) и h(a) – см. конец пункта 3.2 на рис.
2.1.
В пункте 3.3 берется производная от V(a), которая сразу упрощается (оператором символьного преобразования simplify). Несложный анализ вида производной
показывает, что оптимальный угол вырезки – это один из корней квадратного
уравнения a2-720a+43200. Но мы пока на это не обращаем внимания и начинаем численное решение
задачи.
Рис. 2.2. Решение задачи о пожарном ведре
Пусть радиус заготовки R равен одному метру (см. начало рис.
2.2). Это можно было бы и не оговаривать[1],
так как значение оптимального угла вырезки не зависит от радиуса заготовки (см.
конец рис.
2.1), но для численного
решения задачи о пожарном ведре это необходимо. Правда, можно было написать
проще – R:=1, не привязываясь к метрам (литрам, галлонам –
см. ниже). Но единицы физических величин позволяют нам дополнительно вести
контроль правильности формул через соответствие размерностей[2].
Далее записана (вернее,
скопирована из рис.
2.1) цепочка функций пользователя, формирующая нашу
анализируемую функцию V(a), в которую вложены другие
функции – r(a) и h(a). В последнюю в свою очередь также вложена функция r(a). Механизм вложения функций и
операторов (встроенных и пользовательских) ¾ это мощный инструмент не
только Mathcad, но и других программных сред, позволяющий быстро и изящно
решать довольно сложные задач. Вложенные функции просты по виду, а механизм их
формирования открыт, чего не скажешь о функции V(a) в пункте 3.2 на рис.
2.1.
Прежде чем искать максимум
функции, необходимо убедиться, что он есть. Лучший же способ увидеть максимум –
просмотреть график функции. В среде Mathcad есть семь видов графиков (см. этюд 1), первый из которых (X-Y-график в декартовых
координатах) отображен на рис.
2.2. Здесь график построен по «двухшаговой» технологии: задается вид
функции и сразу отдается команда на вставку графика в Mathcad-документ. По
умолчанию аргумент меняется от минус 10 до плюс 10 с пятьюдесятью точками на
графике. После построения наброска графика его нужно будет отформатировать –
изменить разброс аргумента и др.
На графике в районе 60-70
градусов отчетливо виден максимум функции. Как его уточнить?
Для решения такой задачи в
Mathcad 8 встроена новая функция Maximize, возвращающая координаты максимума анализируемой
функции вблизи точки начального приближения. Если из заготовки вырезать сектор
с углом в 66 с чем-то градусов, то такое ведро будет иметь максимальную
вместимость ¾ 403 литра (106 с половиной
американских или 88 с половиной британских галлонов – продолжение темы единиц
измерения физических величин, начатой в этюде 1).
Заканчивается численное
решение задачи о пожарном ведре проверкой правильности решения: Доверяй, но проверяй! Для этого, во-первых,
оно сравнивается с аналитическим (абсолютно точным, скопированным из рис.
2.1). Во-вторых, построен график той же функции, но на
ином интервале значений аргумента – вблизи найденной точки максимума: в
интервале 65-67 градусов с шагом 0.1[3].
Уточняющий график построен уже по «трехшаговой» технологии ¾ с заданием области значений
переменной-аргумента a. На это приходится идти, так как переменная a
к этому моменту уже имеет скалярное значение, которое мешает строить график в
два шага.
На рис.
2.2 читатель может видеть переменную с индексом a опт. Но здесь индекс опт (оптимальное) не числовой,
как на рис. 1.6 и 1.7, а текстовый.
Числовой индекс должен иметь определенное целочисленное значение, отмечающее
место переменной в векторе или в матрице. Текстовый же индекс – это всего лишь
продолжение имени переменной (функции). Он вводится в Mathcad-документ для
эстетического эффекта – чтобы переменные были более наглядными. Получается
текстовый индекс после того, как в середину имени переменной поставят точку:
было a.опт, стало a опт. Числовой же индекс, как
помнит читатель, вводится либо через квадратную скобку (X[n – Xn), либо через специальную кнопку Xn панели инструментов Matrix.
Попробуем
усложнить задачу о пожарном ведре. Что если вырезанный из заготовки сектор не
выбрасывать, а скручивать из него второе коническое ведро? Вместимость двух
ведер, естественно, будет больше вместимости одного ведра. Вопрос на пари: как
необходимо раскроить заготовку, чтобы суммарный объем двух ведер был
максимальным? Большинство опрошенных, опираясь на здравый смысл, ответят, что
заготовку нужно разрезать пополам по диаметру, и... проиграют пари.
Рис. 2.3. Решение задачи о двух пожарных ведрах
На рис. 2.3 показано численное решение «двухведерной задачи» в среде Mathcad. В основном оно повторяет решение, показанное на рис. 2.2, но имеет такие особенности:
·Сделано допущение, что радиус заготовки равен единице – переменная R в расчете отсутствует.
·Функция объема ведра не
опирается на вложенные функции. Это несколько усложняет понимание сути задачи,
но ускоряет расчет.
·Объем второго ведра
рассчитывается также через функцию V, но аргумент a при этом сдвинут на 360
градусов: второму ведру достаются обрезки от первого ведра.
·На первом графике выведена
не одна кривая, а три: объем первого ведра V(a), объем второго ведра V(360 - a) и сумма объемов обоих ведер SV(a)[4]. Кроме того, шкала оси
функции начата не с нуля, а со значения 0.38 для того, чтобы пользователь
отчетливо увидел два максимума у функции SV и выиграл пари: заготовку нужно разрезать не по диаметру, а несколько
иначе, чтобы получить два разных ведра, но с максимальным суммарным объемом.
·Построен график производной функции SV, на котором видны три точки
пересечения кривой с осью абсцисс, свидетельствующих о двух симметричных
максимумах и об одном локальном минимуме в середине. При форматировании первый
график был обрамлен (умолчание), а на
втором прорисованы оси X и Y. Второй график строится
намного дольше первого из-за того, что значение производной в каждой точке
графика приходится высчитывать, используя алгоритм численного
дифференцирования. А это сама по себе довольно сложная задача. Можно, конечно,
из рис. 2.1 скопировать в рис.
2.2 выражение для производной и работать уже с ней, но
мы договорились решить задачу только численными методами.
Максимумы для
разнообразия найдены не через функцию Maximize, как на рис.
2.2, а через поиск корней производной функции SV. Для этого в расчет
включена встроенная функция root, возвращающая корень
уравнения и тоже требующая первого приближения к решению. Изменили первое
приближение с 120 на 240 угловых градусов ¾ и ответ иной (второй).
Кроме того, пришлось изменить c 10-3 на 10-6
значение системной переменной TOL, отвечающей за точность нахождения корня: наша производная вблизи
максимумов и минимума меняется очень слабо – в пределах 10-4.
Пожарное ведро делается в
виде конуса для того, чтобы его нельзя было поставить на пол, а потом
использовать не по прямому назначению (для стирки, например) – такое ведро свалится
на бок[5].
Решение задачи о двух пожарных ведрах также «валится на бок» – на «левый» (a < 180) или на «правый» (a >180). Такую же форму (конус без
ножки) имеет бокал типа «Пей до дна!».
Не выбросив меньший сектор и
сделав из него второе пожарное ведро, мы мало что выиграли – второе ведро дало
небольшую прибавку в объеме (~ 50 литров). Раскрой заготовки для двух ведер не
по диаметру (a=180), а хитрым способом дал
совсем ничтожный выигрыш по суммарному объему ведер (что-то около литра). Но
нам важен не результат, а сам процесс расчета: «Цель ничто, движение – все!»
Теперь решим
задачу, подобную задаче о пожарном ведре, но более простую и более известную –
задачу о максимальном объеме коробки (см. рис. 2.4).
Она тоже будет иметь интересное продолжение, связанное с утилизацией отходов.
Рис. 2.4. Решение задачи о коробке
У квадратной
жестянки по углам вырезаются четыре квадрата. Полученная таким образом
крестообразная заготовка сгибается по пунктиру в прямоугольную призму без
верхней крышки, а четыре шва свариваются (паяются). Требуется рассчитать размер
сторон вырезаемых квадратов (a ¾ отношение размеров
квадратов), при котором объем нашего «квадратного ведра» (коробки) будет
максимальным.
На рис. 2.4 показано численное решение задачи. Оно отличается
от решения по пожарному ведру (см. рис. 2.2) только
видом анализируемой функции и методом оптимизации: использована функция MinErr[6] в паре с ключевым словом Given, между которыми булево
равенство и ограничение, заставляющее систему искать локальный, а не глобальный
максимум.
Несложный анализ
функции V(a) показывает, что она имеет максимум при a=1/6. Это позволяет оценить
точность использованного нами метода численной оптимизации.
Продолжение
задачи о коробке также похоже на продолжение задачи о пожарном ведре: обрезки
идут на изготовление новых четырех коробок, новые обрезки (их уже будет 16)
тоже пойдут в дело, и так до бесконечности. Но до нее (до бесконечности) мы
доберемся только в этюде 7, сейчас же рассмотрим
только первые семь шагов раскроя
квадратной заготовки, приводящих к формированию 5461 (1+4+16+43+44+45+46) коробок-«матрешек» (рис. 2.5).
Рис. 2.5. Решение задачи о коробках I
Формулу, определяющую объем плодящихся
вышеописанным способом коробок, вывести несложно[7].
Если допустить, что величина a (отношение размера вырезки
к размеру заготовки) сохраняется по шагам раскроя, легко показать, что сторона
исходного квадрата равна a0, четырех новых – a1, шестнадцати последующих – a2 и т.д.
Теперь спрашивается (еще одно пари!), как
нужно кроить заготовки: чему должно быть равно значение a, чтобы суммарный объем коробок был максимальным?
Ответ, лежащий на поверхности, – пропорция
выкройки a должна быть такой, какой
она была для одной коробки (одна шестая – см. рис. 2.4).
Если одна коробка имеет максимальный объем, то его будут иметь и несколько
коробок! Но это не так – оптимальная точка смещается вправо по оси аргументов
по мере выполнения все новых и новых шагов раскроя. На рис.
2.5 для сравнения выведены две кривые: зависимость от значения a объема одной коробки и
объема 5461 коробки. Прирост объема ничтожный, но нам опять же важен не
результат, а процесс расчета. Особенно наглядно это видно на рис.
2.6, где приведена формула расчета суммарного объема коробок в зависимости
от пропорции выкройки a и от числа шагов раскроя n.
Рис. 2.6. Решение задачи о коробках II
В задаче на рис. 2.6 оптимальный размер раскроя (величина a) является функцией числа шагов, что позволяет протабулировать аргумент
и функцию и проследить дрейф оптимума и прирост суммарного объема ведер. Как
видно из таблиц[8], где-то в
районе 7-8 шагов раскроя точность Mathcad становится недостаточной: ответы по
переменной a начинают
изменяться непредсказуемо, а по V – совсем не изменяются.
При поиске
оптимального раскроя коробок (рис. 2.5 и 2.6) мы предположили, что величина a, при которой суммарный объем коробок максимален, должна быть одной и
той же и для больших, и для маленьких коробок. Тем самым мы свели задачу к
оптимизации функции одной переменной (одномерная
оптимизация). На рис.
2.7 это ограничение снято.
Рис. 2.7. Решение задачи о коробках III
На рис.
2.7 суммарный объем коробок рассчитывается как функция уже не одного, а нескольких аргументов: первый шаг раскроя – один аргумент (пункт
1), второй шаг – два аргумента (пункт 2), третий шаг – три аргумента и т.д. В
пункте 1 рис.
2.7 для сравнения использованы три допустимых в Mathcad способа
поиска максимума и рассчитаны отклонения от аналитического решения при
проектировании одной коробки. В пункте 2 рис.
2.7 найдены оптимальные значения переменных a и b (пропорции выкройки
большого квадрата и четырех маленьких квадратиков соответственно), при которых
объем пяти коробок будет максимальным (двухмерная оптимизация). Мы забыли
наложить ограничения на переменные a и b в блоке Given-MinErr и второй результат оказался
неверным. В пункте 3 найденный оптимум проверяется на двух графиках – на линиях
уровня и на поверхности.
В среде Mathcad 8 операторы, которые
разработчик документа по каким-то причинам не хочет показывать другим людям,
можно оконтурить сверху и снизу границами области (команда Area в меню
Insert), которую затем можно захлопнуть (команда Area-Collapse в меню Format).
Это нами и сделано в пункте 3 на рис. 2.7 –
там запрятаны (см. след в виде горизонтальной линии) рутинные операторы формирования
матрицы M, по элементам которой
строятся трехмерные графики. Если теперь по этой линии два раза щелкнуть левой
кнопкой мыши (или щелкнуть раз и отдать команду Area-Expand в меню Format),
то область распахнется и покажет свое содержимое:
В предыдущих версиях Mathcad операторы
прятали от посторонних взглядов, помещая их за правую кромку экрана дисплея,
полагая, что никто не догадается туда заглянуть (тайна Полишинеля – мы уже
упоминали об этом в этюде 1).
Выделенную область можно защитить[9]
(с паролем или без оного) от редактирования (команда Area-Lock в меню Format).
Прием очень удобный. Во-первых, операторы можно прятать от самого себя – отладил какой-то участок Mathcad-документа и запрятал его от греха подальше. Другой случай. Разработчик сдал заказчику расчет, оставив на виду только зону ввода исходных данных и зону с результатом (если вернуться к рис. 1.5 с задачей о купце и сукне, то это самые нижние операторы). Остальное (что заказчику знать не следует – сам расчет) скрыто и защищено паролем. Может быть, там всего лишь пара операторов, но не простых, а гениальных. Рассказывают, что один американец починил за 1000 долларов дорогую паровую машину, стукнув по ней разок молотком. Когда ему сказали, что такая работа стоит от силы доллар, то он не стал спорить: «Да, но знание места, куда нужно бить молотком, стоит 999 долларов!»
Заканчивается рис. 2.7 формулой, по которой
можно рассчитать суммарный объем любого числа коробок, изготовленных по
методике, показанной на рис. 2.5. Найдены параметры раскроя при семи шагах. У
нас получилась схема оптимизации по переменному
числу аргументов. Стоит только изменить длину вектора a, тут же изменится число шагов раскроя квадратной
заготовки.
Продолжение и конец решения задачи о коробках
– в этюде 7, где к численным методам расчета добавятся аналитические
(символьные) методы и... интеллект пользователя.
Попробуем еще
немного «погреметь пожарными ведрами» и зададимся новым вопросом. Что если
круглую заготовку посекторно раскроить для изготовления не одного (см. рис.
2.2) и не двух (см. рис. 2.3), а трех ведер? Сможем ли мы еще что-то «выжать»
из задачи? Можно ли так раскроить круглую заготовку на три сектора и свернуть
из них три конуса, чтобы превысить «двухведерный» рекорд, зафиксированный на
рис. 2.3? Новая, «трехведерная» задача сводится к поиску максимума функции двух переменных: a (угол заготовки для первого
ведра) и b
(для второго).
Третьему ведру перепадут остатки: 360-a-b.
Рис. 2.8. Решение задачи о трех пожарных ведрах
(начало) (середина)
(конец)
На рис. 2.8 помещен протокол решения «трехведерной» задачи.
Поиск максимума начат опять же с формирования функции пользователя и с ее
графического анализа. Поверхность функции двух переменных строилась так, как
показано в пункте 3 на рис. 2.8. Создается сетка с 1681 узлом: 41 линия (0 до 40)
по оси переменной a
и столько же по
оси переменной b. Эта сетка кладется на плоскость a-b,
а затем ее узлы (от 0 до 360 градусов с шагом 9 градусов) поднимаются по оси
функции V на «подобающую» каждому
узлу высоту. Далее эта ажурная конструкция с помощью диалогового окна
форматирования поворачивается[10]
вокруг осей V, a и b так, чтобы человек смог увидеть то, что ему нужно, – максимумы,
минимумы и др. Всю эту работу машина берет на себя. От человека требуется
только наметить узлы сетки (i := 0.. 40, j
:= 0.. 40),
дать «угловое» значение ее узлам (ai := 9×i, bj
:= 9×j – углы меняются от 0 до 360
с шагом 9), заполнить матрицу M значениями «трехведерной»
функции ¾ Mi,j: = V(ai, bj), перевести курсор на свободное
место и отдать команду построения трехмерного графика, отображающего элементы
матрицы М.
Основной
недостаток трехмерной графики Mathcad заключается в том, что область изменения
аргументов должна быть прямоугольной.
Но в нашей «трехведерной» задаче она треугольная,
так как аргументы связаны ограничением a+b£360. В пункте 2 рис. 2.8 функция V строится так, чтобы ее
значения, выходящие за рамки треугольника, приравнивались к нулю (метод
штрафных санкций[11]). Из-за
этого задняя грань поверхности на рис. 2.8 получилась
зубчатой. Тем не менее видны максимумы на сторонах треугольника области
существования аргументов a и b
и провисание в центре. В трех вертикальных сечениях просматривается
«двухведерный» верхний график из рис. 2.3. Пакет Mathcad не смог решить
двухмерную «трехведерную» оптимизационную задачу по методике, представленной на
рис. 2.3 (взятие частных производных по
переменным a и b и поиск корней полученной
системы алгебраических уравнений). Пакет Mathcad пытался искать максимум «у
края обрыва» и «сваливался» в него. Не справилась с этой задачей и специально
введенная в Mathcad 8 функция Maximize при всех трех начальных приближениях (см. пункты
*.1[12]):
мы «танцевали» к максимуму от трех «печек» ¾ из центра треугольника (120
и 120 градусов ¾ см. пункт 4), из одного
угла треугольника (0 и 0 градусов ¾ см. пункт 5) и от одной из
сторон треугольника (150 и 210 градусов ¾ см. пункт 6). С поиском
максимума справилась «старая добрая» функция MinErr[13] ¾ см. пункты *.2. Старая в
буквальном смысле ¾ она ведет свою родословную
еще с DOS-версий Mathcad и поэтому хорошо отлажена.
В пункте 7 сделан дополнительный графический анализ через линии уровня нашей «трехведерной» задачи, которая на поверку оказалась «двухведерной». Сразу виден еще один недостаток трехмерной графики Mathcad: область существования решений ¾ это равнобедренный, а не прямоугольный треугольник[14], как в пункте 7 на рис. 2.8. Оси a и b нужно размещать не под прямым углом, а под углом в 60 градусов, но Mathcad этого делать не может.
В пункте 8 сделана попытка реабилитации функции Maximize, потерпевшей полное фиаско в пункте 6. Если функция MinErr всегда должна работать в паре с ключевым словом Given, то функция Maximize ¾ может. За ключевым словом Given при необходимости пишутся ограничения, открывающие новые возможности в решении оптимизационных задач. Если из пользовательской функции убрать штрафные санкции (переопределить ее ¾ см. начало пункта 7), то функция Maximize справится с поставленной задачей (пункты 8 и 10), если… не застрянет в «седле» (пункт 9). Мы еще раз подтвердили, что третье ведро лишнее: максимумы лежат на краю обрывов – на линиях области существования «двухведерной» задачи. Максимумов шесть. К ним можно прийти, изменяя начальные приближения.
В книге мы еще не раз будем «греметь пожарными ведрами»: в этюде 6 (тестирование программы поиска оптимума функции многих переменных) и в этюде 7 (аналитическое решение задачи о ведре).
Возможность записи перед
функциями Maximize
и Minimize
системы ограничений в виде неравенств и равенств позволяет решать в среде
Mathcad новый класс оптимизационных задач. Вот две из них.
2.2. Задача об оптимальном плане выпуска стульев
Суть задачи. Мебельная фабрика может
выпускать стулья двух типов ценою в 8 и 12 условных единиц (у.е.[15]).
Под этот заказ выделены материальные и людские ресурсы. Кроме того, известно,
сколько досок, ткани и времени идет на изготовление каждого стула:
|
Стул |
Расход досок, м |
Расход ткани, м2 |
Расход времени, чел.-час. |
|
Первый |
2 |
0.5 |
2 |
|
Второй |
4 |
0.25 |
2.5 |
|
Ресурс |
490 |
65 |
320 |
Спрашивается, как нужно спланировать
производство стульев, чтобы наделать их либо количеством, либо ценой поболее.
Это и отображено в отчете о решении задачи на рис. 2.9.
Рис. 2.9. Задача о стульях
Данная задача относится к широкому классу
задач под названием задачи линейного
программирования: необходимо установить план
(программу!) выпуска изделий (у нас это стулья), ориентируясь на целевую функцию (у нас их две ¾ общее количество и общая
стоимость стульев) и принимая во внимание ограничения
(ресурсы по доскам, ткани и человеко-часам). Из рис. 2.9 видно, что можно
выпускать не более 150 стульев (максимум первой целевой функции). А вот с
максимизацией их общей цены не получилось: Mathcad не умеет решать задачу целочисленного линейного
программирования. План выпуска стульев, максимизирующий их количество, вышел
целочисленным случайно.
2.3. Задача об оптимальных перевозках
На рис. 2.10 решается одна из разновидностей задач линейного программирования – транспортная задача: необходимо ежедневно с первого склада перевозить в два магазина 50 телевизоров[16], а со второго склада – 70. При этом первый магазин продает в день 40 телевизоров, а второй – 80 (50+70-40). В транспортной задаче неравенства в ограничениях заменены равенствами. Получается система линейных алгебраических уравнений, но не с одним, как в задаче о купце и сукне (см. рис. 1.6 и рис. 1.7) или в задаче о балке (см. рис. 1.15 и рис. 1.16), а с множеством решений, одно из которых оптимизирует целевую функцию. Известны затраты на перевозку одного телевизора со складов в магазины[17] (четыре константы: 1200 у.е. при перевозке одного телевизора с первого склада в первый магазин, 1600 – с первого склада во второй магазин, 800 – со второго склада в первый магазин и 1000 – со второго склада во второй магазин).
Рис. 2.10. Транспортная задача
Спрашивается, как нужно организовать перевозки (найти значения переменных с1м1, с1м2, с2м1 и с2м2), чтобы затраты были минимальны. На рис. 2.10 дан ответ. Парадокс задачи в том, что по самому дешевому маршруту (со второго склада в первый магазин – 800 у.е.) ничего не возится (с2м1 = 0). Этот парадокс мы также обыграем в следующем этюде.
Задачи на рис. 2.9 и.2.10 простенькие, но очень, если так можно выразиться, жизненно важные. На каждом шагу приходится что-то оптимизировать (расходы, например), принимая во внимание всякого рода ограничения (доходы!). Возвращаясь к сноске 17, можно привести такой пример. После часа пик (зимнее утро, к примеру) расход электроэнергии падает и необходимо снижать нагрузку электрогенераторов. Как это делать? Можно отключить отдельные турбогенераторы, а можно оставить их в работе, изменив нагрузку. Диспетчер энергосистемы дает соответствующие команды, ориентируясь на некие целевые функции: средний расход топлива по системе, выброс с дымовыми газами вредных веществ в атмосферу, износ оборудования, степень готовности электростанций и дальше менять нагрузку и т.д. Переменные такой оптимизации могут быть и вещественными (мощность отдельного энергоблока, которая меняется, естественно, в разумных пределах, определяемых техническими условиями – ограничения в задаче) и целочисленными (число работающих блоков). Эта задача очень сложная, но и очень эффективная – здесь речь идет о высвобождаемых составах с топливом.
Вот еще примеры. Когда нужно убирать пшеницу? Пораньше – зерно еще не вызрело. Попозже – часть зерна уже осыпалась. Сколько и каких акций стоит купить на ограниченную сумму денег, чтобы будущий дивиденд был максимален? В каких средствах массовой информации стоит размещать рекламу на выделенные по смете деньги, чтобы эффект от нее был максимален?
Разговор об оптимизации мы продолжим в этюде 3 в несколько ином ключе.
