МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
УО «Белорусский государственный экономический университет»
Т.А. Бородина
ВЫСШАЯ МАТЕМАТИКА (4 семестр)
Учебно-методическое пособие для организации самостоятельной работы и
методические рекомендации для подготовки к тестированию
Для студентов заочного обучения всех специальностей
Минск 2011 УДК 519.85 ББК 22.183.4 Р е ц е н з е н т доктор физико-математических наук, профессор И.В.Белько Рекомендовано кафедрой прикладной математики и экономической кибернетики БГЭУ У т в е р ж д е н о Редакционно-издательским советом университета Бородина, Т.А.
Математическое программирование: учеб.-метод. пособие для организации Б самостоятельной работы и методические рекомендации для подготовки к тестированию/ Т.А. Бородина.- Мн.: БГЭУ, 2011. – 78 с.
В пособии наряду с теоретическим материалом, представленным в удобном для изучения и усвоения виде, приводятся практические задания и тесты, а также методические рекомендации для самостоятельной подготовки студентов заочной формы обучения к решению тестовых заданий по курсу "Математическое программирование".
УДК 519. ББК 22.183. © Т.А. Бородина © УО «Белорусский государстенный экономичекий университет»,
СОДЕРЖАНИЕ
1. Предисловие.......... 2. Инструкция для студентов........ 3. Методические рекомендации для организации самостоятельной работы 4. Рекомендуемая литература....... 5. Программа самостоятельной работы. Вопросы по теории дисциплины 6. Теоретический материал........ 6.1. Общая задача линейного программирования.... 6.2. Формы записи задач линейного программирования... 6.3. Геометрическая интерпретация и графический метод решения задачи линейного программирования...... 6.4. Симплексный метод решения задач линейного программирования 6.5. Теория двойственности в анализе оптимальных решений экономических задач линейного программирования.. 6.6. Транспортная задача по критерию стоимости... 6.7. Метод динамического программирования.... 7. Задачи для самостоятельного решения..... 8. Задания для самостоятельного тестирования.... 9. Ответы...........ПРЕДИСЛОВИЕ
Учебно-методическое пособие составлено в соответствии с программой курса "Высшая математика (4 семестр)". Предлагаемое пособие ориентировано на студентов экономических вузов и поэтому имеет интерпретацию решений задач, экономико-математических моделей и использование математического аппарата по отдельным темам курса. В данном пособии предлагается учебный материал и методические рекомендации для самостоятельной подготовки студентов заочной формы обучения к сдаче тестовых заданий по курсу "Высшая математика (4 тест)".Учебные материалы включают теоретический материал по отдельным темам, который представлен в виде, удобном студентам для изучения и усвоения, практические задания и тесты. Основу данного пособия составляют не только конкретные числовые примеры, по темам курса "Высшая математика (4 семестр)", решение и анализ которых помогает не только проверить свои знания, но и восполнить в кратчайшие сроки имеющиеся упущения в знании вышеназванного курса. Знания учебного материала, предложенного в данном пособии необходимы студенту для успешной сдачи тестирования в межсессионный период.
При подготовке данных учебных материалов использовалась научная и научно-методическая литература из списка рекомендуемой литературы, а также материал, накопленный в результате педагогической работы автора в Белорусском государственном экономическом университете.
Необходимо отметить, что для глубокого изучения математического программирования наряду с данным пособием нужно пользоваться и другими пособиями по данной тематике [1], [2], [3], [4], [5].
ИНСТРУКЦИЯ ДЛЯ СТУДЕНТОВ
Тестирование проводится по заранее составленному графику в течение учебного года или в первые дни по прибытии студентов на очередную сессию. Студент допускается к тестированию по предъявлению студенческого билета или зачетной книжки. Методист вводит в базу данных фамилию и инициалы, факультет, курс, группу и название дисциплины.На выполнение теста отводится 20 минут. В тесте 10 заданий. К каждому заданию дано несколько ответов, из которых только один является верным. Выполните задание и сравните полученный ответ с предложенными.
Выберите соответствующий номер полученного ответа и отметьте его.
Задания рекомендуется выполнять по порядку. Если задание не удается выполнить сразу, то следует перейти к следующему. Если останется время, вернитесь к пропущенным заданиям.
После окончания тестирования студенту на экране предоставляется перечень и содержание вопросов, на которые даны правильные, неправильные и неполные ответы, количество набранных баллов. Для получения положительного результата тестирования (сдано) необходимо набрать не менее 60 баллов из 100 возможных (т.е. ответить правильно на из 10 заданий теста). Студент, получивший неудовлетворительную оценку (не сдано) или не явившийся на тестирование согласно графика (независимо от причины), к зачету (экзамену) по курсу не допускается, а проходит тестирование в удобное время при наличии свободного компьютерного места по предъявлению студенческого билета или зачетной книжки. В том случае, если тестирование не пройдено вовремя, то зачет (экзамен) отодвигается на ближайший "День заочника". На подготовку к тестированию студенту предоставляется несколько месяцев – весь межсессионный период. Чтобы подготовка была целенаправленной и результативной следует пользоваться данным пособием. В самостоятельной работе студенту помогут преподаватели, еженедельно дежурящие на кафедре по индивидуальному графику и по субботам в "Дни заочника".
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ДЛЯ ОРГАНИЗАЦИИ
САМОСТОЯТЕЛЬНОЙ РАБОТЫ
Самостоятельная работа по овладению основных тем курса «Математическое программирование» предполагает прежде всего изучение теоретического материала по материалам данного пособия или по рекомендуемой литературе [1], [2], [3], [4], [5]. В приводимом ниже списке указывается одно пособие по дистанционному обучению, два учебника по теории дисциплины [3], [4], два задачника [2], [5]. Совсем не обязательно студенту иметь все пять книг, поскольку в них используются в качестве вычислительного аппарата различные алгебраические преобразования, что может вызвать некоторые трудности. В связи с этим целесообразно пользоваться либо комплектом книг [3], [2], либо комплектом книг [4], [5], либо [1]. Надеемся, что студент выберет для себя то, что будет соответствовать имеющемуся у него комплекту.В процессе проработки теоретического материала следует тщательно разбирать все приводимые в тексте пособия иллюстративные материалы и примеры. Степень понимания и усвоения теории значительно повышается при самостоятельном решении задач. Для этого учебный материал из списка литературы окажет студенту неоценимую помощь, поскольку все эти пособия содержат большое количество подробных решенных типовых задач, в том числе и задач с практическим содержанием. На начальной стадии изучения нового материала по курсу будет полезно самостоятельное решение задач уже разобранных в данном пособии с последующей сверкой своего решения и приведенного автором.
При изучении основных тем курса «Высшая математика (4 семестр)»
постоянно используются сведения из общего курса высшей математики, а именно раздел «Линейная алгебра». Кроме того, предполагается, что студенты обладают достаточными знаниями и умениями работы на персональном компьютере.
РЕКОМЕНДУЕМАЯ ЛИТЕАТУРА
1. Костевич Л.С. Математическое программирование – Мн.: БГЭУ, 2003. – 203с. (Система дистанционного обучения) 2. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию – Мн.: Выш. шк., 2001. – 448 с.3. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика.
Математическое программирование. – Мн.: Выш. шк., 2001. – 351 с.
4. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика.
Математическое программирование. – Мн.: Выш. шк., 1994. – 286 с.
5. Кузнецов А.В., Сакович В.А., Холод Н.И. и др. Под общей ред. А.В.
Кузнецова. Сборник задач и упражнений по высшей математике:
Математическое программирование – Мн.: Выш. шк., 1995. – 382 с.
6. Бородина Т.А. Математическое программирование: Учебнометодическое. – Минск: БГЭУ, 2006. – 55 с.
ПРОГРАММА САМОСТОЯТЕЛЬНОЙ РАБОТЫ.
ВОПРОСЫ ПО ТЕОРИИ ДИСЦИПЛИНЫ.
Предмет и задачи математического программирования (МП).Постановка задачи об оптимальном использовании ресурсов и ее экономико-математическая модель.
Постановка задачи об оптимальном составе смеси с заданными свойствами минимальной стоимости и ее экономико-математическая Постановка задачи об оптимальном размещении производства и ее экономико-математическая модель.
Постановка общей задачи математического программирования.
Задача линейного программирования и различные формы ее математической записи (общая, каноническая, симметричная). Преобразование одной записи в другую.
Геометрическая интерпретация целевой функции и ограничений задачи линейного программирования. Геометрическая формулировка задачи линейного программирования.
Графический метод решения задачи линейного программирования с двумя переменными, со многими переменными.
Опорные планы задачи линейного программирования. Соответствие между опорными планами и вершинами многогранника планов.
Вырожденный и невырожденный опорный план. Максимальное число 10.
опорных планов.
Основная теорема линейного программирования. Принципиальная 11.
схема решения задачи линейного программирования, вытекающая из этой теоремы.
Общая идея симплексного метода решения задачи линейного программирования. Геометрическая иллюстрация.
Монотонность и конечность симплексного процесса.
13.
Нахождение начального опорного плана задачи линейного программирования.
Правила выбора переменных, участвующих в преобразовании базиса 15.
при переходе от одного опорного плана к другому, более близкому к оптимальному.
Признак оптимальности опорного плана задачи линейного программирования.
Правила пересчета элементов симплекс-таблицы после выбора разрешающего элемента.
Нахождение оптимального опорного плана задачи линейного программирования при симплекс-методе.
Признак неограниченности целевой функции на множестве планов.
19.
Геометрическая иллюстрация.
Признак бесконечности множества оптимальных планов (альтернативный оптимум). Геометрическая иллюстрация.
Признак неразрешимости задачи линейного программирования.
21.
Геометрическая иллюстрация.
Алгоритм симплексного метода.
22.
Тема 2. Теория двойственности в линейном программировании Понятие двойственности в линейном программировании.
Экономические примеры двойственных задач: задача об оптимальном планировании производства и задача об оценках на используемые в производстве ресурсы. Двойственные оценки.
Симметричные двойственные задачи. Связь между элементами моделей Несимметричные двойственные задачи. Связь между элементами моделей этих задач. Задача, двойственная к канонической задаче.
Первая теорема двойственности и ее экономическое содержание.
Прикладные аспекты теоремы: нахождение оптимального плана двойственной задачи по решению прямой задачи.
Вторая теорема двойственности и ее экономическое содержание.
Прикладные аспекты теоремы: оценка степени дефицитности ресурсов, оценка целесообразности производства новых видов продукции; оценка убыточности производства продукции, не рекомендованной оптимальным планом.
Третья теорема двойственности и ее экономическое содержание.
Прикладные аспекты теоремы: расчет норм заменяемости дефицитных ресурсов, целесообразность приобретения дополнительного количества дефицитных ресурсов.
Свойства двойственных оценок и их использование при экономическом анализе решения задачи линейного программирования.
Постановка транспортной задачи по критерию стоимости и ее экономикоматематическая модель.
Особенности модели транспортной задачи как задачи линейного программирования.
Транспортная задача с открытой и закрытой моделью.
Преобразование открытой транспортной задачи в закрытую.
Условие разрешимости транспортной задачи.
Условие целочисленности оптимального плана транспортной задачи.
Теорема о ранге матрицы системы ограничительных уравнений транспортной задачи и ее прикладное значение. Количество «загруженных»
клеток в транспортной таблице и проблемы, возникающие в связи с этим в вырожденных задачах.
Циклы в транспортной таблице и их свойства.
Циклы свободных клеток транспортной таблицы, когда в ней содержится опорный план.
Способ северо-западного угла построения начального опорного плана 10.
транспортной задачи.
Построение начального опорного плана транспортной задачи способом 11.
наименьшего тарифа.
Построение начального опорного плана транспортной задачи способом 12.
Процедура преобразования опорного плана транспортной задачи в новый 13.
опорный план и проблемы, возникающие в связи с этим в вырожденных Оценка (характеристика) свободной клетки транспортной таблицы и ее 14.
экономический смысл.
Признак оптимальности опорного плана транспортной задачи Неединственность оптимального опорного плана (альтернативный Потенциалы поставщиков и потребителей. Система уравнений для 16.
определения потенциалов.
Экономический смысл потенциалов.
17.
Связь между оценками свободных клеток и потенциалами.
18.
Алгоритм метода потенциалов.
19.
Усложненные постановки транспортной задачи (учет себестоимости 20.
продукции в месте изготовления, блокирование отдельных маршрутов, обязательные поставки).
Задачи транспортного типа с максимизируемой целевой функцией и 21.
изменения в методике решения по сравнению с классической задачей о перевозках.
Тема 4. Элементы целочисленного линейного программирования Постановка и математическая модель полностью целочисленной задачи линейного программирования. Идея решения задачи методом отсечения и его геометрическая иллюстрация.
Построение правильного отсечения и его свойства.
Алгоритм метода Гомори решения полностью целочисленной задачи линейного программирования. Признак неразрешимости задачи в целых числах.
Понятие о методе ветвей и границ.
Тема 5. Элементы нелинейного программирования Постановка задачи нелинейного программирования. Трудности в разработке общих методов решения. Обзор некоторых классов задач нелинейного программирования.
Понятие выпуклой и вогнутой функции. Понятие о локальном и глобальном экстремумах. Графический метод решения задач НЛП.
Метод множителей Лагранжа решения задач НЛП.
Понятие о градиентных методах решения задач НЛП.
Тема 6. Элементы динамического программирования Понятие о динамическом программировании. Метод динамического программирования и его особенности. Принцип оптимальности Беллмана.
Вычислительная схема решения оптимизационной задачи методом динамического программирования.
Задача о выборе наиболее экономного маршрута доставки груза и решение ее методом динамического программирования.
Задача об оптимальном распределении средств между предприятиями на расширение производства продукции и решение ее методом динамического программирования.
Задача оптимального планирования выпуска, содержания и хранения продукции и решение ее методом динамического программирования.
Задача о выборе оптимальной стратегии замены устаревшего оборудования и решение ее методом динамического программирования.
ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ
В данном разделе будут содержаться сведения и информация по курсу линейного программирования с тем, чтобы систематизировать знания о математических методах решения оптимизационных моделей и линейных оптимизационных моделей.используемых классов математических моделей.
инструментом в физике, химии, астрономии, экономике и вообще везде, где человек хотел объяснить и упорядочить наблюдаемые явления. И это естественно — для всякого наблюдения линейная функция является самой удобной математической моделью, и ею охотно пользуются.
Конечно, сейчас поле математических приложений значительно расширилось. Но по-прежнему линейные модели привлекают огромное внимание. Они сравнительно просты, хорошо разработаны, допускают полное исследование и достаточно эффективны в целом ряде стандартных ситуаций.
Линейность — это свойство математических выражений и функций.
Выражение вида ах + bу + с, где х и у — переменные величины, а а, b и с — постоянные числа. называется линейным относительно переменных х и у.
В случае если переменных больше двух — х1, х2, …, хn, линейное выражение относительно этих переменных имеет вид где а 0, a1, a 2, …, a n — постоянные числа.
Заметим, что в линейное выражение все переменные входят в первой степени и никакие переменные не перемножаются.
Линейное программирование является наиболее известным и одним из наиболее широко используемых инструментов. Это математический метод решения задачи оптимального распределения имеющихся ресурсов (или денег, или материалов, или времени) для достижения определенной цели (наибольшего дохода или наименьших издержек).
Линейное программирование — это частный раздел оптимального программирование — раздел прикладной математики, изучающий задачи практической реализации принципа оптимальности в планировании и управлении.
Математическая модель задачи – это отражение оригинала в виде математического программирования включает: совокупность неизвестных величин х1, х2, …, хn ; целевую функцию (показатель эффективности, критерий оптимальности, функцию цели и др.); условия (или систему ограничений), налагаемых на неизвестные величины, совокупность которых образует область допустимых решений ( ). Таким образом, мы можем записать математическую модель в следующем виде F=f(х1, х2, …, хn)max (min) Необходимым условием использования оптимального подхода к планированию и управлению (принципа оптимальности) является гибкость, альтернативность производственно-хозяйственных ситуаций, в условиях которых приходится принимать планово-управленческие решения. Именно такие ситуации, как правило, и составляют повседневную практику приготовление смесей и т.д.).
Рассмотрим основные примеры экономических задач, ставшие классическими:
Задача планирования производства (задача о наилучшем использовании Пусть некоторая производственная единица производит n видов продукции Pj, ( j = 1, n), затрачивая при этом m типов ресурсов Ri, (i = 1, m).
Известны следующие параметры:
c j, ( j = 1, n) – цена единицы продукции j-го вида (вектор цен);
bi (i = 1, m) – запас i-го ресурса (вектор ресурсов);
aij, (i = 1, m; j = 1, n) – количество i-го ресурса, необходимое для производства единицы продукции j-го вида (технологическая матрица);
x j, ( j = 1, n) – планируемый объем производства j-го вида продукции (план производства), при котором обеспечивается максимум прибыли при имеющихся ресурсах.
Составим экономико-математическую модель данной задачи.
Так как c j – цена единицы продукции j-го вида, тогда стоимость x j единиц будет равна c j x j, а цена общего объема продукции:
Так как a ij x j – расход i-го ресурса на производство x j единиц j-го вида продукции, то просуммировав расход i-го ресурса на выпуск всех n видов продукции, получим общий расход этого ресурса на производство продукции, который не должен превышать bi :
ограничениями на ресурсы нужно наложить условие неотрицательности на объемы x j выпуска продукции:
производства примет вид:
Итак, (1.2) - (1.4) – модель поставленной задачи.
Пусть имеется m производителей, у каждого из которых находится a i, (i = 1, m) единиц однородного товара. Этот товар нужно доставить n b j, ( j = 1, n) единиц, чтобы общая величина транспортных издержек была минимальной.
Известны следующие параметры:
cij, (i = 1, m; j = 1, n) – стоимость перевозки единицы товара от i-го производителя j-му потребителю.
xij, (i = 1, m; j = 1, n) – количество товара, перевозимое от i-го производителя j-му потребителю.
Для удобства стоимость перевозки cij, (i = 1, m; j = 1, n) и количество перевозимого товара xij, (i = 1, m; j = 1, n) можно записать в виде матриц:
Математическая модель транспортной задачи примет вид:
(1.5) – целевая функция, описывающая транспортные затраты;
(1.6) – весь продукт из пунктов производства должен быть вывезен;
(1.7) – спрос потребителей должен быть удовлетворен;
(1.8) – условия неотрицательности переменных исключают обратные перевозки.
программирования и решаются при помощи математических методов оптимизации.
Суть принципа оптимальности состоит в стремлении выбрать такое планово-управленческое решение Х = ( х1, х 2, …, х n ), где x j, (j=1, n ) — его компоненты, которое наилучшим образом учитывало бы внутренние хозяйствующего субъекта.
Слова «наилучшим образом» здесь означают выбор некоторого критерия оптимальности, т.е. некоторого экономического показателя, «максимум прибыли», «минимум затрат», «максимум рентабельности» и др.
Слова «учитывало бы внутренние возможности и внешние условия производственной деятельности» означают, что на выбор плановоуправленческого решения (поведения) накладывается ряд условий, т.е. выбор Х осуществляется из некоторой области возможных (допустимых) решений.
Эту область называют также областью определения задачи.
Таким образом, стандартная формулировка общей задачи линейного программирования выглядит так: требуется найти экстремальное значение показателя эффективности (целевой функции) при линейных ограничительных условиях, накладываемых на элементы решения:
……………………………………… где аij, bi, cj — заданные числа.
Условие (1.11) необязательно, но его всегда при необходимости можно добиться. Обозначение {, =, } говорит о том, что в конкретном ограничении возможен один из знаков:, = или.
Общую постановку задачи линейного программирования можно записать в более компактной форме:
найти максимум или минимум функции.
Задача (1.12) - (1.14) — общая задача линейного программирования, иначе — математическая модель задачи линейного программирования, в основе построения (разработки) которой лежат принципы оптимальности и системности.
Вектор Х =(х1, х2, …,хn) (набор управляющих переменных) называется допустимым решением, или планом задачи, или вектором управления, или поведением оптимального программирования, если он удовлетворяет системе ограничений (1.13) и (1.14). Неотрицательное базисное допустимое решение задачи называется опорным планом. А тот план Х =(х1, х2, …,хn) (опорное решение), который доставляет максимум или минимум целевой функции f(х1, х2, …, хn) (1.12), называется оптимальным планом (оптимальным поведением, или просто решением) задачи линейного программирования.
Таким образом, выбор оптимального управленческого поведения в конкретной производственной ситуации связан с проведением с позиций системности и оптимальности решения задачи линейного программирования.
Оптимальное решение может быть не единственное. Возможны случаи, когда оно и не существует.
Рассмотрим числовой пример задачи линейного программирования.
Пример 1. Фирма выпускает два вида древесно-стружечных плит обычные и улучшенные. При этом производятся две основные операции прессование и отделка. Составить экономико-математическую модель задачи при помощи которой требуется указать, какое количество плит каждого типа можно изготовить в течение месяца так, чтобы обеспечить максимальный представленных в таблице 1, если за каждые 100 обычных плит фирма получаем доход, равный 80 ден.ед., за каждые 100 плит улучшенного вида 100 ден.ед.
поставленной задачи.
Введем следующие обозначения. Пусть х1 количество партий в плит обычного вида, изготавливаемых в течение месяца, а х2 то же для плит улучшенного качества.
Тогда ожидаемый доход можно записать так:
Для изготовления х1 партий в 100 плит обычного вида и х2 партий в 100 плит улучшенного вида требуется 5х1 + 10х2 килограммов дерева. Ясно, что полученное число не может превосходить количество материала, имеющегося в наличии, т.е. 1000 кг. Тем самым, ограничение на материал имеет вид: 5х1 + 10х2 1000.
Подобным же образом рассчитывается ограничения на время изготовления и затраты:
неотрицательности на объемы выпуска плит:
Итак подведем итог: требуется найти такие значения х1 и х2, подчиненные условиям для которых Итак, соотношения (1.15) – (1.16) и есть математическая модель задачи поставленной в данном примере. Эта задача будет решена позже, после того как будет рассмотрен графический метод решения задач линейного программирования.
Формы записи задач линейного программирования Выше были рассмотрены задачи с линейными ограничениями и линейной функцией. В одних из задач ограничения имели вид неравенств, в необходимо различать виды записи задач линейного программирования.
Рассмотрим основные из них.
называют задачу максимизации или минимизации линейной функции при линейных ограничениях где J1 J2 =( j=1, n ) и аij, bi, cj — постоянные числа.
Симметричной формой записи задачи линейного программирования называют задачу максимизации линейной функции (2.1.), при линейных ограничениях (2.2.), когда все ограничения имеют смысл неравенства вида «» и все переменные неотрицательны, т.е.
Канонической формой записи задачи линейного программирования называют задачу максимизации линейной функции (2.1.), при линейных ограничениях (2.2.), когда все ограничения имеют смысл равенства и все переменные неотрицательны, т.е.
На практике часто приходится одну форму записи задачи линейного программирования преобразовывать в другую. При этом пользуются следующими соображениями:
При необходимости задачу максимизации можно заменить задачей минимизации и наоборот. Экстремум этих функций достигается в одной и той же точке, т.е. min f = - max ( -f ). После решения задачи max ( -f ) необходимо изменить на противоположный знак оптимума неотрицательности (например хк), то её можно заменить разностью двух новых неотрицательных переменных (хк’ и xк’’), т.е. хк=хк’–xк’’.
Любое ограничение неравенство задачи линейной оптимизации вида “ ”, можно преобразовать в равенство добавлением к его левой части дополнительной неотрицательной переменной, а неравенство, вида неотрицательной переменной.
В экономических задачах дополнительные переменные всегда имеют определенный, практический смысл. Рассмотрим пример.
Пример 2. Привести модель задачи к канонической форме.
Решение: Модель нашей задачи записана в общем виде. Так как на переменную х2 не наложено условие неотрицательности, то её мы заменим разностью двух неотрицательных переменных х2’ и х2” (x2 = х2’ - х2”) и подставим полученное выражение вместо переменной х2 в модель задачи. В результате мы получим модель:
Ограничение неравенство 3х1 + 4( х2’ - х2”) - 6х3 9 преобразуем в равенство путем вычитания дополнительной переменной х Ограничение неравенство 5х1 + 4х3 11 преобразуем в равенство путем добавления к левой части дополнительной переменной х Следует заметить, что в каждое ограничение необходимо вводить свою дополнительную переменную. И, наконец, преобразуем исходную задачу минимизации к задаче максимизации, применив соображения из пункта 1 z = - f = -8х1 -6( х2’ - х2”) - 3х3 max.
Итак, мы получили следующую модель задачи, которая записана в каноническом виде:
Геометрическая интерпретация и графический метод решения Задание точки посредством упорядоченного набора чисел позволяет описывать при помощи формул различные множества, это дает возможность добавить к геометрическим рассуждениям действенный аналитический аппарат и, наоборот, привлекать к исследованию разнообразных формул наглядные геометрические соображения.
Известно, что любой упорядоченный набор n чисел можно геометрически интерпретировать как точку или вектор n-мерного Х =(х1,х2,…,хn) будем интерпретировать как точки или векторы.
В простейшем случае, когда число переменных равно двум, удобен простой и наглядный графический метод. Он не требует больших предварительных знаний и позволяет получать ответ без привлечения дополнительных средств и, что особенно важно, раскрыть суть идей, лежащих в основе других методов.
Рассмотрим модель вида (1.2) (1.4) с двумя переменными На координатной плоскости Ох1х2 линейное уравнение вида аijхj+аijхj=bi изображается прямой, а линейное неравенство аijхj+аijхj bi или аijхj+аijхj bi является полуплоскостью. Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми х1=0 и х2=0. Если система ограничений совместна, то полуплоскости как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых составляют решение данной системы. Совокупность этих точек называют многоугольником решений. Это может быть точка, отрезок, луч, замкнутый многоугольник, неограниченная многоугольная область.
Пусть наша система неравенств (3.2.) и (3.3.) образует область множества) (рисунок 1).
Придадим целевой функции произвольное значение, например равное k. Получим С1х1 +С2х2 = k. А это уравнение прямой линии, в каждой точке которой целевая функция сохраняет одно и то же постоянное значение равное k. Если теперь k считать параметром, а не константой, то мы получим семейство параллельных прямых, называемых линиями уровня целевой функции.
Осталось найти направление возрастания и убывания целевой функции. Найдем частные производные целевой функции по переменным х Они показывают скорость возрастания целевой функции вдоль осей х и х2 соответственно. Вектор С = (С1, С2) показывает направление наискорейшего возрастания целевой функции и называется векторомцелевой функции. Вектор называют антиградиентом и он указывает направление наискорейшего убывания целевой функции. Вектор С = (С1, С2) перпендикулярен к прямым семейства f=const.
Таким образом, геометрически задача линейной оптимизации (3.1.)представляет собой поиск такой точки многогранника решений, координаты которой доставляют линейной функции наибольшее (наименьшее) значение, причем допустимыми решениями являются все точки многогранника решений.
Если в задаче линейной оптимизации ограничения заданы в виде ограничений с двумя переменными, то она может быть решена графически.
Графический метод решения состоит из следующих этапов.
Этап 1. Сначала на координатной плоскости Ох1х2 строится допустимая многоугольная область (область допустимых решений, область определения), соответствующая ограничениям. Далее строится векторградиент линейной функции. Начало вектора находится в точке с координатами (0; 0), а вершина в точке с координатами (С1, С2). Следует заметить, что значения С1 и С2 и есть коэффициенты при переменных целевой функции задачи. Для удобства можно строить вектор, пропорциональный вектору С. В какой-нибудь точке, принадлежащей допустимой области строится прямая семейства f=const, которая всегда будет проходить перпендикулярно вектору-градиенту.
Этап 2. Прямая f=const, перпендикулярная вектору-градиенту, перемещается в направлении этого вектора в случае максимизации функции (или в противоположном направлении задачи минимизации) до тех пор, пока не покинет пределов многоугольной области. Крайняя (предельная) точка (или точки) области при этом движении и является точкой максимума (минимума) целевой функции.
Этап 3. Для нахождения координат точки максимума (минимума) достаточно решить систему из двух уравнений прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума (минимума). Например это значения а1 и а2. Значение функции, найденное в получаемой точке, является максимальным (минимальным). И затем останется выписать ответ, который будет иметь вид: Х *=(а1,а2),fmax = f(а1,а2).
В случае минимизации целевой функции прямую f=const надо перемещать в направлении, противоположном вектору-градиенту (по направлению вектора-антиградиента). Ясно, что если прямая при своем движении не покидает допустимой области, то соответствующий максимум неограниченна на множестве планов).
Пример 3. Решить графическим методом задачу примера 1:
Решение: Ограничения х1 0, х2 0 означают, что область решений будет лежать в первой четверти декартовой системы координат. Отметим эту область на рис. 2 (первая четверть, указываем направление стрелочками).
Этап 1. Определим множество решений первого неравенства. Оно состоит из решения уравнения 5х1 + 10х2 = 1000 и строгого неравенства 5х1+10х2 (min) 11. Модель двойственной задачи построенной к данной принимает следующий вид:
12. При решении пары двойственных задач (одна из которых задача об оптимальном использовании ресурсов) получен следующий результат:
f( x ) = 20x1+10x2+9x3 (max); Х * =(10; 0; 3; 0; 8; 0); У * =(2; 0; 4; 0; 5; 0).
Значение прибыли, если в производство ввести 3 единицы наиболее дефицитного ресурса, будет равно 13. Оцените целесообразность включения в план нового вида продукции, нормы затрат ресурсов на единицу которого равны соответственно 3, 4, 2, а прибыль от реализации равна 40 ден.ед., если при решении задачи о производстве продукции при оптимальном использовании ресурсов было получено следующее решение 14. Оцените целесообразность закупки 10 единиц второго вида ресурса по цене 2,5 ден.ед., если при решении задачи о производстве продукции при оптимальном использовании ресурсов было получено следующее решение f( x ) = 46x1+25x2+30x3 (max) 15. План находящийся в данной таблице является 16. Для клетки (1; 4) замкнутый цикл представлен в таблице 17. Оценка свободной клетки ( 2; 1) равна 18. Полученный план перевозок транспортной задачи является 19. Если значение потенциала U2 = 1, то значение потенциала V3 будет равно 20. Для данного опорного плана, находящегося в следующей таблице, значение функции будет равно 21. Принцип оптимальности Беллмана для задачи в которой решается вопрос о том, как спланировать работу группы предприятий, чтобы экономический эффект от выделенных этим предприятиям дополнительных финансовых или материальных ресурсов был максимальным, формализуется в следующее функциональное уравнение динамического программирования.
3) fn(xn-1, un) = min (zn(xn-1, un)+fn-1(xn)) ОТВЕТЫ
3. У * (67/220; 0; 3/20; 0; 0), min=267; да, на b1=5*(67/220)=67/44;
«