Методы принятия оптимальных решений

Размещено на http://www.allbest.ru/

Математические модели в экономике и управлении

математический модель программирование

Математическое моделирование получило широкое распространение в исследовании экономических систем. Это обусловлено тем, что экономические системы характеризуются сложными количественными взаимосвязями, которые можно выразить как взаимосвязь множества переменных и которые хорошо поддаются математическому описанию в виде уравнений и неравенств.

Таким образом, математическая модель экономической системы - это достаточно точное описание этой системы с помощью математического аппарата (систем уравнений, неравенств, различного рода функций, графиков, логических отношений и т.д.).

Моделирование и построение математической модели экономического объекта позволяют свести экономический анализ производственных процессов к математическому анализу и принятию эффективных решений.

Различие взаимосвязей экономических систем и возможностей их описания в математической форме привело к необходимости разделить экономико-математические модели на классы:

Модели макроэкономики описывают те процессы и проблемы, которые существуют на макроэкономическом уровне и которые могут быть решены ее же средствами.

Параметрами модели макроэкономики могут быть занятость, совокупный спрос, совокупное предложение, национальный доход, инфляция, экономический рост, инвестиция, совокупный уровень цен.

Динамические модели отражают весь экономический процесс, т.е. переход из исходного состояния в конечное. Здесь решающим является фактор времени. Теоретические модели позволяют изучать общие свойства экономики и ее характерные элементы дедукцией выводов из формальных предпосылок. Прикладные модели дают возможность оценить параметры функционирования конкретного экономического объекта и сформулировать рекомендации для принятия практических решений. Детерминированные модели предполагают жесткие функциональные связи между переменными модели. Стохастические модели допускают наличие случайных воздействий на исследуемые показатели и используют инструментарий теории вероятностей и математической статистики для их описания. Корреляционно-регрессионные модели представляют собой уравнения связей зависимого и нескольких независимых факторов. Микроэкономические модели описывают взаимодействие отдельных элементов экономической системы в рыночной сфере.

Оптимизационные модели основываются на математическом программировании, т.е. разделе математики, связанном с изучением и разработкой методов решения экстремальных задач, отысканием экстремальных значений функций, т.е. выбором оптимальных вариантов.

Использование оптимизации для идентификации параметров математической модели

Оптимизационные модели характеризуются системой математических уравнений и неравенств экономической задачи, объединенных какой-либо целевой функцией, при решении которой определяется наилучшее решение.

При решении экономических задач ставится определенная цель, которую необходимо достичь. Однако в большинстве случаев мы располагаем ограниченным количеством средств или ресурсов для достижения этой цели.

Экономико-математические модели включают в себя систему ограничений, целевую функцию. Система ограничений состоит из отдельных математических уравнений или неравенств, называемых балансовыми уравнениями или неравенствами. Целевая функция связывает между собой различные величины модели. Как правило, в качестве цели выбирается экономический показатель (прибыль, рентабельность, себестоимость, валовая продукция и т.д.)

Решением экономико-математической модели, или допустимым планом называется набор значений неизвестных, который удовлетворяет ее системе ограничений. Модель имеет множество решений, или множество допустимых планов, и среди них нужно найти единственное, удовлетворяющее системе ограничений и целевой функции. Возникает проблема выбора из множества вариантов решения задачи того, который обеспечивает наилучшее или наиболее эффективное распределение ресурсов. Этот наилучший вариант и называется оптимальным. Выбор оптимального варианта определяется каким-либо показателем, который называется критерием оптимизации.

Таким образом, для принятия оптимального решения любой экономической задачи необходимо построить ее экономико-математическую модель, по структуре включающую в себе систему ограничений, целевую функцию, критерий оптимальности и решение.

Теория оптимизации и методы выбора экономических решений

В общем виде математическая постановка оптимизационной задачи состоит в определении максимума или минимума целевой функции при условиях , где - заданные функции; - искомые переменные; - некоторые действительные числа.

В зависимости от свойств функций методы принятия оптимальных решений подразделяются на методы решения задач линейного и нелинейного программирования.

Если все функции являются линейными или не содержат произведения искомых переменных, соответствующая задача - это задача линейного программирования. Если хотя бы одна из функций - нелинейная, то соответствующая задача - задача нелинейного программирования.

Среди задач нелинейного программирования наиболее изучены задачи выпуклого программирования, в результате решения которых определяют минимум выпуклой (или максимум вогнутой) функции, заданной на выпуклом замкнутом множестве. В задачах целочисленного программирования неизвестные могут принимать только целочисленные значения. В задачах дробно-линейного программирования целевая функция - отношение двух линейных функций. Задача динамического программирования - задача, процесс нахождения решения которой является многоэтапным.

Если в целевой функции или в функциях, определяющих область возможных изменений переменных, содержаться случайные величины, то такую задачу относят к стохастическому программированию.

Формулировка задачи линейного программирования

Существует множество форм деятельности предприятий, которые связаны с распределением ресурсов. Эти ресурсы включают труд, сырье, оборудование и денежные средства. Цель предприятия состоит в определении наиболее эффективного метода такого распределения ресурсов по соответствующим переменным, которое оптимизирует некоторый результат функционирования системы. Например, наладить производство таким образом, чтобы максимизировать общий выпуск продукции за месяц, максимизировать время использования оборудования за неделю или минимизировать еженедельные затраты труда.

Линейное программирование является подходящим методом для моделирования распределения ресурсов, если цель и ограничения на ресурсы можно выразить количественно в форме линейных взаимосвязей между переменными.

В задаче линейного программирования целевая функция представляет собой линейную форму вида:

а система ограничений на переменные - систему линейных уравнений и неравенств:

Каждое решение системы представляет собой совокупность значений переменных , удовлетворяющих всем неравенствам системы.

Стандартная (нормальная) и каноническая формы представления задачи ЛП и сведение к ним

Математическая модель ЗЛП может быть канонической и неканонической.

Если все ограничения системы заданы уравнениями и переменные неотрицательные, то такая модель задачи называется канонической. Если хотя бы одно ограничение является неравенством, то модель ЗЛП является неканонической. Чтобы прейти от неканонической модели к канонической, необходимо в каждое неравенство ввести балансовую переменную . Если знак неравенства ?, то балансовая переменная вводится со знаком +, если знак неравенства ?, то со знаком -. В целевую функцию балансовые переменные не вводятся.

Свойства допустимого множества и оптимального решения в задаче ЛП

Определение. Допустимым планом (допустимым решением) задачи линейного программирования называется вектор , удовлетворяющий системе ограничений. Множество допустимых решений образует область допустимых решений.

Допустимое решение, при котором целевая функция достигает своего экстремального значения, называется оптимальным решением ЗЛП и обозначается .



Выпуклые множества в n-мерном пространстве

Рассмотрим на плоскости Х1ОХ2 совместную систему линейных неравенств.

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой . Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми . Система совместна, поэтому полуплоскости как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы. Совокупность этих точек называется многоугольником решений. Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью.

Свойства решений задачи линейного программирования

Теорема 1. Множество всех планов задачи линейного программирования выпукло.

Теорема 2. Целевая функция задачи линейного программирования может достигать экстремального значения только в угловой точке области допустимых решений.

Таким образом, для нахождения оптимального решения задачи линейного программирования нет необходимости перебирать все допустимые решения, а достаточно ограничиться перебором лишь конечного числа возможных решений угловых точек многоугольника.

Графический метод решения ЗЛП

Наиболее простым и наглядным методом решения ЗЛП является графический метод. Он основан на геометрической интерпретации ЗЛП и применяется при решении ЗЛП с двумя переменными.

Алгоритм графического метода решения ЗЛП.

1. Строится область допустимых решений (ОДР) ЗЛП.

2. Строится вектор-градиент целевой функции с началом в точке О(0,0).

3. Проводится линия уровня, которая перпендикулярна вектору .

4. Линия уровня перемещается по направлению вектора для задач на максимум и в направлении, противоположном для задач на минимум. Перемещение производится до тех пор, пока у нее не окажется только одна общая точка с областью допустимых решений. Эта точка, определяющая единственное решение ЗЛП, и будет точкой экстремума. Если окажется, что линия уровня параллельна одной из сторон ОДР, то в таком случае экстремум достигается во всех точках соответствующей стороны, а ЗЛП будет иметь бесчисленное множество решений. ЗЛП может быть неразрешимой, когда определяющие ее ограничения окажутся противоречивыми. Находим координаты точки экстремума и значение целевой функции в ней:

1. Построение опорных планов.

2. Отыскание оптимального плана. Условия оптимальности.

3. Алгоритм симплексного метода.

Построение опорных планов

Симплексный метод является универсальным, т.е. может быть применен при решении любой задачи линейного программирования. В основе симплексного метода лежит алгоритм симплексных преобразований системы. Он позволяет, исходя из известного опорного плана (базисного решения) задачи, за конечное число шагов получить ее оптимальный план. Идея симплексного метода содержит три существенных момента:

- указывает способ нахождения первоначального опорного плана;

- устанавливает критерий оптимальности опорного плана;

- указывает способ перехода от неоптимального плана к лучшему плану, более близкому к оптимальному.

Таким образом, идея симплекс - метода заключается в последовательном улучшении плана. Решение ЗЛП симплекс-методом проводится в симплексных таблицах, которые заполняются после нахождения исходного базисного (опорного) решения.

Отыскание оптимального плана. Условия оптимальности

Теорема. Если после выполнения очередной итерации:

1) найдется хотя бы одна отрицательная оценка Дj для задачи на max (положительная для задачи на min) и в каждом столбце с такой оценкой будет хотя бы один положительный элемент, то можно улучшить план, выполнив следующую итерацию;

2) найдется хотя бы одна отрицательная (положительная) оценка, столбец которой не содержит положительных элементов, то функция Z неограниченна в области допустимых решений, т.е. ;

3) все оценки окажутся неотрицательными для задач на max (не положительными для задач на min), то найдено оптимальное решение.

Алгоритм симплексного метода

Математическая модель задачи должна быть канонической. Если она неканоническая, то ее надо привести к каноническому виду.

Исходная задача должна содержать базисные переменные, т.е. вектора образующие единичную матрицу.

Для задачи на определения максимума.

Шаг 1. Заполняем первую симплекс-таблицу

Шаг 2. Проверяем план на оптимальность: все .

а) план оптимален, то выписываем решение,

б) задача неразрешима

в) иначе переходим к шагу 3.

Шаг 3. Выбираем разрешающий столбец:

Шаг 4. Выбираем разрешающую стороку:

Шаг 5. На пересечение разрешающего столбца и строки стоит разрешающий элемент. В базисе вектор стоящий в разрешеющей строке заменяем на вектор стоящий в разрешающем столбце.

Шаг 6. Пересчитываем новую симплекс- таблицу по методу Жордана-Гаусса.

В задаче на определение минимума изменяются следующие шаги.

Шаг 2. Проверяем план на оптимальность: все .

а) план оптимален, то выписываем решение,

б) задача неразрешима

в) иначе переходим к шагу 3.

Шаг 3. Выбираем разрешающий столбец: .

Алгоритм метода Жордана-Гаусса:

1. Разрешающая строка делится на разрешающий элемент.

2. Разрешающий столбец дополняется нулями.

3. Если в разрешающей строке (столбце) имеются нули, то соответствующие им столбцы (строки) переписываются без изменения.

4. Остальные элементы вычисляются по правилу «прямоугольника»: Новый элемент равен разности произведений чисел, стоящих по диагоналям, деленной на разрешающий элемент, причем первое произведение берется с разрешающим элементом:

1. Применение метода искусственного базиса.

2. Теорема для отыскания оптимального плана исходной задачи.

3. Решение задачи методом искусственного базиса.



Применение метода искусственного базиса

Иногда при решении ЗЛП в матрице коэффициентов при неизвестных системы ограничений нет единичных столбцов, из которых можно составить единичную матрицу, т.е. возникает проблема выбора базисных переменных, либо первоначальное решение является недопустимым. В таких случаях используют метод искусственного базиса (М - метод).

М-метод заключается в применении правил симплекс-метода к так называемой М-задаче. Она получается из исходной задачи добавлением к левой части системы уравнений исходной канонической ЗЛП таких искусственных единичных векторов с соотвествующими неотрицательными искусственными переменными, чтобы вновь полученная матрица содержала систему единичныхлинейно независимых векторов.

Теорема для отыскания оптимального плана исходной задачи

В целевую функцию искусственные переменные вводятся с коэффициентом (- М) для задач на max и с коэффициентом (+ М) для задач на min, где М - достаточно большое положительное число. В процессе решения М-задачи следует вычеркивать в симплекс-таблице искусственные векторы по мере их выхода из базиса.

Если все искусственные векторы вышли из базиса, то получаем систему уравнений, равносильную системе уравнений исходной задачи. Если оптимальное решение М-задачи содержит искусственные переменные или М-задача неразрешима, то исходная задача также неразрешима.

Решение ЗЛП методом искусственного базиса

Найти максимальное значение функции при условиях

Составим матрицу коэффициентов системы уравнений:

В матрице нет единичных векторов, из которых можно образовать единичную матрицу, т.е. возникает проблема выбора базисных переменных в каждом из уравнений.

Введем искусственные переменные

Введем их в целевую функцию с коэффициентами (-М), т.к. решается задача нахождения максимуму:

Единичную матрицу образуют коэффициенты при неизвестных , значит эти переменные являются базисными. А так как они являются искусственными переменными, то исходный базис называют искусственным. Переменные х1, х2, х3 и х4 являются свободными.

Таким образом, мы получили расширенную ЗЛП, и будем решать ее симплекс-методом.

min (Дj < 0) = Д2 = - 6М - 3, значит в базис введем переменную х2, значит, из базиса выводим искусственную переменную y1 , поэтому столбец y1 в следующей таблице можно не заполнять.

Производим заполнение второй таблицы по правилам симплекс-метода.

min (Дj < 0) = Д1 = - М - 1, значит в базис введем переменную х1, значит, из базиса выводим искусственную переменную y2 , поэтому столбец y2 в следующей таблице можно не заполнять.

В третьей таблице обе искусственные переменные оказались равными нулю и все, следовательно, получено оптимальное решение исходной задачи.

Ответ:

1. Определение двойственности.

Каждой задаче линейного программирования можно сопоставить определенным образом с ней связанную другую задачу, которая называется двойственной по отношению к первой.

Первоначальная задача называется исходной. Вместе взятые задачи образуют пару взаимно - двойственных задач.

Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой. Совместное рассмотрение таких пар двойственных задач оказывается весьма эффективным средством теоретического исследования проблем линейного программирования и построения различных вычислительных методов. Кроме того, рассмотрение двойственных задач играет большую роль при экономическом анализе результатов расчета.

Правила составления двойственной задачи:

1) если целевая функция исходной задачи формулируется на максимум, то целевая функция двойственной задачи - на минимум (и наоборот), при этом в двойственной задаче на максимум все неравенства в ограничениях имеют вид ?, а в задаче на минимум - вид ?;

2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица в двойственной задаче получаются друг из друга транспонированием;

3) число переменных в двойственной задаче равно числу ограничений исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной;

4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи - коэффициенты при неизвестных в целевой функции исходной;

5) каждому ограничению одной задачи соответствует переменная другой задачи, номер переменной совпадает с номером ограничения. При этом ограничению, записанному в виде неравенства ?, соответствует переменная, связанная условием неотрицательности.

Если ограничение исходной задачи является равенством, то соответствующая переменная двойственной задачи может принимать как положительные, так и отрицательные значения.



Симметричные и несимметричные двойственные задачи

Различают симметричные, несимметричные и смешанные двойственные задачи.

Симметричные двойственные задачи

В симметричных задачах система ограничений как исходной, так и двойственной задачи задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.

Дана исходная задача

при ограничениях

Задача дана в неканоническом виде. Составим математическую модель двойственной задачи, согласно записанным правилам:

при ограничениях

Несимметричные двойственные задачи

В несимметричных задачах система ограничений исходной задачи задается в виде равенств, а система ограничений двойственной в виде неравенств, причем если в целевой функции двойственной задачи требуется найти минимум, то знак неравенств ?, если максимум, то ?. Кроме того, в двойственной задаче переменные могут принимать любое значение, в том числе и отрицательные.

Дана исходная задача

при ограничениях

Задача дана в неканоническом виде. Составим математическую модель двойственной задачи, согласно записанным правилам:

при ограничениях

Смешанные двойственные задачи

Математическая модель исходной задачи имеет условия симметричных и несимметричных задач. При составлении двойственной задачи необходимо выполнять правила симметричных и несимметричных задач.

Зная решение одной из двойственных зада можно найти решение другой задачи

Теорема. Если одна из пары двойственных задач имеет оптимальное решение, то и другая также имеет оптимальное решение, причем для любых оптимальных решений и выполняется неравенство

Если одна из двойственных задач неразрешима ввиду того, что (или ), то другая задача не имеет допустимых решений.

Экономическая интерпретация на основе производственной задачи

Рассмотренная симметричная пара взаимно двойственных задач может быть экономически интерпретирована, например, так.

Прямая задача: сколько и какой продукции надо произвести, чтобы при заданных стоимостях единицы продукции , объемах имеющихся ресурсов и нормах расходов максимизировать выпуск продукции в стоимостном выражении.

Двойственная задача: какова должна быть оценка единицы каждого из ресурсов , чтобы при заданных , и минимизировать общую оценку затрат на всю продукцию.

Оптимальное распределение ресурсов

Допустим для производства продукции используются некоторые ресурсы (сырье, оборудование, финансы, рабочая сила) в количествах . Стоимость единицы ресурса равна тенге. Производство продукции ограничено спросом, который оценивается в количестве штук . Единица продукции может быть продана по цене и для ее производства необходимо единиц ресурса (i=1,2,…,m).

Необходимо решить следующую задачу: какое количество продукции необходимо выпустить, чтобы получить максимальную прибыль при ее реализации?

Виды продукции

Ресурсы

Стоимость

Спрос

Количество ресурса

Стоимость ресурса

Обозначим через количество единиц выпускаемой продукции. Не следует выпускать продукции больше, чем диктуется спросом, т.е.

Количество ресурса израсходованного на производство всех рассматриваемых видов продукции , будет равно:

Учитывая, что количество ресурса равно получим ограничение, определяющее расход ресурса:

Аналогично записываются ограничения, определяющие фактический расход любого из ресурсов , т.е.

Очевидно, что количество единиц производимой продукции не может быть отрицательным числом, следовательно:

Прибыль, получаемая от реализации продукции, определяется разностью между ценой произведенной продукции и ее себестоимостью , т.е.

В итоге получаем математическую форму записи задачи о распределении ресурсов: определить количество выпускаемой продукции , которое удовлетворяет линейным неравенствам (1.1)-(1.3) и обеспечивает максимум прибыли - линейной целевой функции (1.4).

Загрузка оборудования

Производство располагает станками трех типов в количествах N1, N2, N3 штук соответственно. Станки могут производить шесть видов продукции: Р1, Р2, Р3, Р4, Р5, Р6. Единица продукции Рj приносит производителю доход cj (j=1,2,…,6). В соответствии с планом должно выпускаться не менее bj (j=1,2,…,6) единиц продукции Рj в месяц.

Каждый тип станка может производить любой из перечисленных видов продукции, но в разных количествах. Станок i-го типа (i=1,2,3) может изготавливать единиц готовой продукции (j=1,2,…,6) в месяц. Вопрос: на каких станках производить продукцию, чтобы месячный план был выполнен и стоимость изготовленной продукции была максимальна?

Математическая модель задачи будет иметь вид:

Полная стоимость изготовленной продукции равна

Система ограничений по количеству станков

Согласно имеющемуся плану задание по производству продукции может быть выполнено или перевыполнено. Поэтому соответствующая система ограничений записывается следующим образом:

Неотрицательность количества произведенной продукции выражается неравенством

Таким образом, проблема оптимальной загрузки оборудования формулируется следующим образом: определить план производства, который удовлетворяет системам ограничений (2.2)-(2.4) и обеспечивает максимум прибыли - линейной целевой функции (2.1).

Оптимальный объем производства

Фирма выпускает изделия четырех видов, для производства которых используются пять технологических операций . Рассчитано, что ожидаемая прибыль от продажи изделия равна . Эти технологические операции могут также использоваться для других целей. Поэтому время, в течении которого операции могут производиться для изготовления рассматриваемых изделий, ограниченно длительностью рабочего дня и равно . Длительность технологической операции при изготовлении одного изделия равна . Вопрос: каким должен быть суточный объем производства изделий , чтобы прибыль от их реализации была максимальной?

Условия задачи запишем в таблицу:

Операции

Изделия

Время использования

Стоимость изделия

Запишем математическую модель этой задачи. В качестве управляемых переменных можно выбрать количество изготовляемых изделий . Тогда прибыль от продажи изделий имеет вид:

Ограничения, связанные с возможной продолжительностью операций , выражаются системой неравенств. Система ограничений должна быть дополнена естественными ограничениями которые означают, что количество изготовленных изделий каждого вида не может быть отрицательным.

Формирование торговой сети

В регионе расположены населенные пункты, численность жителей которых известна, а также расстояние и стоимость поездок между ними. Кроме того задано множество типовых проектов предприятий общественного питания. Необходимо найти оптимальный план размещения предприятий общественного питания в регионе, обеспечивающий минимальные приведенные затраты на их строительство, эксплуатацию и на поездки жителей между населенными пунктами.

В качестве критерия оптимальности принимаем приведенные затраты С на строительство, эксплуатацию и поездки населения. Тогда формальная запись задачи представляет следующий вид:

Найти такие типовые варианты q предприятий общественного питания для i-го пункта и численность населения j-го пункта, обслуживаемого предприятиями i-го пункта, которые обеспечивают минимум затрат в соответствии с целевой функцией вида при следующих условиях-ограничениях.

- предложение продукции общественного питания, предоставляемое населению района предприятиями общественного питания i-го пункта, должно соответствовать мощности предприятия:

- потребности населения j-го пункта в продукции, обеспечиваемой предприятиями района, должна быть удовлетворена:

- расстояние от j-го пункта населения до i-го пункта размещения предприятия не должно превышать допустимого радиуса обслуживания

- кроме того, существуют ограничения на переменные .

1. Постановка транспортной ЗЛП и ее математическая модель.

2. Метод дифференциальных рент решения транспортной ЗЛП.

3. Открытая модель транспортной задачи.

Постановка транспортной ЗЛП и ее математическая модель

Транспортными задачами называются задачи определения оптимального плана перевозок груза из данных пунктов отправления в заданные пункты потребления. Постановка транспортной задачи, которая получила название задачи по критерию стоимости, следующая: в n пунктах отправления Ai находятся соответственно а1,…,аn единиц однородного груза, который должен быть доставлен m потребителям Bj в количестве в1,…, вm единиц. Заданы стоимости cij перевозок единицы груза из i-го пункта отправления к j-му пункту потребления.

спланировать перевозки так, чтобы максимально удовлетворить потребности и чтобы суммарные затраты на перевозки всего груза были минимальные.

Различают закрытую и открытую модели транспортной задачи

Имеются m пунктов отправления на которых сосредоточено определенное количество однородного продукта . Имеются n пунктов потребления , в которые необходимо перевезти следующее количество продуктов . Если общая сумма продукта в пунктах отправления равна общей потребности в нем всех пунктов потребления, то такая модель называется закрытой, а если не равна, то модель называется открытой. При решении задачи открытая модель приводится к закрытой путем введения фиктивного пункта отправления и потребления.

Из каждого пункта отправления возможна транспортировка продукта в любой пункт потребления, причем стоимость перевозок единицы груза из i-го пункта отправления в j-й пункт потребления известна.

Требуется составить такой план перевозок, при котором общие транспортные расходы были бы минимальными. При этом весь продукт из пунктов отправления должен быть вывезен, а потребности каждого потребителя удовлетворены полностью.

За неизвестные здесь принимаются перевозимые объемы груза .

Математическая модель транспортной задачи в структурном виде:

при условиях

Транспортная задача также состоит из трех частей: цель задачи, ограничения и условия неотрицательности.

Занесем данные транспортной задачи в специальную таблицу называемую распределительной.

Метод дифференциальных рент решения транспортной ЗЛП

Алгоритм метода дифференциальных рент

1) Заполняется первая распределительная таблица, которая дополняется столбцом для указания избытка и недостатка по строкам и строкой для записи разностей.

2) В каждом из столбцов находится минимальный тариф и обводится кружком.

3) Заполняются клетки с обведенными тарифами, при этом учитываются запасы и потребности соответствующих пунктов, т.е. записывается минимальное число из запаса и потребности.

4) Определяются избыточные (положительные) и недостаточные (отрицательные) строки.

Избыточными считаются строки, в которых остался нераспределенный запас. Если запаса нет, а потребность пункта не удовлетворена, то это недостаточная строка.

Замечание: общая величина избытка совпадает с общей величиной недостатка.

Если остаток в строке равен 0, то в этом случае строка считается положительной при условии, что вторая заполненная клетка, стоящая в столбце, связанном с данной строкой еще одной заполненной клеткой, расположена в положительной строке.

5) Находятся разности между минимальными тарифами, записанными в избыточных строках, и тарифами, стоящими в заполненных клетках в отрицательных строках. Для заполненных клеток стоящих в положительных строках разности не находятся.

6) Выбирается наименьшая из найденных разностей, которая называется промежуточной рентой.

7) Осуществляется переход к новой таблице: тарифы, стоящие в положительных строках переписываются без изменений, а к тарифам стоящим в отрицательных строках прибавляется рента. Затем возврат к пункту 2.

Решение задачи продолжается до тех пор, пока не будут исчерпаны все запасы, и не удовлетворены все потребители.

Замечание: оптимальный план перевозок находим из последней таблицы, а стоимости перевозок берем из первой.

Открытая модель транспортной задачи

Теорема. Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах потребления.

В случае превышения запаса над потребностью вводится фиктивный (n+1) пункт назначения с потребностью и при этом транспортные расходы равны нулю .

Если потребности больше, чем запасы, то вводится фиктивный (m+1) пункт отправления с запасом груза , здесь также транспортные расходы равны нулю .

Постановка задачи целочисленного программирования

Значительная часть экономических задач, относящихся к ЗЛП, требует целочисленного решения, К ним относятся задачи, у которых переменные величины означают количество единиц неделимой продукции, например: выпуск оборудования, распределение производственных заданий между предприятиями, распределение самолетов по линиям и т.д.

В общем виде математическая модель задачи целочисленного программирования имеет вид:

Определить максимальное (минимальное) значение функции:

при ограничениях

Иногда можно получить целочисленное решение, не прибегая к специальным вычислительным приемам. Такой особенностью обладает, например, транспортная задача. Но зачастую оптимальное решение задачи, найденное симплексным методом, не является целочисленным. Его можно округлить до ближайших целых чисел. Однако такое округление может дать решение, не лучшее среди целочисленных решений, или привести к решению, не удовлетворяющему системе ограничений. Для решения задач ЦП разработан ряд вычислительных методов.

При наличии в задаче линейного программирования двух переменных, а в системе ограничений - неравенств она может быть решена графическим методом.

В системе координат Х1ОХ2 находят область допустимых решений, строят вектор и линии уровня. Перемещая линию уровня по направлению для задач на максимум (минимум) находим наиболее удаленную (приближенную) от начала координат точку и ее координаты.

В том случае, когда координаты этой точки нецелочисленные, в области допустимых решений строят целочисленную решетку и находят на ней такие целые числа, которые удовлетворяют системе ограничений и при которых значения целевой функции наиболее близко к экстремальному нецелочисленному решению. Координаты такой вершины и являются целочисленным решением.

Определение оптимального плана задачи целочисленного программирования (метод Гомори)

Одним из основных методов решения задач целочисленного программирования является метод Гомори. Вначале симплексным методом находят оптимальное решение задачи. Если решение целочисленное, то задача решена. Если же оно содержит хотя бы одну дробную координату, то накладывают дополнительное ограничение по целочисленности и вычисления продолжают до получения нового решения. Если и оно является нецелочисленным, то вновь накладывают дополнительное ограничение по целочисленности. Вычисления продолжают до тех пор, пока не будет получено целочисленное решение или показано, что задача не имеет целочисленного решения.

Пусть получено оптимальное решение, которое не является целочисленным, тогда последняя симплекс таблица имеет вид:

Пусть и хотя бы одно - дробные числа.

Введем следующие обозначения и целые части чисел и .

Определение. Целой частью числа называют наибольшее целое число, не превосходящее числа .

Дробную часть чисел и обозначим и, она определяется следующим образом:

Примеры:

Если и хотя бы одно - дробны, то с учетом введенных обозначений дополнительной ограничение по целочисленности примет вид:

Данное ограничение вводится в последнюю симлекс таблицу и решение задачи продолжается дальше.

Примечание. 1) Если - дробное число, а все - целые числа, то задача линейного программирования не имеет целочисленного решения.

2) Ограничение целочисленности может быть наложено не на все переменные, а лишь на их часть. В этом случае задача является частично целочисленной.

1. Понятие об игровых моделях.

2. Приведение матричной игры к задаче линейного программирования.

3. Критерии выбора решений в условиях неопределенности.

Понятие об игровых моделях

Главная задача управленческого персонала любой компании - принятие правильного решения вовремя. Такого рода задачи встречаются во многих сферах человеческой деятельности: в экономике, в политике, в военном деле и др. Довольно часто приходится принимать решения в условиях неопределенности, а именно, возникают ситуации, в которых две (или более) стороны преследуют различные цели, а результаты любого действия каждой из сторон зависят от мероприятий партнера. Например:

1) доход производителя некоторого продукта зависит не только от цены на этот продукт, но и от того, сколько продукта решит купить покупатель по данной цене;

2) при выборе ассортимента товаров, выпускаемых данным предприятием, необходимо учитывать, какой ассортимент товаров будут выпускать другие предприятия. Иначе может оказаться, что товары, выпущенные данным предприятием, не найдут сбыта;

Все ситуации, когда эффективность действия одного участника не зависит от действия других участников, можно разделить на два типа:

1) ситуации, когда интересы участников совпадают. В этих случаях участники должны договориться между собой о совместных действиях;

2) ситуации, когда интересы участников не совпадают. Тогда им не выгодно сообщать друг другу свои решения, так как кто-либо из участников сможет воспользоваться значением чужих решений и получить больший выигрыш. Ситуации такого рода называются конфликтными.

Теория игр занимается построением математических моделей конфликтных ситуаций и разработкой методов решения возникающих в этих ситуациях задач.

Упрощенная модель конфликтной ситуации называется игрой, стороны, участвующие в конфликте - игроками, а исход конфликта - выигрышем.

В игре могут сталкиваться интересы двух или нескольких противников, поэтому игры разделяются на парные и множественные. Игра называется парной, если в ней участвуют два игрока, и множественной, если число игроков больше двух.

Если во множественной игре интересы игроков совпадают, то они могут объединяться, создавать коалиции. Такие игры называются коалиционными.

Наибольшее практическое значение имеют парные игры. Обозначим игроков через А и В. Предполагается, что результат игры (выигрыш) определяется некоторым числом.

Ходом игрока будем называть выбор одного из предложенных правилами игры действий и его осуществлением.

Стратегией игрока называется план, по которому он совершает выбор ходов в течение игры.

Задача теории игр - определение для игроков оптимальной стратегии, т.е. такой стратегии, которая при многократном повторении игры обеспечивает каждому игроку максимально возможный средний выигрыш.

Теория игр является современной, научной методикой принятия оптимальных решений в условиях противоречий, в условиях конфликта, в условиях неполного знания тех обстоятельств, в которых приходится принимать решение.

Рассмотрим простейшую математическую модель конфликтной ситуации, когда имеются два участника и когда выигрыш одного равен проигрышу другого. Такая модель называется антагонистической игрой двух лиц с нулевой суммой. Задача первого игрока - максимизировать свой выигрыш. Задача второго игрока - минимизировать свой проигрыш или минимизировать выигрыш первого игрока. Игру можно представить в виде матрицы, в которой строки - стратегии первого игрока, столбцы стратегии второго игрока, а элементы матрицы - выигрыши первого игрока. Такую матрицу называют платежной (или матрицей игры). В общем случае парную игру с нулевой суммой можно записать платежной матрицей.

Задача каждого из игроков - найти наилучшую стратегию игры, при этом предполагается, что противники одинаково разумны и каждый из них делает все, чтобы получить наибольший доход.

Найдем наилучшую стратегию первого игрока. Пусть игрок А выбирает некоторую стратегию Аi, тогда в наихудшем случае он получит выигрыш, равный . Предвидя такую возможность, игрок А должен выбирать такую стратегию, чтобы максимизировать свой минимальный выигрыш :

Величина -гарантированный выигрыш игрока А - называется нижней ценой игры. Стратегия обеспечивающая получение называется максиминной.

Игрок В, выбирая стратегию, исходит из следующего принципа: при выборе некоторой стратегии Вj его проигрыш не превосходит максимального из значений элементов j-го столбца матрицы, т.е. меньше или равен . Поэтому игрок В, очевидно, выберет такое значение j, при котором его максимальный проигрыш минимизируется:

Величина называется верхней ценой игры, а соответствующая ему стратегия игрока - минимаксной.

Теорема. Нижняя цена игры всегда не превосходит верхней цены игры

Если, то такая игра называется игрой с седловой точкой, а пара оптимальных стратегий - седловой точкой матрицы. Число называется ценой игры. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях.

Решение игр в смешанных стратегиях:

Если игра не имеет седловой точки, то поиск решения игры приводит к применению сложной стратегии, состоящей в случайном применении двух и более стратегий с определенными частотами. Такая сложная стратегия называется смешанной.

Смешанной стратегией игрока А называется применение им чистых стратегий с вероятностями соответственно, причем

Аналогично определяется смешанные стратегии игрока В, как применение чистых стратегий с вероятностями соответственно, причем

Основная теорема теории игр (Теорема Неймана)

Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно среди смешанных стратегий.

Если чистая стратегия применяется с отличной от нуля вероятностью, то она называется активной.

Теорема об активных стратегиях:

Если один из игроков придерживается своей активной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.

Эта теорема имеет большое практическое значение - она дает конкретные модели нахождения оптимальных стратегий при отсутствии седловой точки.

Рассмотрим матричную игру 2x2. Платежная матрица такой игры имеет вид:

Если седловой точки нет, то решением являются смешанные стратегии , которые находятся из решения систем уравнений:

Замечание. Для решения системы (2) достаточно выбрать два уравнения, т.к. после решения системы (1) цена игры v уже найдена. Можно взять первое и третье уравнения либо второе и третье уравнения. Матрицы большой размерности можно упростить, уменьшив их размерность путем вычеркивания дублирующих (одинаковых) и заведомо невыгодных стратегий.

Решение игр с помощью линейного программирования

Каждая конечная игра двух лиц с нулевой суммой может быть представлена как задача линейного программирования.

Пусть игра mxn задана платежной матрицей и не имеет седловой точки. Тогда для отыскания оптимальной стратегии игрока А рассмотрим систему

Разделим на v>0 и обозначим , (i=1,2,…,m). (3)

Тогда имеем систему:

Игрок А стремится сделать свой гарантированный выигрыш v максимальным. Это значит, что величина должна принимать минимальное значение. Таким образом, задача решения игры свелась к следующей задаче линейного программирования: определить такие неотрицательные значения переменных х1,х2,..,хm, чтобы обратилась в минимум линейная функция

Z=x1+x2+…+xm

при условии, что выполняются ограничения (4).

Решая задачу симплекс методом находим хi (i=1,2,..,m), Z=, а затем pi=vixi.

Аналогично для игрока В получаем двойственную задачу линейного программирования:

Итак, решение игры mxn свелось к решению двойственной пары задач линейного программирования. Согласно теоремам теории игр это решение всегда существует.

Критерии выбора решений в условиях неопределенности

В рассмотренных ранее матричных играх предполагалось, что в них принимают участие два игрока, интересы которых противоположны. Поэтому действия каждого игрока направлены на увеличение выигрыша (уменьшения проигрыша). Однако в некоторых задачах, приводящих к игровым, имеется неопределенность, вызванная отсутствием информации об условиях, в которых осуществляется действие (погода, покупательский спрос и т.д.). Эти условия зависят не от сознательных действий другого игрока, а от объективной действительности, которую называют природой. Такие игры называются статистическими или играми «с природой».

Человек в играх с природой стремится действовать осмотрительно в зависимости от конкретной ситуации, природа действует случайно она безразлична к выигрышу, и не стремится использовать промахи игрока. Условия игры задаются матрицей. При выборе оптимальной стратегии игрока А применяются различные критерии принятия решения.

1. Критерий Байеса

При известном распределении вероятностей различных состояний природы критерием принятия решения является максимум математического ожидания выигрыша, то есть

2. Критерий Лапласа

В некоторых задачах, когда вероятности состояний природы неизвестны, для их оценки используются принцип недостаточности основания Лапласа, согласно которому все состояния природы полагаются равновероятными.

Критерием принятия решения является максимум математического ожидания выигрыша, то есть

Если распределение вероятностей состояний природы неизвестно, то используются следующие критерии:

3. Максимальный критерий Вальда

Он основан на выборе стратегии игрока А, при которой минимальный выигрыш максимален. Если руководствоваться этим критерием, надо ориентироваться на худшее в игре и выбирать ту стратегию, при которой выигрыш в худших условиях является максимальным:

4. Критерий минимального риска Сэвиджа

Стратегия выбирается из условия, чтобы не допустить чрезмерно высоких потерь, к которым она может привести. Находится матрица рисков, элементы которой показывают, какой убыток понесет игрок, если для каждого состояния природы он не выберет наилучшей стратегии. Оптимальная стратегии находится из выражения

5. Критерий Гурвица

Выбирается стратегия, при которой достигается

Замечание. Если , критерий Гурвица превращается в пессимистический критерий Вальда, а при - в критерий крайнего оптимизма, рассчитанный на наилучшее стечение обстоятельств. На оказывает влияние степень ответственности лица, принимающего решения по выбору стратегии. Чем хуже последствия ошибочных решений, больше желание застраховаться, тем ближе к единице.

Мы не можем признать окончательное решение, выбранное по какому-либо одному критерию. Поэтому необходимо проанализировать решения, полученные по указанным критериям, и выбрать доминирующий ответ.



Общая постановка задачи динамического программирования

Разновидностью подхода оптимизации в задачах математического программирования является динамическое программирование. Отличительной особенностью решения оптимизационных задач динамического программирования является сведение его к решению более простых «подзадач» и оптимизации целевой функции на каждом этапе. Поэтому задача динамического программирования заключается в многошаговой оптимизации для получения общего результирующего оптимума.

Предметом динамического программирования являются задачи оптимального планирования, носящие динамический характер в том смысле, что при их решении приходится учитывать фактор времени, или структуру объекта исследования, или последовательность операций.

Методом динамического программирования решаются большой спектр задач в экономической практике, например: задачи оптимального распределения капиталовложений, замены оборудования, управления запасами; разработки принципов календарного планирования производства и выравнивания занятости при колебаниях спроса на продукцию и др.

Формально задача динамического программирования имеет общий вид:

при условиях

Целевая функция Z является аддитивной от показателя эффективности каждого шага.

Принцип оптимальности Беллмана

Принцип оптимальности впервые был сформулирован Р.Беллманом в 1953 г. Этот принцип состоит в следующем: Каково бы ни было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.

Беллманом четко были сформулированы и условия, при которых принцип верен. Основное требование - процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияние на предшествующие шаги.

Принцип оптимальности утверждает, что для любого процесса без обратной связи оптимальное управление таково, что оно является оптимальным для любого подпроцесса по отношению к исходному состоянию этого подпроцесса. Поэтому решение на каждом шаге оказывается наилучшим с точки зрения управления в целом.

Алгоритм решения задач с помощью рекуррентных уравнений Беллмана

Рассмотрим последовательность задач, полагая последовательно n=1,2,… при различных состояниях s - одношаговую, двухшаговую и т.д., - используя принцип оптимальности.

На каждом шаге любого состояния системы sk-1 решение Xk нужно выбирать «с оглядкой», так как этот выбор влияет на последующее состояние sk и дальнейший процесс управления, зависящий от sk. Это следует из принципа оптимальности.

Но есть один шаг, последний, который можно для любого состояния sn-1 планировать локально-оптимально, исходя только из соображений этого шага.

Рассмотрим n-й шаг: sn-1 - состояние системы к началу n-го шага, - конечное состояние, Xn - управление на n-м шаге, а - целевая функция (выигрыш) n-го шага.

Согласно принципа оптимальности, Xn нужно выбирать так, чтобы для любых состояний sn-1 получить максимум (минимум) целевой функции на этом шаге.

Обозначим через максимум целевой функции - показателя эффективности n-го шага при условии, что к началу последнего шага система S была в произвольном состоянии sn-1, а на последнем шаге управление было оптимальным называется условным максимумом целевой функции на n-м шаге.

Очевидно, что

Максимизация ведется по всем допустимым управлениям Xn.

Решение Xn, при котором достигается , также зависит от sn-1 и называется условным оптимальным управлением на n-м шаге. Оно обозначается через .

Решив одномерную задачу локальной оптимизации, найдем для всех возможных состояний sn-1 две функции и .

Общая задача нелинейного программирования

Математическая модель задачи нелинейного программирования в общем виде формулируется следующим образом: найти вектор , удовлетворяющий системе ограничений и доставляющий экстремум целевой функции.

Нелинейное программирование применяется при прогнозировании промышленного производства, управлении товарными ресурсами, планировании обслуживания и ремонта оборудования и т.д.

В зависимости от вида целевой функции и системы ограничений разрабатываются специальные методы решения, к которым относятсяметоды множителей Лагранжа, квадратичное и выпуклое программирование, градиентные методы, приближенные методы решения, графический метод.