шпоры - 2 курс 2 семестр

27) Сформулировать и доказать условие неограниченности целевой функции на множестве допустимых решений при решении задачи линейного программирования симплекс-методом. В частном случае общей задачи ЛП система уравнений имеет предпочитаемый вид, при этом правые части всех уравнений неотрицательны. Допустим необходимо минимизировать целевую функцию L=c1x1+c2x2+...cnxn (1), при условиях: x1 + g1,m+1xm+1 + ... + g1nxn = h1, x2 + g2,m+1 xm+1 + ... + g2nxn = h2, (2) ... ... ... ... xm + gm,m+1 xm+1 + ... + gmnxn = hm и xj≥0, j = 1,2,...n (3). Для решения такой задачи применяется симплексный метод линейного программирования. Из выражения L=L0-∆m+1xm+1-...-∆nxn (1) следует, что базисное решение x1=h1, x2=h2,...xm=hm, xm+1=0,...xn=0 (2) является оптимальным решением задачи ЛП Базисное решение является единственным оптимальным решением задачи ЛП тогда и только тогда, когда в уравнении среди коэффициентов при неизвестных нет ни одного положительного, т. е. условие оптимальности имеет вид ∆j≤0 , j=1,2,…,n. Если же хотя бы один из коэффициентов при свободных неизвестных равен нулю, то будут и небазисные оптимальные решения. Очевидно, оптимальных решений будет еще больше, если среди коэффициентов при свободных неизвестных в уравнении (1) окажется несколько нулевых. Если есть хотя бы одна свободная неизвестная, такая что коэффициент ∆j при ней в последнем уравнении системы положителен, а в первых m уравнениях той же системы среди коэффициентов g1j, g2j, …gmj при ней нет ни одного положительного, то задача линейного программирования неразрешима в силу неограниченности линейной формы L=c1x1+c2x2+...cnxn на множестве неотрицательных решений системы ограничений	28)сформулировать теорему связи решений исходной и вспомогательной задач при решении задачи линейного программирования методом искусственного базиса: Метод искусственного базиса применяется к решению задач линейного программирования в общем случае, когда система ограничений не имеет предпочитаемого вида. Пусть требуется минимизировать (1) при ограничениях: (2) . (3) К данной задаче ЛП непосредственно нельзя применить симплексный метод, т.к. система (2) не имеет предпочитаемого вида, хотя правые части всех ее уравнений можно считать неотрицательными. Поэтому к левой части каждого уравнения системы (2) добавим по одной искусственной неотрицательной неизвестной и образуем следующую систему m линейных уравнений с n+m неизвестными: (4) где (5) Очевидно, в системе (4) неизвестные образуют базисный набор, который принято называть искусственным. Кроме того, образуем искусственную линейную форму: (6) и сформулируем следующую вспомогательную задачу линейного программирования: минимизировать линейную форму (6) при линейных ограничениях (4) и (5). Для решения вспомогательной задачи можно применить симплексный метод, так как система (4) имеет предпочитаемый вид, искусственные неизвестные являются базисными, а правые части всех уравнений неотрицательны. В процессе решения вспомогательной задачи система уравнений (4) будет подвергаться симплексным преобразованиям, в результате которых искусственные базисные неизвестные будут переходить в число свободных, а в базисный набор будут постепенно включаться исходные неизвестные. На некотором этапе процесса решения вспомогательной задачи система уравнений (4) примет такой предпочитаемый вид, что соответствующее базисное решение будет оптимальным решением этой задачи. При этом минимальное значение целевой функции может быть или положительным, или равным нулю, так как функция представляет сумму неотрицательных переменных. Если Smin<0, то исходная задача не имеет решения ввиду противоречивости условий (2) и (3). Действительно, если допустить, что система уравнений (2) имеет неотрицательное решение (α1,α2,...,αn), то вспомогательная задача будет иметь решение (α1,α2,...,αn,0,0,…,0) для которого S=0, что противоречит предположению. Если же S=0, то возможна дальнейшая минимизация.	38.Двойственные (расчетные) оценки ресурсов. Симметричная пара двойственных задач ЛП. Несимметричная пара двойственных задач ЛП, правила составления двойственной задачи для данной задачи ЛП со смешанными ограничениями. Теория двойственности является центральной частью всего ЛП. Она имеет богатое экономическое содержание. В рамках модели ЛП предприятия должна существовать внутренняя система оценки ресурсов, используемых им в процессе производства. Эти оценки связаны с технологическими особенностями данного производственного процесса, характеризуемыми матрицей условий A, со структурой и количеством ресурсов, отпущенных для производственного потребления, описываемых вектором B, а также со структурой внешних цен, на основе которых получается вектор прибылей C. Эти оценки называют расчетными оценками ресурсов. Расчетную оценку единицы ресурса не следует отождествлять с той ценой, по которой предприятию был отпущен этот ресурс. Последняя отражает общественно необходимые затраты на производство единицы ресурса, а расчетная цена показывает только сравнительную ценность этого ресурса на данном предприятии в данных конкретных условиях. В зависимости от вида исходной задачи линейного программирования различают симметричные и несимметричные пары двойственных задач. Если система ограничений исходной задачи состоит из неравенств и на все переменные хj наложено условие неотрицательности, то исходная задача и составленная по определенному правилу двойственная задача образуют симметричную пару двойственных задач. Пусть исходная задача имеет вид: найти наибольшее значение функции при ограничениях: . Правило составления двойственных задач 1.    Каждому ограничению исходной задачи ставится в соответствие двойственная переменная yi, где . 2.    Составляется целевая функция , коэффициентами которой будут свободные члены системы ограничений исходной задачи, а цель задачи меняется на противоположную: . 3.    Составляется система ограничений двойственной задачи, при этом матрица из коэффициентов системы ограничений исходной задачи транспонируется, знак неравенства меняется на противоположный, свободными членами будут являться коэффициенты из целевой функции исходной задачи: (2) 4.    Переменные yi в двойственной задаче также неотрицательны, т.е. . (3) Если двойственную задачу принять за исходную и по данному правилу составить двойственную задачу, то получим исходную задачу. Понятие двойственности является взаимным. В несимметричном случае двойственная задача составляется по тем же правилам, что и в случае симметричной пары, но если двойственная переменная поставлена в соответствие ограничению уравнения, то эта переменная свободна по знаку.
37.Запишите симметричную пару двойственных задач линейного программирования. Прямая задача имеет ограничение ≤, целевая функция максимальна Двойственная ≥,цифровая функция минимальна 2х1+3х2+8х3≥50 y1 2у1+4у2≥100 4х1-7х2+9х3≤ у2 3у1-7у2≥200 F=100х1+200х2+300х3=>max 8у1+9у2≥300 Х1,2,3≥0 G=50у1+60у2=>min 39.Матричная запись пары двойственных задач ЛП (симметричная пара задач с ограничениями-неравенствами и нессиметричная пара,где в одной из задач ограничения имеют вид равенств) Прямая Двойствен AX≤И A*Y≥C х≥0 Y≥0 F=CX=>max G=B*Y=>min Если среди неравенств есть 1 равенство,то нессиметричная пара. 2х1+3х2+8х3≤50 у1 4х1-7х2+9х3=60 у2	40,41,42.Основное неравенство теории двойственности ЛП. Малая теорема двойственности и ее экономическое содержание. Теорема о достаточном условии оптимальности решений пары двойственных задач ЛП. Для любых допустимых решений и прямой и двойственной задач ЛП справедливо неравенство: . Для любого допустимого плана исходной задачи и для любого допустимого в-ра оценок ресурсов общая стоимость всего произведенного продукта не превышает суммарной стоимости ресурсов. Малая теорема двойственности: Для существования оптимального решения пары двойственных задач необходимо и достаточно существование допустимого решения для каждой из них. Теорема о достаточном условии оптимальности решений пары двойственных задач: Если и - допустимые решения пары двойственных задач, для которых выполняется равенство , то и - оптимальные решения соответствующих задач. Согласно этой теореме, план производства продукции и вектор оценок ресурсов является оптимальным, если цена всей произведенной продукции и суммарная оценка ресурсов совпадают	43.Первая основная теорема двойственности и ее экономическое истолкование. Теория двойственности является центральной частью всего ЛП. Она имеет богатое экономическое содержание. Если одна из двойственных задач имеет оптимальное решение, то двойственная ей задача также имеет оптимальное решение, причем экстремумы целевых функций равны, т.е. . Если одна из двойственных задач не имеет оптимального решения, то другая задача также не имеет оптимального решения, причем если одна из задач не имеет оптимального решения из-за неограниченности целевой функции, то другая из-за несовместности системы ограничений. Связь между задачами двойственной пары глубже, чем указано в формулировке теоремы. Оказывается, что симплексный метод, примененный к одной из задач, автоматически приводит к решению другой задачи. Экон.смысл: если задача определения оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения минимальных оценок ресурсов, причем цена продукта, полученного при реализации оптимального плана, совпадает с суммарной оценкой имеющихся ресурсов. Совпадение значений целевых функций для соответствующих решений пары двойственных задач является достаточным условием оптимальности этих решений. Эта т-ма вместе с еще 2-мя теоремами и образует так называемую т-ию двойственности ЛП.
44.Вторая основная теорема двойственности (о дополняющей нежесткости) и ее экономическое истолкование. Для того чтобы допустимые решения исходной и двойственной задач являлись оптимальными решениями соответствующих задач двойственной пары необходимо и достаточно выполнение следующих условий: ; Т.е. если какое-либо нер-во системы ограничений одной из задач не обращается в точное равенство оптимальным решением этой задачи, то соответствующая компонента оптимального решения двойственной задачи должна быть равна 0. Если же какая-либо компонента оптимального решения положительна, то соотв-ее ей ограничение в двойственной задаче должно быть обращено в точное равенство. Другими словами: 1)если хj^0>0,то aijyi^0=cj; 2)если aijyi^0>cj , то xj^0=0; 3)если yi^0>0, то aijxj^0=bi; 4)если aijxj^0<bi,то yi^0=0. j=, i= Если по оптимальному плану расход i-того ресурса < его запасов, то оценка этого ресурса=0. Если же оценка>0, то расход этого ресурса равен его запасу. Таким образом, дефицитный (полностью используемый по оптимальному плану) ресурс имеет положительную оценку в двойственной задаче, а недефицитный – нулевую оценку. С точки зрения пр-ва: если оценка ресурсов, расходуемых по j-ой технологии больше цены продукта, то j-ая технология не применяется (xj=0). Если же по некот. плану j-ая технология применяется (xj>0), то оценка ресурсов, расходуемых по данной технологии, равна цене продукта. Эта т-ма вместе с еще 2-мя теоремами и образует так называемую т-ию двойственности ЛП.	45.Третья основная теорема двойственности (об оценках влияния ресурсов на выпуск продукции) и ее экономическое содержание (без доказательства). Перераспределение ресурсов между предприятиями фирмы с помощью двойственных оценок ресурсов. Значения переменных yi^0 в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов (правых частей bi) системы ограничений исходной задачи на величину максимума целевой функции: zmax/bi =yi^0 , при этом увеличение правой части i-го ограничения приводит к увелич. или уменьш. zmax в зависимости от того будет ли yi^0 положит. или отрицательным. Экон.смысл: двойственная оценка ресурса – это приращение прибыли, приходящейся на единицу приращения этого ресурса. Здесь речь идет лишь о достаточно малых приращениях ресурсов, так как изменение величины в некоторый момент вызовет изменение оценок . Оценки позволяют выявить направление мероприятий по расшивке узких мест производства (ресурсы с положительной двойственной оценкой), обеспечивающих получение наибольшего экономического эффекта. Эта т-ма вместе с еще 2-мя теоремами и образует так называемую т-ию двойственности ЛП. Из 2-ой и 3-ей теорем следует, что часть ресурсов, у которых двойственные оценки будут отличны от 0, необходимо будет пополнять для продолжения выпуска продукции. Недостающие ресурсы должны быть пополнены, причем в оптимальном количестве. 46.В чем состоит условие устойчивости двойственных оценок? Область устойчивости двойственных оценок B=>B+T, область устойчивости-множество значений (t1,t2) на двумерной плоскости. -A2T≤Hопт T =t1 t2 Hопт=A2B Hопт=A2(B+T)=0 A2B+A2T≥0 -A2T≤ Hопт	89. Верхняя и нижняя цена игры в матричной игре в чистых стратегиях, их нахождение. Стратегия называется чистой, если выбор игрока неизменен от партии к партии. У первого игрока, очевидно, есть m чистых стратегий, у второго – n. При анализе игр противник считается сильным, т.е. разумным. Рассмотрим описанную конфликтную ситуацию с точки зрения первого игрока. Если мы( первый игрок) выбираем свою i-ю стратегию (i-ю строку матрицы А), то второй игрок, будучи разумным, выберет такую стратегию j, которая обеспечит ему наибольший выигрыш ( а нам наименьший), т.е. он выберет такой столбец j матрицы А, в котором платеж aij( второго игрока первому) минимален. Переберем все наши стратегии i= 1,2,,..,m и выберм ту из них, при которой второй игрок, действуя максимально разумно, заплатит нам наибольшую сумму. Величина α = maxi=1,2,…n minj=1,2,…m aij называется нижней ценой игры, а соответствующая ей стратегия первого игрока- максиминной. Аналогичный рассуждения( но уже с точки зрения второго игрока) определяют верхнюю цену игры β = minj=1,2,…n maxi=1,2,…m aij и соответствующую ей минимаксную стратегию второго игрока. По своему определению нижняя цена игры α представляет собой максимальный гарантированный выигрыш первого игрока( т.е. применяя свою максиминную стратегию, первый игрок обеспечивает себе выигрыш, не меньший α), а верхняя цена- величину, противоположную минимальному гарантированному проигрышу второго игрок( т.е. применяя свою минимаксную стратегию, второй игрок гарантивует, что он не проиграет больше, чем β ,или, иначе, выиграет не меньше , чем (-β)). 90. Оптимальные стратегии в матричной игре в чистых стратегиях, условие их существования, седловая точка матрицы. Если α= β, то говорят, что игра имеет седловую точку в чистых стратегиях. Общее значение α и β называется ценой игры и обозначается v= α= β . При этом стратегии игроков, соответствующие седлововой точке, называются оптимальными чистыми стратегиями, так как эти стратегии являются наиболее выгодными сразу для обоих игроков, обеспечивая первому игроку гарантированный выигрыш не менее v, а второму игроку- гарантированный проигрыш не более (-v), и отклоняться игрокам от этих стратегий невыгодно.
47.Условие сохранения структуры производственной программы и двойственных оценок ресурсов при изменении объемов ресурсов. Задача о «расшивке узких мест производства», ее математическая модель и решение. Двойственная оценка ресурса — это приращение прибыли, приходящееся на единицу приращения этого ресурса. Оценки позволяют выявить направление мероприятий по расшивке узких мест производства (ресурсы с положительной двойственной оценкой), обеспечивающих получение наибольшего экономического эффекта. В задаче планирования производства находится оптимальный план пр-ва и узкие места пр-ва, т.е. те ресурсы кот. используются полностью, а потому называются дефицитными. Расшивка «узких мест» пр-ва подразумевает заказ дополнительно дефицитных ресурсов. Пусть T(t1,t2,…,tm) - вектор дополнительных объемов ресурсов, (В+Т) – вектор новых объемов ресурсов. Прирост прибыли, приходящийся на ti единиц i-го ресурса, будет равен уiti, где уi- двойственная оценка этого ресурса. Cледует иметь ввиду, что найденными двойственными оценками ресурсов мы можем пользоваться только при таких изменениях объемов ресурсов и, соответственно, компонент оптимального плана, когда сохраняется структура плана производства и остаются постоянными двойственные оценки ресурсов. Условие устойчивости двойственных оценок, как видно из соотношения Q^-1B=H, характеризуется неравенством: H+Q^-1T≥0 Составить план расшивки узких мест пр-ва означает указать сколько единиц каждого из дефицитных ресурсов нужно дополнительно заказать, чтобы суммарный прирост прибыли был максимальным. Т.о. проблема расшивки «узких мест» представляет собой задачу линейного программирования: найти план расшивки T(t1, t2,…, tm), максимизирующий суммарный прирост прибыли: w = y^*T, при условиях H+Q^-1T>=0 и T>=0.	48) Постановка и математическая модель транспортной задачи, число базисных неизвестных. Записать основные свойства этой модели. Сначала рассмотрим случай,когда суммарные запасы продукции поставщиков = суммарным запросам потребителей: ∑ai=∑bj Транспортная задача,в которой выполняется это условие,называется сбалансированной,закрытой или замкнутой.В этом случае удовлетворение запросов всех потребителей возможно,если от каждого поставщика вывозится вся продукция , а каждому потребителю продукция доставляется в количестве, соответствующем его запросам.Очевидно,что математической моделью закрытой транспортной задачи будет следующая задача ЛП: m n L=∑ ∑ cijxij->min i=1 j=1 ∑xij=ai, i=1,…1m, j=1 ∑xij=bj, j=1,…,n, i=1 xij≥0, i=1,…,m; j=1,…,n. Отметим 2 важных свойства задачи (1.2)-(1.5): 1)задача всегда имеет решение 2)ранг матрицы коэффициентов системы уравнений (1.6),(1.4) равен m+n-1.	49.Постановка и математическая модель транспортной задачи,в которой суммарные запасы продукции меньше суммарныхъ запросов на нее.Записать правила сведения такой модели к замкнутой задаче и записать полученную замкнутую модель транспортной задачи. Правило:Если суммарная мощность меньше суммарного спроса,то вводится фиктивный поставщик,его мощность=тому чего не хватает.В таблице вводится доп. строка,затраты считаются 0. 50. Постановка и математическая модель транспортной задачи,в которой суммарные запасы продукции больше суммарныхъ запросов на нее.Записать правила сведения такой модели к замкнутой задаче и записать полученную замкнутую модель транспортной задачи. Правило:Если суммарная мощность меньше суммарного спроса,то вводится фиктивный потребитель,его мощность=тому чего не хватает.В таблице вводится доп. строка,затраты считаются 0.
51.Методы построения первого базисного решения транспортной задачи. Транспортная задача формулируется следующим образом. Продукт, сосредоточенный в m пунктах производства в кол-ве a1, a2,...,am единиц, необходимо распределить между n пунктами потребления, которым необходимо b1,b2,..,bn единиц. Стоимость перевозки единицы продукта из i-го пункта пр-ва в j-ый пункт потр-ия равна cij. Необходимо составить план перевозок, при кот. запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах пр-ва и общие транспортные расходы по доставке были бы минимальны. Первое базисное допустимое решение легко построить по правилу северо-западного угла. В соответствии с этим правилом, заполнение транспортной таблицы начинается с левой верхней клетки и состоит из однотипных шагов, на каждом из которых из рассмотрения исключается один поставщик или один потребитель: если остаток продукта у i-го поставщика после предыдущих шагов меньше, чем неудовлетв. запрос j-го потребителя, то исключается из рассмотрения i-й поставщик, и в клетку (i, j) заносится поставка xij, равная остатку продукта у i-го поставщика после предыдущих шагов; если остаток продукта у i-го поставщика после предыдущих шагов больше, чем неудовлетворенный запрос j-го потребителя, то исключается из рассмотрения j-й потребитель, и в клетку (i, j) заносится поставка xij, равная неудовлетворенному запросу j-го потребителя; если остаток продукта у i-го поставщика после предыдущих шагов равен неудовлетворенному запросу j-го потребителя, то исключается из рассмотрения или i-й поставщик, или j-й потребитель, и в клетку (i, j) заносится поставка xij=0 равная остатку продукта у i-го поставщика после предыдущих шагов. После этого рассматривается левая верхняя клетка среди тех, которые остаются после вычеркивания строк, соответствующих поставщикам, весь запас продукта у которых уже распределен по потребителям, и столбцов, соответствующих потребителям, запросы которых уже удовлетворены. Каждому поставщику ставится в соответствие потенциал pi, а каждому потребителю — потенциал qi. При этом каждой клетке соответствует некоторая оценка: . Один из потенциалов можно выбрать произвольно, так как в системе одно уравнение линейно зависит от остальных. Обычно полагают p1=0. Остальные потенциалы вычисляются из условия, что для базисных клеток ∆ij=0. Затем вычисляются оценки всех свободных клеток. Если хотя бы одна из оценок строго положительна, то базисное допустимое решение, содержащееся в данной транспортной таблице, не является оптимальным. Выбирается свободная клетка (r, s), соответствующая наибольшей положительной оценке . Для выбранной свободной клетки строится цикл пересчета — замкнутая ломаная, одна из вершин которой находится в данной свободной клетке, а все остальные — в занятых клетках, соседние звенья взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы. Так производится перераспределение поставок вдоль цикла пересчета, при котором происходит такой переход к новому базисному допустимому решению.	53.Записать математическую модель замкнутой транспортной задачи, составить двойственную к ней задачу и записать условия второй основной теоремы двойственности для получения пары взаимодвойственных задач ЛП. Сначала рассмотрим случай,когда суммарные запасы продукции поставщиков = суммарным запросам потребителей: ∑ai=∑bj Транспортная задача,в которой выполняется это условие,называется сбалансированной,закрытой или замкнутой.В этом случае удовлетворение запросов всех потребителей возможно,если от каждого поставщика вывозится вся продукция , а каждому потребителю продукция доставляется в количестве, соответствующем его запросам.Очевидно,что математической моделью закрытой транспортной задачи будет следующая задача ЛП: m n L=∑ ∑ cijxij->min i=1 j=1 ∑xij=ai, i=1,…1m, j=1 ∑xij=bj, j=1,…,n, i=1 xij≥0, i=1,…,m; j=1,…,n. Отметим 2 важных свойства задачи (1.2)-(1.5): 1)задача всегда имеет решение 2)ранг матрицы коэффициентов системы уравнений (1.6),(1.4) равен m+n-1. Задача,двойственная к транспортной задаче. Пусть дана закрытая транспортная задача,математическая модель которой имеет вид (1.2)-(1.5).Составим двойственную задачу.Обозначим переменные двойственной задачи,соответствующие уравнениям (1.3) через Pi (i=1,...,m),а переменные, соответствующие уравнениям (1.4)-через Qj(j+1,…,n). Тогда задача,двойственная к задаче (1.2)-(1.5), примет вид m m ∑aipi+∑bjqi->max i=1 j=1 pi+qj≤cij, i=1,…,m; j=1,..,n. Задача (1.6),(1.7)содержит(mn) неравенств (1.7) относительно (m+n) неизвестных Pi и Qj ,которые могут принимать значения любого знака. Из второй основной теоремы двойственности получаем,что допустимое решение Хij (i=1,…,m; j=1,…,n) задачи (1.2)-(1.5) и допустим решение Pi(i=1,…,m) и Qj (j=1,…,n) задачи (1.6)-(1.7) будут оптимальными решениями соответствующих задач тогда и только тогда,когда они будут удовлетворять следующим условиям: n pi(∑xij-ai)=0,i=1,…,m j=1 m qj(∑xij-bj)=0,j=1,…,n i=1 xij(pi+qj-cij)=0, i=1,..,m; j=1,..,n Отметим что для нашей нессиметричной пары взаимодвойственных задач условия (1.8) и (1.9) выполняются для любых допустимых решений задачи (1.2-1.5),поэтому условия (1.8-1.9) не накладывают никаких ограничений на Pi и Qj.Также на консультации разбирали(смотрите тетрадь)