Методы оптимальных решений лекции - 1. Моделирование экономических систем. Основные понятия и определения.
Методы оптимальных решений
Методы оптимальных решений (стр. 1 )
Методы оптимальных решений
1. Моделирование экономических систем. Основные понятия и определения.
1. Моделирование экономических систем. Основные понятия и определения.
Методы оптимальных решений (стр. 1 )
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны. Несмотря на многообразие задач организационного управления, при их решении можно выделить некоторую общую последовательность этапов, через которые проходит любое исследование. Построение содержательной модели рассматриваемого объекта процесса. На данном этапе происходит формализация цели управления объектом, выделение возможных управляющих воздействий, влияющих на достижение сформулированной цели, а также описание системы ограничений на управляющие воздействия. Построение математической модели, т. Проверка полученных результатов на их адекватность природе изучаемой системы, включая исследование влияния так называемых внемодельных факторов, и возможная корректировка первоначальной модели. В курсе методы оптимальных решений центральное место отведено вопросам, относящимся к четвертому пункту приведенной выше схемы. Это делается не потому, что он является самым важным, сложным или интересным, а потому, что остальные пункты существенно зависят от конкретной природы изучаемой системы, в силу чего для действий, которые должны производиться в их рамках, не могут быть сформулированы универсальные и содержательные рекомендации. Для решения экономической задачи математическими методами составляют математическую модель задачи, то есть записывают ее с помощью математических выражений: Для математического описания экономической задачи можно руководствоваться следующей общей схемой:. Эти соотношения образуют систему ограничений математической модели;. Построенная функция называется целевой. В зависимости от свойств целевой функции, математическое программирование можно рассматривать как ряд самостоятельных дисциплин, занимающихся изучением и разработкой методов решения определенных классов задач. Если - линейная функция и линейны функции, описывающие ограничения на переменные , то математическая модель представляет задачу линейного программирования. Если хотя бы одна из указанных функций нелинейная, то математическая модель является объектом исследования нелинейного программирования. Наиболее изученным разделом математического программирования является линейное программирование. Для решения задач этого раздела разработан целый ряд эффективных алгоритмов и методов. Математическое моделирование является, с одной стороны, очень важным и сложным, а с другой -- практически не поддающимся научной формализации процессом. Заметим, что неоднократно предпринимавшиеся попытки выделить общие принципы создания математических моделей приводили либо к декларированию рекомендаций самого общего характера, трудноприложимых для решения конкретных проблем, либо, наоборот, к появлению рецептов, применимых в действительности только к узкому кругу задач. Поэтому более полезным представляется знакомство с техникой математического моделирования на конкретных примерах. Мощным инструментом решения задач, построенных на базе математической модели, является наука, которая называется математическое программирование. В данном случае понятие программирование употребляется в смысле планирование в отличие от программирования для ЭВМ. В свою очередь, в зависимости от вида решаемых задач, в математическом программировании выделяют такие области, как линейное, нелинейное, дискретное, динамическое, стохастическое программирование. Курс по методам оптимальных решений должен дать студентам достаточное представление о математическом аппарате, используемом при принятии решений в экономических задачах. Освоение этого материала придает студенту уверенность, которой обычно недостает, если он с самого начала направляет свои усилия на изучение философских аспектов и искусства принятия решений. Графический метод применяется для решения ЗЛП, заданной в симметричной форме. Этот метод наиболее эффективно применяется для решения задач с двумя переменными, так как требует графических построений. В случае трех переменных необходимы построения в R 3 , в случае четырех переменных необходимы построения в R 4 и т. Множество точек называется выпуклым , если для любых двух точек множества оно содержит отрезок, их соединяющий. Теорема 1 Пересечение любого количества выпуклых множеств является выпуклым множеством. Теорема 2 Пусть имеются две произвольные точки и в пространстве R n. Тогда для любой точки отрезка [ PQ ] должно выполняться: Гиперплоскостью в пространстве R n называется множество точек, удовлетворяющее уравнению. Заметим, что в двумерном случае гиперплоскостью является прямая. Полупространством называется множество точек, удовлетворяющее одному из неравенств или. Гиперплоскость делит точки пространства на два полупространства. В двумерном случае гиперплоскостью является полуплоскость. Теорема 3 Полупространство является выпуклым множеством. Следствие Пересечение любого количества полупространств является выпуклым множеством. Многогранником называется пересечение одного или более полупространств. Многогранник в двумерном случае называется многоугольником. Точка выпуклого множества называется угловой , если она не лежит внутри никакого отрезка, соединяющего две другие точки из множества. Угловыми точками треугольника являются его вершины их три. Угловыми точками круга являются точки окружности, которая его ограничивает их бесконечное число. Теорема 4 Оптимальный план ЗЛП соответствует вершине многогранника решений, определяемого ее системой ограничений. Пусть задача линейного программирования с двумя переменными задана в симметричной форме. Для решения этой задачи можно перебрать все вершины многоугольника, определяемого системой ограничений, и выбрать из них ту, в которой значение функции больше. Но можно не перебирать все вершины, а воспользоваться понятиями линии уровня и градиента. Линией уровня функции Z называется множество точек, удовлетворяющее уравнению , где c - произвольная константа. В двумерном случае, это уравнение определяет прямую. Линии уровня образуют семейство параллельных прямых. Вектор называется градиентом функции Z. Вектор в каждой точке перпендикулярен линии уровня, проходящей через эту точку, и указывает направление наибольшего возрастания функции Z ,. Таким образом, наибольшее значение Z достигается в вершине, через которую проходит линия уровня, соответствующая наибольшему значению Z. Отмечают полуплоскости, соответствующие ограничениям - неравенствам. Заштриховывают многоугольник, определяемый системой ограничений. Для этого определяют общую часть ранее отмеченных m полуплоскостей, лежащую в первой четверти следует из условий неотрицательности переменных. Если выбранный для построения многоугольника масштаб не позволяет построить , то вместо него строят вектор в случае, если длина слишком мала для построения или в случае, если длина слишком велика для построения , где. В случае необходимости параллельным переносом линию уровня следует расположить таким образом, чтобы многоугольник находился впереди линии уровня по направлению. Это будет наиболее удаленная вершина многоугольника, в которой линия уровня пересекается с многоугольником. В зависимости от особенностей области допустимых решений и взаимного расположения области и вектора при решении задачи линейного программирования возможны различные случаи. Если область допустимых решений - ограниченный многоугольник, то может быть либо единственное решение, либо бесконечно много решений - все точки отрезка, соединяющего две вершины многоугольника альтернативный оптимум. В случае альтернативного оптимума оптимальный план представляется выражением координат произвольной точки отрезка через координаты ее концов. Если область допустимых решений - неограниченный многоугольник, то в зависимости от направления задача может иметь или не иметь решения. В этом случае так же может оказаться альтернативный оптимум. На рисунке а функция достигает минимума в точке А , а максимума - в любой точке отрезка ВС альтернативный оптимум ; на рисунке б максимум достигается в точке А , минимума функция не имеет; на рисунке в функция не имеет ни минимума, ни максимума. Каждое неравенство исходной системы ограничений определяет полуплоскость. Запишем уравнения граничных прямых для этих полуплоскостей. Каждая прямая разбивает плоскость на две полуплоскости. Выбранные полуплоскости отметим стрелочками. Найдем пересечение отмеченных полуплоскостей с учетом условия: Вектор определяет направление наибольшего возрастания функции Z. Построим из начала координат вектор. Этот вектор также показывает направление наибольшего возрастания функции. Перемещая линию уровня параллельным переносом в направлении вектора , находим последнюю точку пересечения линии уровня и заштрихованного пятиугольника - точку А. Эта точка является точкой максимума функции. Точка А получается в результате пересечения прямых 2 и 3. Для нахождения ее координат решим систему:. Пусть имеются два пункта, расстояние между которыми равно км. Между ними необходимо осуществить связь, имеющую 12 телефонных, 31 телеграфных и 18 фототелеграфных каналов с помощью кабелей двух типов, обладающих следующими характеристиками:. Определить необходимое количество кабелей каждого типа для осуществления связи с наименьшими затратами. По определению эти переменные должны быть неотрицательны. Для осуществления связи необходимо наличие не менее требуемого количества каналов. Получаем ограничения на количества имеющихся каналов:. Затраты на осуществление связи, имеющей x 1 кабелей I типа и x 2 кабелей II типа, составят: Получаем математическую модель задачи:. Заштрихуем полученный неограниченный четырехугольник ABCD. Перемещая линию уровня параллельным переносом в направлении вектора , находим первую точку пересечения линии уровня и заштрихованного четырехугольника - точку B. Эта точка является точкой минимума функции. Точка B получается в результате пересечения прямых 2 и 3. Для осуществления связи с наименьшими затратами необходимо 3 кабеля I типа и 4 кабеля II типа. При этом минимальные затраты составят у. Для решения оптимизационных задач используется надстройка Поиск Решения. Все действия по настройке и использованию данной надстройки приводятся для Excel и выше. Сначала необходимо убедиться, что эта надстройка присутствует на вкладке Данные в группе Анализ. Если команда Поиск решения или группа Анализ отсутствует, необходимо загрузить эту надстройку Надстройка. Вспомогательная программа, служащая для добавления в Microsoft Office специальных команд или возможностей. Для этого щелкните пиктограмму Microsoft Office в верхнем левом углу окна , далее щелкните кнопку Параметры Excel. В появившемся окне Параметры Excel выберите слева поле Надстройки. В правой части окна должно быть установлено значения поля Управление равным Надстройки Excel , нажмите кнопку Перейти , которая находится рядом с этим полем. В окне Надстройки установите флажок рядом с пунктом Поиск решения и нажмите кнопку ОК. Далее можно работать с установленной надстройкой Поиск Решения. До вызова Поиск Решения необходимо подготовить данные для решения задачи из математической модели:. Ниже перечислены основные поля и кнопки диалогового окна Поиск решения и их назначение. Эта ячейка должна содержать формулу. Результат поиска отображается в поле Изменяя ячейки. Ограничения можно добавлять, удалять, изменять с помощью соответствующих кнопок, расположенных возле поля Ограничения. При нажатии этой кнопки открывается диалоговое окно Добавить ограничение , с помощью которого вводятся ограничения. При этом открывается диалоговое окно Изменить ограничение, которое позволяет редактировать выбранное ограничение. При этом сохраняются установки, сделанные в окнах диалога, появлявшихся после нажатий на кнопки Параметры , Добавить , Изменить или Удалить. При этом открывается диалоговое окно Параметры поиска решения , в котором настроить параметры, можно загрузить или сохранить оптимизируемую модель. Управление алгоритмом поиска и определение его параметров скорости сходимости, точности и т. В этом окне можно изменять условия и варианты поиска решения для линейных и нелинейных задач, а также загружать и сохранять оптимизируемые модели. Значения и состояния элементов управления, используемые по умолчанию, подходят для решения большинства задач. В поле можно ввести время в секундах , не превышающее ; значение , используемое по умолчанию, подходит для решения большинства простых задач. В поле можно ввести количество итераций, не превышающее ; значение , используемое по умолчанию, подходит для решения большинства простых задач. Поле должно содержать число из интервала от 0 до 1. Относительная погрешность по умолчанию 0, При указании большего допуска поиск решения заканчивается быстрее. Сходимость применяется только к нелинейным задачам, условием служит дробь из интервала от 0 до 1. Для решения задач линейного программирования его значения несущественны. Данный вариант предусмотрен для хранения на листе более одной модели оптимизации, первая модель сохраняется автоматически. Решим задачу из Примера 2 раздела 1. Подготовим данные на листе. Сначала определим ячейки, в которые будет помещен результат решения. Пусть это будут ячейки В2, С2, сделаем у них заголовки. В этих ячейках нет данных, их должен будет рассчитать Excel, они выделены цветом. Далее заполним коэффициенты при неизвестных и правые части системы ограничений строки Заведем строку 9 для целевой функции. Цветом выделена ячейка, в которой будет находиться значение целевой функции для найденного оптимального решения. В ячейки D5, D6, D7 ведем формулы для зависимостей левых частей системы ограничений, а в ячейку E9 - формулу для зависимости целевой функции. Далее необходимо воспользоваться надстройкой Поиск решения. На вкладке Данные в группе Анализ выберите команду Поиск решения. Появится диалоговое окно Поиск решения , которое необходимо заполнить следующим образом для добавления ограничений пользуемся кнопкой Добавить:. Далее нажимаем кнопку Параметры и в появившемся окне Параметры поиска решений устанавливаем флажок неотрицательные значения, линейная модель и нажимаем OK. В окне Поиск решения после нажатия кнопки Выполнить появляется окно Результаты поиска решения , в котором выбираем сохранение найденных значений и нажимаем кнопку ОК. Результаты поиска решений для ячеек В2 и С2 установлены числовые форматы с 0 знаками после запятой:. Для составления математической модели задачи введем две переменные: Предприятие не может израсходовать сырья больше, чем у него имеется, поэтому получаем следующие ограничения на использование имеющегося сырья:. Предположим, что по некоторым обстоятельствам потребитель отказался от заказа, и предприятие решило продать сырье, не выпуская продукцию. По каким ценам будет продаваться сырье? Составим математическую модель возникшей задачи. Предприятию имеет смысл не выпускать продукцию только в случае, если выручка от продажи сырья не меньше, чем стоимость произведенной из этого сырья продукции. На производство одной единицы продукции P 1 расходуется 3 единицы сырья S 1 , 4 единицы сырья S 2 и 4 единицы сырья S 4. Если не выпускать продукцию P 1 , а продать все сырье, из которого его можно изготовить, то выручка от реализации этого сырья составит. Аналогично, выручка от реализации сырья, из которого можно изготовить продукцию P 2 , составит. Выручка от продажи сырья должна быть не меньше стоимости единицы соответствующей продукции. С другой стороны, покупатель сырья хочет купить это сырье как можно дешевле. На покупку сырья будет затрачено у. Составленная задача называется двойственной к исходной. Как видно из построенных моделей кроме экономической связи между ними существует и математическая связь. Перечислим условия, связывающие построенные задачи. Количество переменных двойственной задачи соответствует количеству ограничений исходной задачи. Коэффициенты при неизвестных в целевой функции исходной задачи являются правыми частями в ограничениях двойственной задачи и, наоборот, правые части ограничений исходной задачи являются коэффициентами при неизвестных в целевой функции двойственной задачи. Знаки неравенств задач противоположны: Матрица коэффициентов при неизвестных в системе ограничений двойственной задачи является транспонированной матрицей коэффициентов при неизвестных в системе ограничений исходной задачи. Заметим, что если к двойственной задаче построить двойственную, то получим исходную задачу. Поэтому говорят о паре симметричных взаимно двойственных задач. Рассмотрим правила построения двойственной задачи в общем случае. Пусть имеется задачи линейного программирования в общем виде:. Сначала производится согласование цели исходной задачи и неравенств ее системы ограничений. Если какое-нибудь неравенство не соответствует цели задачи, то его следует домножить на -1 для смены знака на противоположный. Каждому i -му ограничению системы исходной задачи соответствует переменная y i двойственной задачи и, наоборот, каждому j -му ограничению системы двойственной задачи соответствует переменная x i исходной задачи. Подпишем эти соответствия слева от систем. Коэффициенты при неизвестных в целевой функции двойственной задачи совпадают с правыми частями системы ограничений исходной задачи. Матрица системы ограничений двойственной задачи получается транспонированием из матрицы системы ограничений исходной задачи;. Коэффициенты правых частей двойственной задачи - это коэффициенты при неизвестных в целевой функции исходной задачи. Знаки ограничений двойственной задачи могут быть либо неравенствами, соответствующими цели двойственной задачи, либо равенствами. Неравенство ставится в случае, если на переменную исходной задачи, соответствующую ограничению двойственной задачи, наложено условие неотрицательности. Если такого условия нет, то соответствующее ограничение двойственной задачи - уравнение. На переменную y j двойственной задачи следует наложить условие неотрицательности лишь в том случае, если i -е ограничение исходной задачи - неравенство. Согласуем знаки неравенств с целью задачи. Второе неравенство не согласовано с целью функции, умножим его обе части на В системе имеется 3 ограничения, поэтому в двойственной задаче будет 3 переменные, подпишем эти переменные слева от ограничений. Второе ограничение является уравнением, так как на переменную x 2 не наложено условие неотрицательности. На переменную y 3 не наложено условие неотрицательности, так как соответствующее y 3 ограничение исходной задачи - уравнение. В силу того, что все три формы записи задачи линейного программирования общая, симметричная, каноническая эквиваленты, далее будем рассматривать пару симметричных двойственных задач. Теорема 1 Основное неравенство теории двойственности Пусть и - допустимые решения пары двойственных задач в симметричной форме. Экономический смысл Теоремы 1 заключается в том, что при любом допустимом плане производства общая стоимость всей произведенной продукции не превосходит суммарной оценки ресурсов, соответствующей любому допустимому решению двойственной задачи. Теорема 2 Достаточный признак оптимальности решения Пусть и - допустимые решения пары двойственных задач и. Экономический смысл Теоремы 2 заключается в том, что планы производства и оценки ресурсов оптимальны, если стоимость произведенной продукции совпадает с суммарной оценкой ресурсов. Теорема 3 О минимаксе Если одна из пары двойственных задач имеет решение, то и другая имеет решение, причем. Если одна из пары двойственных задач имеет неограниченную функцию, то система ограничений второй задачи не совместна. Экономический смысл Теоремы 3 заключается в том, что максимально возможная стоимость произведенной продукции совпадает с минимально возможной стоимостью сырья. Теорема 4 Равновесия Пусть и - допустимые планы пары двойственных задач в симметричной форме. Эти планы являются оптимальными тогда и только тогда, когда выполняются следующие условия дополняющей нежесткости:. Теорема 4 позволяет определить оптимальное решение одной из пары двойственных задач по решению другой. Если ограничение одной задачи при подстановке оптимального решения обращается в строгое неравенство, то соответствующая двойственная переменная в оптимальном решении двойственной задачи равна 0. Если в оптимальном плане одной задачи какая-нибудь переменная положительна, то соответствующее ей ограничение двойственной задачи является уравнением. Дадим экономическую интерпретацию условиям дополняющей нежесткости. Если в оптимальном решении какое-нибудь сырье имеет отличную от 0 оценку, то оно будет израсходовано полностью ресурс является дефицитным. Если сырье расходуется не полностью находится в избытке , то его оценка равна 0. Таким образом, получаем, что двойственные оценки - это мера дефицитности сырья. Оценка показывает, на сколько возрастет значение целевой функции при увеличении запаса соответствующего сырья на 1 ед. Если некоторый вид продукции входит в план производства, то затраты на его производство совпадают со стоимостью произведенной продукции. Если затраты на производство какого-нибудь вида продукции больше стоимости продукции, то продукция не производится. В случае если одна из пары двойственных задач содержит две переменных, ее можно решить графически, а, затем, найти решение двойственной задачи, используя Теоремы 3 и 4. При этом могут возникнуть 3 случая: Найдем оптимальное решение двойственной задачи по теореме равновесия. Запишем условия дополняющей нежесткости. Составить двойственную задачу к задаче из примера раздела 1. Каждая ли симметрическая задача может быть приведена к каноническому виду? Если да, то как это делается? Может ли линия уровня целевой функции быть параллельной вектору целевой функции? Какой вывод можно делать из того, что ОДР не ограничена по направлению, противоположному вектору целевой функции? Можно ли для ЗЛП, содержащей в системе ограничений неравенства разных направлений, построить двойственную задачу? Если в основной задаче отсутствуют условия неотрицательности переменных, то какие последствия это влечет в двойственной задаче задаче? Что можно сказать о решении двойственной задачи, если решение основной задачи не существует по причине несовместимости ее системы ограничений? В каждом из пяти филиалов производственного объединения могут изготовляться изделия пяти видов. Учитывая необходимость углубления специализации, в каждом из филиалов решено выпускать только один вид продукции, при этом каждый из видов изделий должен выпускаться одним из филиалов. Себестоимость каждого изделия в каждом из филиалов различна и задается матрицей C - себестоимость производства i-м филиалом j-го вида продукции. Найти распределение выпуска продукции между филиалами, чтобы общая себестоимость выпущенной продукции была минимальной. Подобную задачу можно решать симплекс-методом, но можно использовать специальный метод - венгерский метод. В каждой строке находим минимальный элемент и вычитаем его из всех элементов соответствующей строки. В каждом столбце находим минимальный элемент и вычитаем его из всех элементов соответствующего столбца. Проводим минимальное количество вертикальных и горизонтальных линий, пересекающих все нули. Если таких количество таких линий равно количеству строк матрицы С, то 2-ой этап завершен. В противном случае выберем среди неперечеркнутых элементов минимальный и построим новую матрицу по правилам:. Находим строку или столбец матрицы, в которой имеется единственный 0. Если такой строки или столбца нет, то берем любую строку или столбец, содержащие нули. Тогда в матрице X и все остальные элементы i-ой строки и j-го столбца равны 0. Если в матрице С остался один элемент, то соответствующий элемент матрицы X равен 1 и этап 3 закончен. Иначе переходим на п. В матрице С исключаем из дальнейшего рассмотрения 1-ю строку и 1-ый столбец. В матрице С исключаем из дальнейшего рассмотрения 5-ю строку и 3-ий столбец. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования. Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики. Решение задачи линейного программирования графическим способом. Проверка плана на оптимальность. Анализ и корректировка результатов решения задач линейного программирования симплексным методом. Применение линейного программирования для решения транспортной задачи. Свойство системы ограничений, опорное решение задачи. Методы построения начального опорного решения. Распределительный метод, алгоритм решения транспортной задачи методом потенциалов. Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Способы решения задач линейного программирования с вещественными числами симплекс-методом. Общие задачи, формы записи, максимизация и минимизация функции методом искусственного базиса. Пути поиска и исключения из базиса искусственных переменных. Графическое решение задач линейного программирования. Решение задач линейного программирования симплекс-методом. Возможности практического использования математического программирования и экономико-математических методов при решении экономических задач. Математическая формализация оптимизационной проблемы. Геометрическая интерпретация стандартной задачи линейного программирования, планирование товарооборота. Сущность и алгоритм симплекс-метода. Постановка транспортной задачи, последовательность решения. Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей. Предмет и задачи теории игр. Сведение матричной игры к задачам линейного программирования. Основные принципы разработки деловых игр для исследования экономических механизмов. Решение матричной игры в смешанных стратегиях. Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т. PPT, PPTX и PDF-файлы представлены только в архивах. Главная Коллекция рефератов "Otherreferats" Экономико-математическое моделирование Методы оптимальных решений. Различные формы записи задачи линейного программирования. Специальные задачи линейного программирования. Сведение матричной игры к задаче линейного программирования. Графическое решение задачи нелинейного программирования. Специальные задачи линейного программирования 2. Решение задач, сформулированных на базе построенной математической модели. Реализация полученного решения на практике. Для математического описания экономической задачи можно руководствоваться следующей общей схемой: Эти соотношения образуют систему ограничений математической модели; 3 поиск наилучшего решения формулируют в терминах поиска оптимального максимального или минимального значения функции. Задача линейного программирования задана в канонической форме , если требуется максимизировать целевую функцию, все ограничения системы - уравнения и на все переменные наложено условие неотрицательности. Набор чисел называется допустимым решением планом , если он удовлетворяет системе ограничений ЗЛП. Множество всех допустимых решений называется областью допустимых решений ОДР. Допустимое решение , для которого достигается максимальное минимальное значение функции, называется оптимальным планом ЗЛП. Все три формы записи ЗЛП являются эквивалентными в том смысле, что имеются алгоритмы перехода от одной формы к другой. Таким образом, если имеется способ решения задачи в одной из форм, то всегда можно определить оптимальный план задачи, заданной в любой другой форме. Задача в симметричной форме решается графическим методом, а в канонической форме - симплекс-методом. Рассмотрим алгоритмы перехода от одной формы к другой. Переход осуществляется путем добавления в левую часть каждого неравенства дополнительной неотрицательной переменной. Вводимые новые переменные называются балансовыми. Для осуществления такого перехода находится общее решение системы уравнений - ограничений, целевая функция выражается через свободные переменные. Далее, воспользовавшись неотрицательностью базисных переменных, можно исключить их из задачи. Симметричная форма задачи будет содержать неравенства, связывающие только свободные переменные, и целевую функцию, зависящую только от свободных переменных. Значения базисных переменных находятся из общего решения исходной системы уравнений. Каждая переменная, на которую не было наложено условие неотрицательности, представляется в виде разности двух новых неотрицательных переменных. Неравенства преобразуются в уравнения путем введения в левую часть каждого неравенства балансовой переменной таким же образом, как это было описано при переходе от симметричной к канонической форме. Задачу минимизации функции Z заменяют на задачу максимизации функции -Z таким же образом, как это было описано при переходе от симметричной к канонической форме. Пример 1 Следующие множества точек на плоскости являются выпуклыми: Следующие множества точек на плоскости не являются выпуклыми: Пример 2 Следующие множества являются многоугольниками. Пример 3 Угловыми точками треугольника являются его вершины их три. Угловая точка многогранника называется его вершиной. Рассмотрим ЗЛП, заданную в симметричной форме. Для графического решения задачи ЗЛП используют следующий алгоритм: Вычисляют координаты оптимальной точки и значение функции Z в этой точке. Пример 1 Решить графически ЗЛП: Решение Каждое неравенство исходной системы ограничений определяет полуплоскость. Для нахождения ее координат решим систему: Пример 2 Пусть имеются два пункта, расстояние между которыми равно км. Между ними необходимо осуществить связь, имеющую 12 телефонных, 31 телеграфных и 18 фототелеграфных каналов с помощью кабелей двух типов, обладающих следующими характеристиками: Каналы Количество каналов для кабеля типа I II Телефонные 1 3 Телеграфные 5 4 Фототелеграфные 2 3 Стоимость 1 км кабеля в у. Получаем ограничения на количества имеющихся каналов: Получаем математическую модель задачи: До вызова Поиск Решения необходимо подготовить данные для решения задачи из математической модели: Определить ячейки, в которые будет помещен результат решения изменяемые ячейки. Ввести данные системы ограничений коэффициенты при неизвестных и правую часть. Ввести зависимости от изменяемых ячеек для левых частей системы ограничений. Ввести зависимость от изменяемых ячеек для целевой функции. Ниже перечислены основные поля и органы управления названных диалоговых окон. Ниже описаны значения полей, переключателей и флагов этого диалогового окна: Появится диалоговое окно Поиск решения , которое необходимо заполнить следующим образом для добавления ограничений пользуемся кнопкой Добавить: Результаты поиска решений для ячеек В2 и С2 установлены числовые форматы с 0 знаками после запятой: Решение совпадает с найденным графическим способом. Для изготовления двух видов продукции P 1 , P 2 предприятие использует 4 вида сырья S 1 , S 2 , S 3 , S 4. Запасы сырья и расходы на изготовление каждого вида продукции приведены в таблице. Составить план производства, при котором стоимость выпущенной продукции будет максимальной. Сырье Запасы Расход на единицу продукции P 1 P 2 S 1 20 3 2 S 2 16 4 1 S 3 30 0 3 S 4 40 4 0 Стоимость единицы продукции у. Предприятие не может израсходовать сырья больше, чем у него имеется, поэтому получаем следующие ограничения на использование имеющегося сырья: Переменные обеих задач не отрицательны. Пусть имеется задачи линейного программирования в общем виде: Каждой задаче такой можно поставить в соответствие двойственную задачу: Построение двойственной задачи происходит по следующим правилам: Цель двойственной задачи противоположна цели исходной задачи. Матрица системы ограничений двойственной задачи получается транспонированием из матрицы системы ограничений исходной задачи; Коэффициенты правых частей двойственной задачи - это коэффициенты при неизвестных в целевой функции исходной задачи. Пример 1 Построим двойственную задачу для задачи Согласуем знаки неравенств с целью задачи. Матрица левой части системы ограничений исходной задачи: Матрица левой части системы ограничений двойственной задачи: Следующие теоремы дают зависимости между решениями пары двойственных задач. Эти планы являются оптимальными тогда и только тогда, когда выполняются следующие условия дополняющей нежесткости: Пример 2 Составить двойственную задачу и найти ее решение по теореме равновесия , если известно решение исходной задачи: Согласуем знаки неравенств с целью исходной задачи. Подставим в составленную систему оптимальное решение исходной задачи: Произведение равно нулю, если один из множителей равен 0. Получаем Тогда, Оптимальное решение двойственной задачи По Теореме 3. Пример 3 Составить двойственную задачу к задаче из примера раздела 1. Знаки неравенств уже согласованы с целью задачи. Получаем Тогда, Вычтем из первого уравнения второе: Оптимальное решение двойственной задачи По Теореме 3. Окончательно, Вопросы для самопроверки 1. Может ли система ограничений общей ЗЛП включать строгие неравенства? Может ли целевая функция ЗЛП содержать нелинейные выражения из переменных? Может ли допустимое решение ЗЛП содержать отрицательную компоненту? Чем отличается оптимальное решение ЗЛП от допустимого? Чем отличается канонический вид ЗЛП от общего? Может ли каноническая задача быть приведена к общему виду? Какое максимальное число неравенств может содержать ЗЛП с двумя переменными? Как строится ОДР ЗЛП с двумя переменными? Может ли ОДР быть невыпуклым многоугольником? Может ли ОДР быть открытым множеством? Что такое линия уровня? Может ли ЗЛП с двумя переменными иметь два и только два оптимальных решения? В каком случае задача ЛП с двумя переменными не имеет решения? Сколько переменных может содержать ЗЛП, которую можно решить графически? Чем отличаются матрицы систем ограничений в паре двойственных задач? Какова связь между экстремальными значениями пары двойственныхзадач? В чем смысл теоремы равновесия? Составим математическую модель задачи. Каждая вид продукции должен выпускаться: В противном случае выберем среди неперечеркнутых элементов минимальный и построим новую матрицу по правилам: Далее переходим на п. В матрице С вычеркиваем i -ю строку и j -ый столбец. Решим сформулированную выше задачу. Этап 1 Этап 2 Этап 3 Порядок составления матрицы X: Решение задачи линейного программирования симплекс-методом. Решение задач линейного программирования. Методы линейного программирования для решения транспортной задачи. Примеры использования графического и симплексного методов в решении задач линейного программирования. Исследование операций в экономике. Оптимизационные задачи в экономике и алгоритмы решения некоторых задач линейного программирования. Применение графического метода и симплекс-метода для решения задач линейного программирования. Моделирование оптимизационных задач экономики с использованием теории игр. Другие документы, подобные "Методы оптимальных решений".
Быстро поправиться в ногах
Текст про лучшую подругу
Смеяться над собой афоризмы
Гигиенические нормативы 169
Таблица зольского района по футболу
Расписание рейсов хабаровск москва