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

Графический метод используется для решнения задач с 2-мя переменными следующего вида:

Z(x)= c1x1+c2x2+…+cnxn-àmax (1)

 

a11x1+a12x2≤b1 (≥b1)

a21x1+ a22x2≤b2 (≥b2)

……………………….

Am1x1+ am2x2≤bm(≥bm)

X1≥0, x2≥0

 

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

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

Областью решения линейного неравенства ai1x1+ ai2x2≤bi является одна из двух полуплоскостей, на кот. прямая ai1x1+ ai2x2=0, соответствующая данному неравенству, делит координатную плоскость.

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

Для нахождения среди допустимых решений оптимальные решения используют линии уровня и опорные прямые.

Определение: Линией уровня называется прямая, на которой целевая функция принимает постоянное значение.

Уравнние линии уровня в общем случае имеет вид: c1x1+c2x2=l (c)где l (c) – const/ Все линии уровня и между собой их норм. n=(c1; c2).

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

 

 

Значение z(x) на линии уровня возрастают, если линии уровня перемещать в направлении их нормали и убывают при перемещении линии уровня в обратном направлении.

 

 

Основные теоремы двойственности.

Теорема двойственности в ЛП строится на след.основных теремах:

1)Если одна из ЗЛП имеет конечный оптимум,то и двойственная к ней также имеет конечный оптимум,причем оптимальные значения линейных форм задач совпадают. F_max =Z_min.

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

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

 

 

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

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

2. Если ОДР является пустым множеством, то задача не имеет решения в виду не совместимости системы ограничений.

3. Если ОДР является пустым множеством, построим нормаль линии уровня n=(C1;C2) и одну из линий уровня, имеющую общие точки с этой областью.

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

5. Если при перемещении линии уровня по ОДР в направлении соответствующем приближению к экстремуму z(x). Линия уровня уходит в бесконечность, то задача не имеет решения в виду неограниченности z(x). Fmax=∞, Fmin=∞

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

7. После нахождения оптимальных решений вычислить значение z(x) на этих решениях.

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

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) задачи ЛП имеют оптимальные решения в одной из угловых точек выпуклого множества системы неравенств