МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ ЧЕРКАССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ В.Я.ГАЛЬЧЕНКО, Р.В.ТРЕМБОВЕЦКАЯ ЛИНЕЙНЫЕ ЗАДАЧИ ОПТИМИЗАЦИИ MATHCAD - ПРАКТИКУМ Учебное пособие Черкассы 2016 УДК 519.85(076) ББК 22.18я73 Г17 Рекомендовано к печати Ученым советом Черкасского государственного технологического университета (протокол №2 от 29 августа 2016 г.) Рецензенты: Верлань А.Ф. – главный научный сотрудник отдела математического и компьютерного моделирования Института проблем моделирования в энергетике им.Г.Е.Пухова НАНУ, член-корреспондент АПН Украины, доктор технических наук, профессор, заслуженный деятель науки и техники Украины Снитюк В.Е. – доктор технических наук, профессор, заведующий кафедры интеллектуальных и информационных систем Киевского национального университета имени Тараса Шевченко Триус Ю.В. - доктор педагогических наук, профессор, заведующий кафедры компьютерных наук и информационных технологий управления Черкасского государственного технологического университета Гальченко В.Я., Трембовецкая Р.В. Линейные задачи оптимизации. MathCAD – практикум / В.Я. Гальченко, Р.В.Трембовецкая – Черкассы: ЧДТУ, 2016. – 116 с., ил. ISBN 978-617-7318-37-7 В учебном пособии изложены конспективно основные теоретические положения и практический материал по решению задач линейного программирования. Существенное внимание уделено компьютерной реализации рассматриваемых методов в среде универсального математического пакета MathCAD, содержатся комплекты заданий для самостоятельной работы и большое количество примеров, способствующих лучшему пониманию и усвоению предмета. Для студентов инженерно-технических и экономических специальностей вузов. Материал, изложенный в пособии, может быть также использован аспирантами и специалистами соответствующих профилей в своей научно-исследовательской работе. ISBN 978-617-7318-37-7 © Гальченко В.Я., Трембовецкая Р.В., 2016 СОДЕРЖАНИЕ ВВЕДЕНИЕ……………………………………………………… 5 1. Задачи линейного программирования …………………… 8 1.1. Графический метод решения задач линейного программирования ………………………………………………... 10 1.1.1. Графический метод решения двумерных задач линей- ного программирования ………………………………………… 14 Задание 1. …………………………………………………… 25 1.1.2. Графическое решение задач линейного программирова- ния со многими переменными ………………………………….. 28 Задание 2. …………………………………………………… 35 2. Численное решение задач линейного программирова- ния в среде MATHCAD ………………………………………... 38 2.1. Численное решение задач линейной оптимизации с не- большим количеством неизвестных …………………………… 38 Задание3. ……………………………………………………. 39 2.2. Численное решение задач линейной оптимизации, харак- теризуемых большим количеством неизвестных, с использо- ванием матричной формы записи ……………………………… 42 Задание 4. …………………………………………………… 55 3. Представление задач линейного программирования в каноническом виде …………………………………………….. 58 Задание 5. …………………………………………………… 62 4. Сведение прямых задач линейного программирования к двойственным с последующим поиском решения численным методом……………………………………………. 66 Задание 6. …………………………………………………… 71 5. Целочисленные задачи линейной оптимизации ………... 74 5.1. Графический метод решения задачи целочисленного ли- нейного программирования …………………………………….. 74 5.2. Решение целочисленной задачи оптимизации методом полного перебора ………………………………………………... 84 5.3. Решение целочисленной задачи оптимизации путем вве- дения дополнительного ограничения ………………………….. 86 5 Задание 7. …………………………………………………… 88 Задание 8.……………………………………………………. 90 Задание 9.……………………………………………………. 90 6. Задачи линейного программирования с несколькими целевыми функциями…………………………………………… 90 6.1. Решение многокритериальных задач линейной оптимиза- ции методом последовательных уступок ……………………… 92 6.2. Поиск компромиссного решения задач линейного про- граммирования с несколькими целевыми функциями………... 97 6.3. Решение многокритериальных задач линейной оптимиза- ции путем сведения к замещающей с последующим примене- нием метода равных и наименьших отклонений……………… 101 Задание 10. ………………………………………………….. 107 Задание 11. ………………………………………………….. 110 Задание 12. ………………………………………………….. 110 Литература ……………………………………………………… 111 Термины и определения ………………………………………. 112 6 ВВЕДЕНИЕ Выбор наилучшего варианта или, по крайней мере, близкого к нему по какому-либо критерию либо группе критериев среди мно- жества возможных альтернативных вариантов представляет собой задачу, решение которой является актуальной для многих областей науки и техники. Отдельный класс задач рассматриваемых в данном учебном пособии, являющемся первой частью полного издания, представляют линейные задачи оптимизации. Они находят широкое применение в технике, экономике, химии, медицине, военных науках и др. Чаще всего решение подобных задач сводится к поиску экстремума функции в общем случае нескольких переменных, кото- рый ищется детерминированными, вероятностными или эвристиче- скими методами. Методы решения задач указанного типа доста- точно хорошо разработаны, а сведения о них содержатся в многочис- ленных литературных источниках, посвященных данной тематике. Среди них можно указать, например, такие, которые представляют особый интерес для читателей и относятся к фундаментальным: Таха Хэмди А. "Введение в исследование операций", 6-ое издание. – М.: Изд. Дом "Вильямс", 2001. – 912 с.; Зайченко Ю.П. "Дослідження операцій. Підручник", 7-ме видання, перероблене та доповнене.– К.: Видавничий Дім "Слово", 2006. – 816 с; Карманов В.Г. "Математи- ческое программирование: учеб. пособие", 5-ое издание. — М.: Физ- матлит, 2004. — 264 с. В тоже время решение практических задач линейного програм- мирования в современных условиях предполагает широкое приме- нение компьютерной техники, что, с одной стороны, позволяет изба- виться от рутинной работы по выполнению зачастую громоздких вычислений, а, с другой стороны, делает возможным использование в своей работе программного обеспечения, написанного предше- ственниками, без существенных затрат времени на освоение не все- гда простых методов решения задач линейной оптимизации. В современной учебной литературе теоретический материал из- лагается с одновременной параллельной демонстрацией возможно- стей его реализации в различных прикладных компьютерных паке- тах. Чаще всего читателя ориентируют на такие пакеты, как Mi- crosoft Excel, Matlab, Mathematica и др. Достаточно популярной в этом смысле, например, является монография Курицкого Б.Я. "По- иск оптимальных решений средствами Excel 7.0" - СПб.: ВНV – 7 Санкт-Петербург, 1997. – 384 с., где с позиций непрограммиста пред- ложен для непрограммистов широкий спектр компьютерно-реализо- ванных методов решения оптимизационных задач. В данном учебном пособии авторы придерживаются той же кон- цепции с той лишь разницей, что предлагают читателю воспользо- ваться для решения практических задач линейной оптимизации уни- версальным пакетом компьютерной математики MathCAD, имею- щим ряд существенных преимуществ перед другими аналогичными пакетами. Характерной особенностью пакета, делающей его приме- нение предпочтительным и целесообразным, является создание до- кументов-приложений с использованием технологии WYSIWYG (What You See Is What You Get — "что видишь, то и по- лучаешь"), т.е. с использованием привычных стандартных матема- тических обозначений, когда документ на экране выглядит точно так же как и обычная математическая запись. Для использования пакета не требуется изучать какую-либо систему команд, как, например, в случае пакетов Mathematica или Matlab. Пакет ориентирован в первую очередь на проведение численных расчетов, но имеет встро- енный символьный процессор, что позволяет выполнять аналитиче- ские преобразования. Он легок в освоении и удобен в использова- нии, обладает, кроме мощных вычислительных, достаточно продви- нутыми графическими возможностями, отличается великолепным пользовательским интерфейсом. В дополнение ко всему математи- ческий пакет MathCAD имеет достаточно простые средства програм- мирования, позволяющие при необходимости реализовать любой вычислительный алгоритм, что дает возможность встраивать в свой документ программные модули, содержащие стандартные алгорит- мические структуры: ветвления и циклы. Детальный разбор приве- денных в пособии программных модулей MathCAD, обладающих "прозрачной" структурой, позволяет обеспечить глубокое понима- ние сути изучаемых методов. В тоже время обучение на примерах предоставляет читателю возможность совершенствования в научном прикладном программировании. В каждом разделе пособия для удобства приводится краткое из- ложение теоретического материала, а основной акцент делается на его практическую реализацию с применением современных компь- ютерных технологий. Первый раздел пособия содержит сведения, а также соответству- ющие MathCAD-документы графического решения двумерных и 8 многомерных, которые могут быть сведены к первым, линейных за- дач оптимизации. Второй раздел посвящен численному решению задач линейного программирования с применением встроенных функций MathCAD, в том числе задач, характеризуемых наличием большого количества переменных, с использованием матричной формы записи. В третьем разделе представлены приемы преобразования одной формы математической формулировки линейных оптимизационных задач в другую, в результате численного решения рассматриваемых задач в среде MathCAD показана эквивалентность различных форм. Четвертый раздел демонстрирует возможности перехода от ре- шения прямых задач линейной оптимизации к двойственным по от- ношению к ним эквивалентным задачам. Пятый раздел рассматривает особенности решения в пакете MathCAD целочисленных задач линейного программирования, включая графический метод и метод полного перебора возможных значений переменных. В шестом разделе содержатся сведения о методах решения мно- гокритериальных линейных задач, в том числе основанные на поиске компромиссного решения для случаев противоречивых критериев. Все приемы и методы, рассматриваемые в учебном пособии, в обязательном порядке иллюстрируются соответствующими MathCAD-документами, позволяющими без особых проблем разо- браться в деталях изучаемых вопросов. Для успешного освоения изучаемого материала каждый раздел содержит комплект заданий для самостоятельного выполнения. В заключение отметим, что представленный в пособии материал использовался при проведении авторами лекционных, практических и лабораторных занятий по курсам "Математические методы опти- мизации и моделирование систем и процессов", "Оптимизация при- нятия решений в технике", которые читались студентам приборо- строительных специальностей 3-го, 4-го и 6-го курсов Черкасского государственного технологического университета. Авторы надеются, что материал учебного пособия будет полезен широкому кругу читателей: студентам, магистрантам, аспирантам, научным сотрудникам, всем, кто сталкивается с необходимостью ре- шения задач линейной оптимизации. 9 1. Задачи линейного программирования Линейное программирование (ЛП)– это метод решения опти- мизационных задач, в моделях которых целевые функции и ограни- чения строго линейны. ЛП успешно применяется в различных сферах для решения, прежде всего, экономических и управленческих задач (военной об- ласти, промышленности, сельском хозяйстве, транспортной отрасли, здравоохранении и др., а также в социологических науках) [1-10]. К числу базовых задач линейного программирования относятся:  Задача планирования производства (оптимального исполь- зования ресурсов);  Задача раскроя материалов;  Транспортная задача;  Задача оптимальной загрузки производственного оборудо- вания (распределительная задача);  Задача о составлении рациона. Совокупность соотношений, содержащих целевую функцию и ограничения на её аргументы, называется математической моде- лью. Математическая модель любой задачи линейного программиро- вания включает в себя:  целевую функцию (критерий оптимальности), максимум или минимум которой необходимо обеспечить;  систему ограничений в форме линейных уравнений и нера- венств;  требования неотрицательности переменных. Общей ЗЛП называется задача, которая состоит в определении оптимальных (максимальных или минимальных) значений линейной целевой функции, в которой система ограничений может содержать как равенства, так и неравенства. Математическая формулировка общей задачи линейного про- граммирования (ОЗЛП): требуется найти значения действительных переменных x , x ,…, x , при которых целевая функция (показатель 1 2 n эффективности) [1-10]: F  c x c x ...c x  max(min) (1) 1 1 2 2 n n принимает экстремальное значение при ограничениях: 10 а х  а х ... а x  b , 11 1 12 2 1n n 1  a x  a x ... a x  b ,  21 1 22 2 2n n 2 ...  a x  a x ... a x  b , i1 1 i2 2 in n i  a x  a x ... a x  b ,  i1,1 1 i1,2 2 i1,n n i1 ...  a x  a x ... a x  b ,  m1 1 m2 2 mn n m x ,x ,,x  0 1 2 n где а , b , c - заданные постоянные величины, ij i j i 1, 2,, m; j 1, 2,, n. Формулировку общей задачи линейного программирования можно записать более компактно: n (2) F  с x  max(min) j j j1 при ограничениях: n  a  х  b , i 1,2,,m; x  0 ij j i n j1 n  a  х  b , i 1,2,,m; x  0 ij j i n j1 Стандартной (или симметричной) ЗЛП называется задача, которая состоит в определении оптимального значения целевой функции, при условии, что система ограничений представлена в виде системы неравенств. Симметричная, или стандартная форма задачи линейного программирования имеет вид [1-10]: F  c x c x ...c x  max F  c x c x ...c x  min 1 1 2 2 n n 1 1 2 2 n n а х а х ...а x  b , а х  а х ... а x  b , 11 1 12 2 1n n 1 11 1 12 2 1n n 1 a x a x ...a x  b ,. a x  a x ... a x  b , 21 1 22 2 2n n 2 21 1 22 2 2n n 2   (3) ... ...   a x a x ...a x  b , a x  a x ... a x  b ,  m1 1 m2 2 mn n m  m1 1 m2 2 mn n m x ,x ,,x  0 x ,x ,,x  0 1 2 n 1 2 n 11