Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Московский государственный университет леса ___________________________________________________________ МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ С EXCEL Учебное пособие Для студентов всех специальностей МГУЛа Издательство Московского государственного университета леса Москва ⎯ 2005 УДК 519.8 Д17 Данилин, Г. А. и др., Математическое программирование с EXCEL: Учебное пособие для студентов всех специальностей МГУЛа / Г. А. Данилин, В. М. Курзина, П. А. Курзин и др. ⎯ М.: МГУЛ, 2005. ⎯ 113 с.: ил. Учебное пособие содержит основные элементы исследований операций, ис- пользуемые в различных экономических приложениях; задания по лабораторным ра- ботам и сведения, необходимые для их выполнения. Разработано в соответствии с Государственным образовательным стандартом ВПО 2000 г. для направления подготовки студентов на основе примерной програм- мы дисциплины "Высшая математика" для всех специальностей 2005 года. Одобрено и рекомендовано к изданию в качестве учебного пособия редакционно-издательским советом университета Рецензенты: профессор А. В. Корольков, профессор Л. Е. Цветкова Кафедра высшей математики Авторы: Геннадий Александрович Данилин, доцент; Вера Михайловна Курзина, доцент; Павел Алексеевич Курзин, ас.; Ольга Митрофановна Полещук, доцент © Данилин Г. А., Курзина В. М., Курзин П.А., О. М. Полещук, 2005 © Московский государственный университет леса, 2005 3 Введение На современном этапе развития общества, с переходом к рыночным отношениям, резко повысилась управленческая роль руководителя произ- водства (предприятия). В связи с этим умение находить оптимальные управленческие решения − один из признаков, по которому оцениваются профессионализм и опытность менеджера. Оптимальное решение – это выбранное по какому-либо критерию оптимизации наиболее эффективное из всех альтернативных вариантов решение. К методам оптимизации относятся анализ, прогнозирование и моделирование. Моделирование может быть физическое и математиче- ское. Физическое моделирует предметы, а математическое – процессы. Математические модели – основное средство решения задач оптимизации любой деятельности. Ценность математических моделей для экономиче- ского анализа и оптимизации решений состоит в том, что они позволяют получить чёткое представление об исследуемом объекте, охарактеризовать и количественно описать его внутреннюю структуру и внешние связи. В соответствии с Государственным общеобразовательным стандар- том математическое моделирование процессов экономики изучается в курсе "Высшей математики" в разделе "Экономико-математические мето- ды и модели". Методы оптимизации задач прикладной математики разра- ботаны в математическом программировании (исследовании операций). Математическое программирование позволяет широко использовать в процессе принятия решений вычислительную технику, что является жиз- ненной необходимостью в процессе технико-экономического обоснования и определения экономической эффективности инвестиционных проектов. Теоретической основой и практическим инструментом анализа и прогнозирования решений в экономике и бизнесе являются экономико- математические модели и проводимые по ним расчёты. Необходимость применения персональных компьютеров в процессе принятия управленческих решений в наше время стала особенно актуаль- на. Однако, к сожалению, не все специалисты владеют простым и доступ- ным даже непрофессиональным программистам средством решения раз- личных задач, в том числе и задач математического программирования, а именно, табличным процессором Excel. Для успешного решения задач с помощью Excel необходимо знать основные идеи и методы исследования операций, условия их применения. Цель курса – помочь студентам освоить элементы математического программирования и методы решений задач с использованием Excel, даю- щие возможность оперативно принимать решения в будущей деятельности студентов как специалистов. Курс обеспечивает тесную связь обучения математическим методам с общеинженерной подготовкой специалиста. 4 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Математические модели оптимизации позволяют существенно под- нять качество планирования и управления при реализации различных эко- номических проектов. Так, если установлено (например, методами матема- тической статистики), что рассматриваемые характеристики зависят друг от друга линейно, причём область допустимых решений задаётся линей- ными функциями-ограничениями, то для решения таких задач могут быть использованы линейные математические модели. Это могут быть задачи о распределении ресурсов, о рационе питания (диете), о планировании пере- возок, распределении работ, расстановке кадров и многие другие. При оп- тимизации переменной величины в случае линейности модели применя- ются методы линейного программирования. Основное положение в линей- ном программировании заключается в том, что связь между факторами, влияющими на исследуемую характеристику, линейна. Кроме того, только линейными зависимостями должны быть заданы используемые в задаче функции-ограничения, определяющие область изменения допустимых зна- чений рассматриваемой величины. Линейное программирование решает задачи нахождения оптималь- ных значений переменных для линейной целевой функции и системы её ограничений, заданных линейными алгебраическими уравнениями или не- равенствами. 1.1. Постановка задачи Общей задачей линейного программирования называется задача о нахождении максимума (минимума) линейной функции F(X) =C x +C x +...+C x (1.1) 1 1 2 2 n n при ограничениях ⎧a x + a x +...+ a 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 ; ⎨ k1 1 k2 2 kn n k (1.2) a x + a x +...+ a x =b ; ⎪ k+1,1 1 k+1,2 2 k+1,n n k+1 ⎪a x + a x +...+ a x =b ; k+2,1 1 k+2,2 2 k+2,n n k+2 ⎪ ..................................................... ⎪ ⎪ a x + a x +...+ a x =b , ⎩ m1 1 m2 2 mn n m x ≥0, j =1,2,..., l;l ≤ n. j 5 Решение X =(x ,x ,...,x ) системы ограничений (1.2), при котором 1 2 n функция F(X) принимает максимальное (минимальное) значение, называ- ется оптимальным планом задачи линейного программирования. Все ос- тальные решения системы ограничений называются допустимыми пла- нами. Функция F(X) называется целевой функцией. Ограничения (1.2) называются основными. Стандартной (симметричной) задачей называется задача линейного программирования, в которой все основные ограничения заданы неравен- ствами и все переменные задачи неотрицательны. Основной (канонической) задачей называется задача линейного про- граммирования, в которой все ограничения заданы равенствами и все пе- ременные неотрицательны. 1.2. Симплексный метод Для нахождения оптимального плана задачи линейного программи- рования применяется симплексный метод. Симплексный метод решения задач линейного программирования основан на идее последовательного улучшения решения задачи, исходя из опорного плана (первоначального решения), найденного каким угодно спо- собом. В задачах линейного программирования, как правило, решаются сис- темы ограничений, в которых число линейно независимых переменных меньше общего числа переменных задачи. Любые m переменных системы m линейных уравнений с n пере- менными (m< n) называются базисными (основными), если определитель матрицы размерности m×m коэффициентов при них отличен от нуля. Ос- тальные n − m переменных называются свободными (неосновными). Симплексный метод позволяет улучшать план задачи наиболее ра- циональным способом, опираясь на критерии оптимальности решения. Критерий оптимальности решения при отыскании максимума линейной функции симплексным методом можно сформулировать сле- дующим образом: если в выражении линейной функции через свободные переменные отсутствуют положительные коэффициенты при свободных переменных, то решение оптимально. Критерий оптимальности решения при отыскании минимума линейной функции: если в выражении линейной функции через свободные переменные отсутствуют отрицательные коэффициенты при свободных переменных, то решение оптимально. 6 На практике удобнее для выяснения вопроса: является ли найденный план оптимальным, пользоваться оценками переменных ∆ , j =1,n, кото- j рые вычисляются по формулам n ∆ =∑C a −C . (1.3) j i ij j i=1 Тогда критерии оптимальности решения формулируются иначе, а именно: при отыскании максимума функции: если оценки всех переменных неотрицательны, то значение целевой функции максимально и решение оптимально; при отыскании минимума функции: если оценки всех переменных неположительны, то значение целевой функции минимально и решение оптимально. Первоначальное допустимое решение определяется методом вырав- нивания (введением дополнительных переменных, с помощью которых неравенства превращаются в равенства) или М-методом − методом искус- ственного базиса. Практические расчеты при решении реальных задач, если не исполь- зуется ЭВМ, проводят в так называемых симплексных таблицах. Рассмотрим одну из часто решаемых симплексным методом оптими- зационных задач − задачу о распределении ресурсов. Предприятие производит три вида электронной техники: телевизоры, магнитофоны и моноблоки. Технологические коэффициенты, определяю- щие затраты того или иного ресурса на производство одной единицы про- дукции каждого вида, а также количества запасов соответствующих ресур- сов, используемых при выпуске этих изделий, и прибыль, получаемая предприятием-производителем от реализации одной единицы каждого ви- да продукции, приведены в табл. 1.1. Требуется таким образом спланировать выпуск изделий на заводе, чтобы получать наибольшую, максимальную, прибыль. Решение задачи начнём с допущения, что неизвестная x обозначает 1 количество телевизоров, x − количество магнитофонов, а x − количество 2 3 моноблоков, выпускаемых предприятием. Тогда получаем, что затраты по ресурсу "Пластиковые формы" на данном предприятии, согласно заданным табл. 1.1 технологическим коэффициентам определяются зависимостью 2,5x +1,7x + 2,1x . При этом затраты по ресурсу "Пластиковые формы" 1 2 3 не должны превышать 150 единиц, заданных в качестве имеющегося на предприятии запаса. 7 Т а б л и ц а 1.1 Технологические коэффициенты, прибыль и запасы ресурсов Запас Ресурс Телевизор Магнитофон Моноблок ресурса Пластиковые формы 2, 5 1, 7 2, 1 150 Электронные кабели 3, 7 2, 2 2,8 175 Электронные платы 4, 5 2, 1 3,5 250 Трудозатраты 5, 0 3, 0 4,5 130 Прибыль от реализации одного изделия 3, 0 1,0 2,0 ─ Таким образом, получаем первое ограничение на количество выпус- каемой продукции: 2,5x +1,7x + 2,1x ≤150. (1.4) 1 2 3 Аналогично составляются ограничения по другим ресурсам, и в ре- зультате получаются еще три ограничения по ресурсам: 3,7x + 2,2x + 2,8x ≤175; (1.5) 1 2 3 4,5x + 2,1x +3,5x ≤ 250; (1.6) 1 2 3 5,0x + 3,0x + 4,5x ≤130. (1.7) 1 2 3 Кроме того, поскольку количество выпущенной продукции не может быть отрицательной величиной, естественно потребовать, чтобы выполня- лись неравенства x ≥0; x ≥0; x ≥0. (1.8) 1 2 3 При выпуске выбранного количества продукции согласно данным табл.1.1 предприятие получит прибыль, определяемую функцией 8 F(X)=3,0x +1,0x + 2,0x . (1.9) 1 2 3 Решение задачи оптимизации заключается в нахождении таких ко- личеств выпускаемой продукции, которые обеспечивают функции прибы- ли максимальное значение при заданных ограничениях по количеству имеющихся на предприятии ресурсов. Каждое из решений системы нера- венств (1.5) − (1.7), будет допустимым решением (планом) для данной за- дачи. Оптимальным решением называется то из допустимых решений, при котором целевая функция имеет максимальное значение. В разных за- дачах оптимальных решений может быть как множество, так и не быть во- обще, или может существовать единственное оптимальное решение (план). Таким образом, объединяя составленные по данным табл.1.1 зависи- мости (1.5) − (1.8), получаем математическую модель задачи о распределе- нии ресурсов: F(X) =3,0x +1,0x + 2,0x →max, 1 2 3 ⎧2,5x +1,7x + 2,1x ≤150; 1 2 3 ⎪ ⎪3,7x + 2,2x + 2,8x ≤175; 1 2 3 ⎨ 4,5x + 2,1x +3,5x ≤ 250; (1.10) ⎪ 1 2 3 ⎪5,0x +3,0x + 4,5x ≤130, ⎩ 1 2 3 x ≥0; x ≥0; x ≥0. 1 2 3 Естественное ограничение о неотрицательности количеств выпускае- мой продукции вытекает из смысла производственной задачи. Решение сформулированной задачи может быть найдено, например, симплексным методом. Поскольку ограничения задачи являются неравенствами "с недостат- ком", введём дополнительные вспомогательные переменные x ,x ,x ,x , 4 5 6 7 которые называют "выравнивающими", и с помощью них превратим нера- венства в равенства: F( X )=3,0x +1,0x + 2,0x → max, 1 2 3 ⎧2,5x +1,7x + 2,1x + x =150; 1 2 3 4 ⎪ ⎪3,7x + 2,2x + 2,8x + x =175; 1 2 3 5 ⎨ 4,5x + 2,1x +3,5x + x = 250; (1.11) ⎪ 1 2 3 6 ⎪5,0x +3,0x + 4,5x + x =130, ⎩ 1 2 3 7 x ≥0; x ≥0; x ≥0; x ≥0; x ≥0; x ≥0; x ≥0. 1 2 3 4 5 6 7 Теперь система (1.11) является системой четырёх линейных алгеб- раических уравнений относительно семи неизвестных. Решения системы (1.11) находим симплексным методом в табл. 1.2, с использованием мето- 9 да Жордана − Гаусса для решения систем линейных алгебраических урав- нений. Метод Жордана − Гаусса − это метод нахождения базисных реше- ний систем m линейных алгебраических уравнений относительно n неиз- вестных, если n≥ m, в специальных таблицах, позволяющих в ходе реше- ния замещать базисный элемент одним из свободных переменных. Коли- чество N различных базисных решений определяется формулой n! N =Cm = . (1.12) n m!⋅(n − m)! Среди найденных базисных решений могут быть и вырожденные, то есть такие, в которых значение базисной переменной равно нулю. В качестве первого базиса берём систему векторов (x ,x ,x ,x ), и 4 5 6 7 соответствующий базисный вектор имеет нулевые координаты, поскольку коэффициенты целевой функции при соответствующих переменных равны (см. (1.1)): C =3,0; C =1,0; C =2,0; C =0; C =0; C =0; C =0. 1 2 3 4 5 6 7 При решении системы (1.11) и нахождении того её базисного реше- ния, которое обеспечивает максимум рассматриваемой функции прибыли (целевой функции) F , использованы критерии симплексного метода для задач линейного программирования. Стрелки в табл. 1.2 указывают разре- шающий столбец и разрешающую строку, на их пересечении находится разрешающий элемент. Разрешающим столбцом является столбец, содержащий максималь- ную по абсолютному значению отрицательную оценку − наименьший эле- мент строки оценок. Разрешающей строкой называется строка, соответст- вующая минимальному значению из оценок элемента строки δ , найденно- i го для всех элементов разрешающего столбца по элементам столбца сво- бодных членов уравнений по формуле a δ = i0 . (1.13) i a ik Согласно критерию оптимальности решения при нахождении его симплексным методом следует отыскать такое базисное решение получен- ной системы уравнений, при котором оценки его будут неотрицательны в случае максимума целевой функции или неположительны в случае мини- мума целевой функции. 10 Т а б л и ц а 1.2 Решение задачи о распределении ресурсов симплексным методом Неизвестные в задаче программирования Оценка Базис Свободные элемента x члены строки баз уравнений x x x x x x x δ 1 2 3 4 5 6 7 i x 150 2,5 1,7 2,1 1 0 0 0 60 4 18 46 x 175 3,7 2,2 2,8 0 1 0 0 37 5 4 55 x 250 4,5 2,1 3,5 0 0 1 0 9 6 5,0 →x 130 3,0 4,5 0 0 0 1 26 ← 7 ∆ F =0 − 3,0 ↑ − 1,0 − 2,0 0 0 0 0 ─ j x 85 0 0,2 − 0,15 1 0 0 − 0,5 4 x 78,8 0 − 0,02 − 0,53 0 1 0 − 0,74 5 x 113 0 − 0,6 − 0,55 0 0 1 − 0,9 6 x 26 1 0,6 0,9 0 0 0 0,2 1 ∆ F = 78 0 0,8 0,7 0 0 0 0,6 ─ j Если промежуточные базисные решения не удовлетворяют критерию оптимальности, производится замещение одного из базисных неизвестных