Объктивно-обусловленные оценки

Объктивно-обусловленные оценки

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

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

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

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

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

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

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

Свойства объективно-обусловленных оценок:

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

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

3. Двойственные оценки позволяют определить нормы заменяемости ресурсов.

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

 

Платежная матрица

Пусть имеем парную конечную игру размерности mxn, т.е. игрок А может принять стратегии А₁, А₂, …, А_n, а игрок B может принять стратегии B₁, B₂, …, B_m. В результате выбора ими любой пары стратегии A_iB_j однозначно будет определен исход (a_ij). Пусть значение (a_ij) известны для всех пар стратегий.

Bj Ai	B1	B2	…	Bn
А1	a11	a12	…	a1n
А2	a21	a22	…	a2n
…	…	…	…	…
Аm	am1	am2	…	amn

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

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

 

 

Симплексный метод

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

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

2) добавочные переменные взять в качестве остальных, выразить основные переменные через свободные, найти базисные решения; если полученное базисное решение будет положительным, то переходят к пункту 4, а если недопустимое – к пункту 3;

3) от полученного недопустимого базисного решения задачи переходят к допустимому или устанавливают, что система ограничений противоречива;

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

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

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

7) выражают новые основные переменные и целевую функцию через свободные переменные, начиная с выделенного уравнения;

8) повторяют пункты 5-7, пока не будет достигнут критерий оптимальности, после этого выписывают компоненты оптимального решения и находят оптимум целевой функции.

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

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

 

 

Некоторые частные случаи

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

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

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

 

 

Свойства и задачи ЛП.

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

2. Если ЗЛП имеет оптимальные решения, то целевая функция принимает max/min в одной из угловых точек многоугольника решений.

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

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

 

Двойственные задачи

1.Составление двойственной задачи.Рассм.2 задачи ЛП:

Эти задачи обладают след.свойствами:

1) В одной задаче ищется max,а в другой min.

2) Коэф.при переменных в линейной формуле одной задачи явл. свободными членами системы ограничений др.задачи.

3)наоборот, своб. члены одной задачи-коэф.при переменных в линейной форме др.задачи.

4)в каждой задаче система ограничений задается в виде неравенста,причем они одного смысла(при нахождении max (≤),а при нахождении min (≥)

5)коэф.при переменных в системе ограничений опис.матрицами:

Кот.явл.транспонированными относительно друг другу.

Число неравенств в системе ограничений одной задачи совпадает с числом переменных 1ой задачи.

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

1.Приводят все неравенства системы ограничений исходной задачи к неравенствам одного смысла.Если в исходной задаче ищется max линейной формы,приводим к виду ≤,если min,то к виду ≥.Для этого неравенства,в кот.это требование не выполяется,умножим на (-1).

2.Выписываем матрицу А,коэф.при переменных исходной задачи,получ.после приобрет.в §1.И сост.матрицу А' трансопонир.относительно матрицы А.

3.Составляют систему огранич.двойств.задачи,взяв в качестве коэф.при переменных элемента матрицы А'.Свободные члены коэф.при переменных в линейной форме исходной задачи и запис.неравенство противопол.смысла по сравнению с неравенством,получ.в §1.

5.Указывают,что необх.найти при решении двойств.задачи (min линейной формы,если в исходной задаче ищется max и наоборот).

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

 

 

Верхние и нижние цены игры

Среди всех чисел i i 1, 2,,m выберем наибольшее. Назовм нижней ценой игры, или максимальным выигрышем максимином. Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно,. Стратегия, соответствующая максимину, называется максиминной стратегией. Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А выбирая стратегию Вj, он учитывает максимально возможный при этом выигрыш для А.

 

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

Термин «седловая точка» также используется для обозначения элемента матрицы, который является наименьшим элементом в своем ряду и наибольшим в своем столбце (или же наоборот, то есть наибольший в ряду и наименьший в столбце).

 

Например, матрица

 

имеет одну седловую точку — «4» в первом ряду третьем столбце меньше, чем элементы в первом ряду матрицы («5», «6», «5»), и больше, чем элементы в третьем столбце («3», «-2»).

 

Матрица

содержит 4 седловых точки — «2» в первом и втором ряду, первом и четвёртом столбце. Данный пример показывает, что матрица может иметь любое количество седловых точек. Так, в матрице, состоящей из одного и того же числа, все элементы являются седловыми.

 

Матрица

 

не имеет седловой точки.

 

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

 

 

Графическое решение игр вида 2×n, m×2

Применяется если хотя бы 1 игрок имеет 2-е стратегии

Игра 2×n

(таблица)

Игра не имеет седловой точки, х1-вероятность применения 1-м игроком 1-й стратегии, х2-1-й игрок, 2-я стратегия, х2=1-х1. у1-вероятность применения 2-м игроком 1-й стратегии и т.д. выигрыш 1-го при применении 2-м 1-й стратегии составляет а11*х1+а22*х2= а11х1+а21(1-х1)+а22=х1(а11-а21+а21)

Аналогично найдем ожидание выигрыша 1-го при применении 2-м – 2-й………n-й стратегии данный в таблице

(таблица)

Видно, что выигрыш 1-го игрока линейно зависит от х1, на оси х1 построим выражение ожидания выигрышей 1-го игрока. Оптимальная стратегия определяется как точка пересечения прямых. Аналогично для 2-го игрока определяется как точка пересечения прямых. Минимизировав его проигрыш.

 

1.Линейное программирование. Исследование операций в экономике. Основные понятия Дисциплина исследование операций имеет важное методологическое значение в системе мат. Подготовки современного экономиста. Наиболее четко реализуются одна из основных идей изучения курса высшей математики, идея матем. моделирования экономических процессов. Исследование операций – наука занимающаяся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами. Операция– всякое управляемое мероприятие направленное на достижение поставленной цели. Результат – зависит от способа ее провидения и организации т.е от выбора некоторых параметров. Всякий определенный выбор параметров- решение. Оптимальные те решения которые предпочтительны другим.	2. Мат. моделирование операций. Для решения экономической задачи необходимо построить мат. модели. При построении модели задача упрощается и схема описывается мат. аппаратов различного рода переменных функций уравнений, неравенств и их систем. Мат. модель экономических процессов называют экономико-математической моделью (ЭММ). В настоящее время разработаны модели которые можно классифицировать по различным признакам: 1)задачи об использовании ресурсов (планирование производства) 2)задачи о рационе (о диете, смесях) 3)задачи о загрузке оборудования (об использовании мощностей) 4)задачи о перевозке грузов от поставщиков к потребителю (транспортные) Задачу о планировании производства можно обобщатькогда предприятие выпускает n-различных изделий продукции p1,p2…pn для их производства требуется m различных видов ресурсов(сырья) S1,S2…Sm. bi – запас сырья. Si известны также технологические коэффициенты aij которые показывают сколько единиц i-го ресурса требуется для изготовления j-го вида изделия(i=1…m, j=1…n) Пусть прибыль получаемая предприятием при реализации 1цы изделия j-го вида = Сj j=1…n. Планируемый период все показатели aij bi Сj предполагаются постоянными. Требуется составить такой план выпуска продукции при котором прибыль предприятия была бы наибольшей. Сведем данные в таблицу: Виды ресурсов Запасы ресурсов Технологические коэффициенты     … j … n   b1 a11 a21 … aij … a1n   b2 a21 a22 … a2j … a2n … … … … … … … … i bi ai1 ai2 … aij … ain … … … … … … … … m bm am1 am2 … amj … amn                 Прибыль   C1 C2 … Cj … Cn Пусть xn –количество ыпущенных изделий n-го вида. Тогда должны выполняться ограничения. (1) Причем x1,x2,…,xn 0 (2) Система линейных неравенств вместе с условием неотрицательности переменных составляют систему ограничений данной задачи по объему соответственного ресурса.В ходе выполнения плана можно использовать весь запас либо его часть. Требуется составить оптимальный план работы предприятия т.е найти такие неотрицательные значения x1,x2,…,xn которые бы удовлетворяли системам ограничений и при которых прибыль от реализации была максимальной (3) Функция F – выражает конечную цель оптимального планирования т.е получение наибольшей прибыли поэтому ее называют целевая функция. Т.к переменные x1,x2,…,xn входят и в целевую функцию и в системе ограничений в 1й степени а показатели aij bi Сj являются постоянными то поставленная задача приобретает собой типичную задачу линейного программирования. Целевая функция в таких задачах носит название – линейная форма функции целей. Система (1) – система функциональных ограничений Неравенство (2) – условия допустимости решения. Задача 1-3 - задача на условный экстремум. Методы решения изучаются в специальном разделе математики –математическое программирование	3. Общая задача ЛП Важная задача экономики – наиболее эффективное использование материальных и трудовых ресурсов. Для их решения и служит математическое программированиев котором изучаются методя принятия оптимальных решений. Предметом МП – является разработка и изучение методов отыскания оптимальных значений функции нескольких переменных при допустимых значениях наложенных на них. Общая задача МП – задача F(x) 1) если система функциональных обозначений состоит только из неравенств то такая задача ЛП – называется стандартной. 2) Если система(1) состоит только из уравнений- каноническая. Общую задачу ЛП можно привести к канонической с помощью введения новых допустимых неотрицательных переменных.	4. Математический аппарат исследования операций. Решение систем m уравнений с n неизвестными. Общий вид такой системы: С помощью метода Гаусса можно установить является ли система несовместной или совместной, а если она совместна то зависима ее уравнения или нет. Уравнения, представляющее собой следствие другого должны быть исключены. Будем считать, что такая проверка выполнена и уравнения системы независимы. Любые m переменные системы m линейных уравнений с n неизвестными(m<n) называются основными, если определитель из коэффициентов при них отличается от нуля, тогда остальные n – m переменные называются не основные(свободные) Основными могут быть разные группы из n переменных. Однако количество различных способов выбора m переменных из общего количества n переменных, конечно и оно равно числу сочетаний . Количество способов разбиения m переменных системы на основные и неосновные ограниченно этим числом и меньше этого числа, если хотя бы один из этих определителей равен 0. Общим решением системы называется такое решение, в котором все основные переменные выражаются через свободные. Базисное решение всякое решение системы, в котором неосновные переменные имеют значение 0. базисных решений системы также будет не более чем . В базисном решении свободные переменные =0 а основные отличаются от 0. но может оказаться что основные также равны 0 такое базисное решение – вырожденное. Замечание: задача ЛП имеет оптимальное решение в одном из допустимых базисных решений и это число ограниченно и не превосходит
5. Выпуклое множество точек. Множества, элементами которых являются точки, называются точечными, примеры: точки круга, прямой, луч, отрезок, угол, сектор и др. Примеры в пространстве: шар, призма. Точечные множества делятся на выпуклые и невыпуклые. Множество точек называется выпуклымесли вместе с его любыми двумя точками ему принадлежит и весь отрезок, соединяющий эти точки. Если существует хотя бы одна пара точек множества, что отрезок соединяющий эти точки не принадлежит целиком этому множеству то множество называется невыпуклым. Теорема:пересечение(общая часть) двух выпуклых множеств также выпуклое множество. Все точки выпуклых множеств можно разделить на 3 группы: внутренние, угловые и граничные. Окрестность точки – круг (шар) бесконечно малого радиуса с центром в этой точке. Внутренняя точка множества – если в некоторой ее окрестности содержатся точки данного множества. Граничная точка множества –если в некоторой ее окрестности содержатся точки принадлежащие и не принадлежащие ему. Угловая точка множества (крайняя)-если через нее нельзя провести не одного отрезка состоящего из точек данного множества и для которого она была бы внутренней. Замечание:1) понятие угловой точки вводится только для выпуклых множеств. Для невыпуклых это определение теряет смысл. 2) задачи ЛП имеют оптимальные решения в одной из угловых точек выпуклого множества системы неравенств

 

Объктивно-обусловленные оценки

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

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

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

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

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

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

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

Свойства объективно-обусловленных оценок:

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

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

3. Двойственные оценки позволяют определить нормы заменяемости ресурсов.

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