Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Система векторов a1, a2,…am называется линейно зависимой, если хотя бы один из векторов этой системы может быть представлен в виде линейной комбинации остальных.
Теорема. Для того, чтобы система векторов была линейно зависимой, необходимо и достаточно, чтобы существовал такой набор чисел мю, из которых хотя бы 1 отлично от нуля, тако что μ1a1 + μ2a2+ …+ μmam=0
Система векторов a1, a2,…am называется линейно независимой, если ни один из векторов этой системы нельзя представить в виде линейной комбинации остальных.
Теорема. Для того, чтобы система векторов была линейно независимой, необходимо и достаточно, чтобы что μ1a1 + μ2a2+ …+ μmam=0 выполнялось только при нулевых значениях всех чисел мю.
Система единичных векторов ортогонального n-мерного векторного пространства линейно
независима, потому что нельзя выразить один вектор через другие.
В каком случае вектор b можно назвать линейной комбинацией векторов a1,..., ап?
В-р является линейной комбинацией в-ров , если его можно представить как сумму произведений данных в-ров на какие-либо числа - коэффициенты линейной комбинации.
Ввести необходимые векторы и матрицы и записать в векторно-матричной форме следующую задачу (дана задача ЛП, записанная в обычном виде).
Под линейным программированием (ЛП) понимается раздел теории экстремальных задач, в котором изучаются задачи нахождения максимума или минимума линейных функций на множествах, задаваемых системами линейных равенств и неравенств в n-мерном векторном пространстве.
Постановка задачи: Дана система m линейных уравнений с n неизвестными
(1)
Где все неизвестные могут принимать только неотрицательные значения x1 0, x2,0,…, xn0, (2) и линейная однородная функция тех же переменных: L = c1x1 + c2x2 + … + cnxn.(3)
Требуется среди всех решений системы уравнений (1) найти такое неотрицательное решение. Которое бы линейная форма (3) принимала наименьшее значение.
Обозначим через A матрицу системы линейных уравнений, X и B – матрицы-столбцы (векторы) переменных и свободных членов. Также введём в рассмотрение n-мерный вектор С, компонентами которого служат коэффициенты линейной формы (3) и n-мерный нуль-вектор 0=(0, 0,…0)
Тогда задачу л/п можно представить в следующем виде:
Линейная форма: L=CX
Система линейных уравнений: AX=B
Условие (2): X≥0
Квадратная матрица В называется обратной для квадратной матрицы А того же порядка, если их произведение А В = В А = Е, где Е - единичная матрица того же порядка, что и матрицы А и В.
Теорема. Для того, чтобы матрица А имела обратную, необходимо и достаточно, чтобы ее определитель был отличен от нуля.
Матрица, обратная матрице А, обозначается через А-1, так что В = А-1.
1) Если в процессе решения появляется уравнение вида 0*х1+0*х2+…+0*хn=bi , где bi¹0 , то это означает, что система несовместна, т.е. не имеет решения
2) Если в процессе решения левая и правая части i ур-я обращаются в 0, т.е.0=0 Þ данное ур-е явл линейной комбинацией ур-й входящих в эту систему, в этом случае это ур-е исключается из всей системы
Решение () системы называют неотрицательным, если все его компоненты αj неотрицательны.
Если правые части всех уравнений полученных систем окажутся неотрицательными, то соответствующие базисные решения также будут неотрицательными. Следовательно, чтобы получить неотрицательные базисные решения СЛАУ, надо научиться вести процесс исключения неизвестных так, чтобы свободные члены всех уравнений на всех этапах этого процесса оставались неотрицательными. Для этого следует руководствоваться следующими правилами: 1)Если в СЛАУ имеются отрицательные свободные члены, то все такие уравнения необходимо умножить на (-1); 2) В качестве разрешающей неизвестной можно принять любую неизвестную, при которой есть хоть один положительный коэффициент, а затем в качестве разрешающего уравнения следует взять то уравнение, которое соответствует наименьшему среди отношений свободных членов уравнений к соответствующим положительным коэффициентам при выбранной неизвестной в этих уравнениях.
Может случиться, что указанное минимальное отношение достигается при нескольких значениях индекса. Тогда любое из соответствующих им уравнений можно принять за разрешающее. Принято говорить в этом случае, что рассматриваемая СЛАУ является вырожденной.
СЛАУ не будет иметь ни одного неотрицательного решения, если в процессе симплексных преобразований в ней появится уравнение, в котором свободный член строго положителен, а среди коэффициентов при неизвестных нет ни одного положительного.
Преобразования системы в соответствии с этими правилами называются симплекс-преобразованиями системы.
Разрешающая неизвестная- неизвестная в СЛАУ с коэффициентом отличным от нуля ,которую собираемся исключить из всех уравнений системы, кроме r-го уравнения(разрешающего).
Разрешающее уравнение – уравнение, содержащее разрешающую неизвестную, а остальные уравнения этой системы ее не содержат.
Переменные, коэффициенты при которых образуют минор, отличный от нуля (базисный минор), называются базисными переменными (x1, x2, …, xr), переменные присутствующие только в одном уравнении системы с коэффициентом 1. Остальные переменные xr+1, …, xn называются свободными.
Общее решение- выражения базисных неизвестных через свободные вида
X1=h1-g1,m+1 - …- g1nxn ,
Xm = gm,m+1xm+1 - … - gmnxn
Среди частных решений системы выделяются базисное , отвечающее нулевым значениям свободных неизвестных : X1 = h1, x2 = h2, …, xm = hm, xm+1 = 0, …,Xn = 0
8. Матрица A = = 1,2,3. Разложите определитель по элементам второго столбца.
9. Дайте определения ранга матрицы размером т*n. Определите ранг матрицы (матрица задана)
Полезно иметь ввиду, что ранг матрицы не изменяется от элементарных преобразований. Под элементарными преобразованиями понимаются:
1) замена строк столбцами, а столбцов соответствующими строками;
2) перестановка строк матрицы;
3) вычеркивание строки, все элементы которой равны нулю;
4) умножение какой-либо строки на число, отличное от нуля;
5) прибавление к элементам одной строки соответствующих элементов другой строки.
Пример на определение ранга матрицы:
Нахождение ранга матрицы с помощью вычисления всех ее миноров требует слишком большой вычислительной работы. Поэтому для нахождения ранга применяется другой алгоритм. Для его описания потребуется ряд дополнительных сведений.
Элементарные преобразования матриц:
1) перестановка строк или столбцов;
2) умножение строки или столбца на число отличное от нуля;
3) добавление к одной из строк другой строки, умноженной на число или добавление к одному из столбцов другого столбца, умноженного на число.
Алгоритм нахождения ранга матрицы.
10. Дайте определения:1)совместной и несовместной СЛАУ, 2) определенной и неопределенной СЛАУ.
СЛАУ называется совместной, если она имеет хотя бы 1 решение и несовместной если не имеет ни одного решения.
СЛАУ называется определенной, если имеет единственное решение и неопределенной, если больше 1 решения.
11. Действия над матрицами: сумма, произведение, транспонирование. Свойства и формулы для расчета элементов.
Матрицей размера mxn наз таблица чисел, кот расположена в m-строках и n-столбцах
a11 а12 …а1n
А= a21 а22 …а2n или кратко А=(aij)
…………..
am1 аm2 …аmn
Транспонированной матрицей наз матрица, в которой, не изменяя порядка, строки заменены столбцами. Для транспонированных матриц справедливы следующие соотношения: 1)(А')' = A; 2)(АВ)' = В'А' ; 3) (А + В)' = А' + В'.
Суммой двух матриц одного размера называется матрица того же размера, каждый элемент которой равен сумме соответствующих элементов матриц-слагаемых. Так, если А - || аij || и В=|| bij||— матрицы размера т х п, то их суммой является матрица С = А + В, такая, что cij=aij+bij.
Произведением матрицы А размера т х п на число А, называется матрица D того же размера, у которой dij=aijλ.
Произведением матрицы А размера т х п на матрицу В размера n х k наз матрица С размера т х k, эл-ты кот сij равны скалярному произведению i-й строки матрицы А на j-й столбец матрицы В, т.е
Произведение матриц обозначается С = АВ. Скалярное произведение векторов а и b можно представить как произведение вектора-строки (матрицы-строки) а на вектор-столбец (матрицу-столбец) b': (a, b) = ab' . Для операции произведения матриц справедливы следующие свойства:
1)A(BС) = (АВ)С; 2)(А+В)С=АС+ВС;
3)A(B+С)=AB+AC; 4) λАВ) = (λА)В.4) λАВ) = (λА)В.
12.Единичная матрица: определение, формулы для элементов
Единичная матрица- квадратная диагональная матрица, элементы стоящие на главной диагонали равны единицы, а остальные эл-ты равны нулю.
Матрица – это прямоугольная таблица чисел, содержащая m строк и n столбцов.
a11 а12 …а1n
А= a21 а22 …а2n или кратко А=(aij)
…………..
am1 аm2 …аmn
Если т=п, то матрица называется квадратной матрицей n-го по рядка. Кв. матрица наз треугольной, если все ее элемен ты, стоящие над или под главной диагональю, равны нулю. Кв. матрица называется диагональной, если все ее эл-ты, стоящие на главной диагонали, отличны от нуля, а остальные равны нулю. Диагональная матрица наз единичной, если у нее по главной диагонали стоят 1. Единичную матрицу принято обозначать буквой Е:
13. Обратная матрица: определение, условия существования обратной матрицы
Квадратная матрица В называется обратной для квадратной матрицы А того же порядка, если их произведение А В = В А = Е, где Е - единичная матрица того же порядка, что и матрицы А и В.
Теорема. Для того, чтобы матрица А имела обратную, необходимо и достаточно, чтобы ее определитель был отличен от нуля т.е. квадратная матрица обратима тогда и только тогда, когда она является невырожденной
14. Постановка линейной производственной задачи, смысл переменных, векторов и матриц,допустимый и оптимальный план, математическая модель
Есть предприятие которое может выпускать видов продукции, используя видов ресурсов. Пусть – расход -го ресурса на единицу -й продукции, – имеющееся количество -го ресурса, – прибыль от реализации единицы -й продукции (удельная прибыль), – искомое количество единиц -й продукции. Задача состоит в том, чтобы найти производственную программу максимизирующую прибыль при ограничениях по ресурсам для каждого где по смыслу задачи все
Матрица А - удельные затраты ресурсов, вектор В объемов ресурсов и век тор С удельная прибыль; ; .
Мат. Модель.
а11x1 + a12x2 + … a1nxn ≤ b1
а21x1 + a22x2 + … a2nxn ≤ b2
. . . . .
аm1x1 + am2x2 + … amnxn ≤ bm.
x1≥0, x2≥0, ...xn≥0.
Если в матем-й модели какой-либо задачи планирования будут содержаться линейные неравенства, то их можно заменить линейными уравнениями с помощью дополнительных неотрицательных неизвестных.
Любое неотрицательное значение системы называют допустимым, а допустимое решение, при котором целевая ф-я принимает наибольшее (наименьшее) значение – оптимальным решением задачи ЛП.
Задачу линейного программирования нередко формулируют как задачу минимизации или максимизации линейной формы L=c1x1+c2x2+...cnxn (1) при ограничениях x1≥0, x2≥0, ...xn≥0 и
∑ aijxj≤bi, i=1,2,...m1,
∑ aijxj=bi, i= m1+1, m1+2,...m2,
∑ aijxj≥bi, i= m2+1, m2+2,...m.
Такую запись называют общей задачей линейного программирования.
Обозначим через А матрицу системы линейных уравнений:
а11x1 + a12x2 + … a1nxn = b1
а21x1 + a22x2 + … a2nxn = b2 (2)
А = . . . . .
аm1x1 + am2x2 + … amnxn = bm.
Через X и B – матрицы-столбцы (векторы) неизвестных и свободных членов:
, ,
а также введем в рассмотрение n-мерный вектор C = (с1 … сn), компонентами которого служат коэффициенты линейной формы (1), и n-мерный нуль-вектор 0(0, 0, …, 0). Тогда линейную форму можно рассматривать как скалярное произведение L=CX (3), систему линейных уравнений (2) заменить одним матричным уравнением AX=B (4), а условия x1≥0, x2≥0, ...xn≥0 записать в виде X≥0 (5). Поэтому часто основную задачу линейного программирования кратко записывают как задачу минимизации(максимизации) линейной формы (3) при линейных ограничениях (4) и (5).
Множество допустимых решений – это пересечение всех прямых, соответствующих линейным ограничениям типа рав-ва и всех полуплоскостей, соответствующих ограничениям типа нерав-ва.
Для линейной функции градиент – это в-р, состоящий из коэффициентов этой ф-ии. Он показывает направление увеличения ф-ии. Через выбранное решение проводим линию уровня целевой ф-ии. Для линейной ф-ии линия уровня – это прямая, перпендикулярная градиенту.
Геом.интерпретация: область допустимых решений – многогранник в пространстве или многоугольник на плоскости, линии постоянных значений целевой функции. Процесс решения состоит в совмещении линии до конца пересечения с областью допустимых значений при наибольшем значении целевой функции в этой точке пересечения- оптимальное решение ( крайнее положение). Метод-перебор угловых точек.
Динамическое программирование представляет собой математический аппарат, разработанный для решения некоторого класса задач математического программирования путем их разложения на относительно небольшие и, следовательно, менее сложные задачи. Специфика метода динамического программирования состоит в том, что для отыскания оптимального управления планируемая операция разделяется на ряд последовательных шагов или этапов. Соответственно и сам процесс планирования операции становится многошаговым и развивается последовательно, от этапа к этапу, причем каждый раз оптимизируется управление только на одном шаге. Динамическое программирование — это планирование дальновидное, с учетом перспективы
Некоторые операции естественно распадаются на этапы, в других это деление приходится вводить искусственно. Примером «естественно многоэтапной» операции может служить планирование работы предприятия на некоторый период времени, состоящий из нескольких хозяйственных лет или кварталов.
Динамическое программирование — это вычислительный метод для решения задач управления определенной структуры, когда задача с переменными представляется как многошаговый процесс принятия решений и на каждом шаге определяется экстремум функции только от одной переменной. n
Знакомство с методом динамического программирования
Процесс динамического программирования разворачивается от конца к началу. Сначала делаются различные предположения о том, чем кончился предпоследний шаг, и для каждого из них выбирается управление на последнем. Затем делаются различные предположения о том, чем кончился предпредпоследний шаг, т. е. рассматриваются различные состояния системы на третьем от конца шаге и выбирается управление на втором от концы шаге так, чтобы оно вместе в уже выбранным управлением на последнем шаге обеспечивало наилучший эффект на двух последних шагах, и так далее, вплоть до первого от начала шага, с которого начинался процесс.
Принцип искать всегда оптимальное продолжение процесса относительно того состояния, которое достигнуто в данный момент, принято называть принципом оптимальности.
Состояние на каждом шаге характ-ся некоторой переменной величиной, кот. называется параметром состояния. Наилучший эффект на данном этапе вместе с уже рассмотренными шагами хар-ся функцией состояния. Решение конкретной задачи методом динамич. программирования сводится к выбору параметра состояния, составлению ф-ии состояния и рекурентных соотношений, связывающих ф-ии состояния для двух соседних последовательных этапов, и их применению для выбора оптимального управления.
В экономике и управлении часто встречаются ситуации, в которых сталкиваются две или более стороны, преследующие различные цели, причем результат, полученный каждой из сторон при реализации определенной стратегии зависит от действий других сторон. Такие ситуации называются конфликтными. Например: аукцион, спортивные состязания, парламентские выборы (при наличии нескольких кандидатов), карточная игра.
Рассмотрим конфликт двух участников с противоположными интересами. Математической моделью такого конфликта является игра с нулевой суммой. Участники игры называются игроками. Стратегией игрока называется осознанный выбор одного из множества возможных вариантов его действий.
Рассмотрим конечные игры, в которых множества стратегий игроков конечны; стратегии первого игрока пронумеруем от 1 до m, а стратегии второго игрока — от 1 до n.
Если первый игрок выбрал свою i-ю стратегию, а второй игрок — свою j-ю стратегию, то результатом такого совместного выбора будет платеж второго игрока первому. Таким образом, игра с нулевой суммой однозначно определяется матрицей, которая называется платежной. Строки этой матрицы соответствуют стратегиям первого игрока, а столбцы — стратегиям второго игрока.
Игра происходит партиями. Партия игры состоит в том, что игроки одновременно называют свой выбор: первый игрок называет некторый номер строки матрицы, а второй — некоторый номер столбца этой матрицы. После этого происходит «расплата». Пусть, например, первый игрок назвал номер i, а второй — j. Тогда второй игрок платит первому сумму. На этом партия игры заканчивается. Если aij>0, то это означает, что при выборе первым игроком i-й стратегии, а вторым — j-й стратегии выигрывает первый игрок.
Цель каждого игрока — выиграть как можно большую сумму в результате большого числа партий. Стратегия называется чистой, если выбор игрока неизменен от партии к партии.
При любой стратегии первого игрока, второй игрок будет выбирать стратегию обеспечивающий ему наибольший выигрыш, поэтому с точки зрения первого игрока надо выбирать такую стратегию, при которой второй игрок, действуя разумно заплатит наибольшую сумму. Такая стратегия первого игрока называется максиминной, а величина =max min aij называется нижней ценой игры.
Аналогично (с точки зрения второго игрока) определяется верхняя цена игры =min max aij и соответствующая ей минимаксная стратегия второго игрока. То есть, принимая свою минимаксную стратегию второй игрок проиграет не больше .
В общем случае имеет место неравенство α≤β, если же α=β, то говорят, что игра имеет седловую точку, общее значение и β называется при этом ценой игры.
При этом стратегии игроков, соответствующие седловой точке, называются оптимальными чистыми стратегиями, так как эти стратегии являются наиболее выгодными сразу для обоих игроков.
Смешанной стратегией первого игрока называется вектор , где все , а . При этом — вероятность, с которой первый игрок выбирает свою i-ю стратегию. Аналогично определяются смешанные стратегии второго игрока. Чистая стратегия также подпадает под определение смешанной — если все вероятности равны нулю, кроме одной, равной единице.
Пусть игроки – Первый и Второй, играют в матричную игру с матрицей . Пусть стратегия Первого есть , а Второго – . Тогда выигрыш Первого есть случайная величина (с.в.) с рядом распределения:
Если игроки применяют свои смешанные стратегии P (p1, p2,…pm )и Q (q1, q2,…qn) соответственно, Выигрыш первого: выигрыш aij
Вероятность pi qj.
То есть первый игрок с вероятностью pi gj. выигрывает aij.. Математическое ожидание выигрыша первого игрока равно М(P,Q)= pi qj aij есть средний выигрыш.
И это равно математическому ожиданию проигрыша второго игрока.
Пусть есть дисперсия этой случайной величины. Естественно назвать среднее квадратическое отклонение с.в. , т.е. риском для первого при игре со стратегиями . Поскольку выигрыш первого есть проигрыш для второго, то есть случайный проигрыш второго и вполне естественно можно назвать риском игры с такими стратегиями и для второго.
Предположим сначала, что игроки озабочены только максимизацией среднего дохода за партию игры – обычная цель в таких играх. Тогда игроки будут играть со своими оптимальными стратегиями: – Первый игрок и – второй, стратегии оптимальны, если М(P,Q*)М(P*,Q*)М(P*,Q)
Пара (P*,Q*) – решение игры. Математическое ожидание с. в. называется ценой игры, обозначим ее
Граф-это совокупность двух множеств: множества Х, элементы которого называют вершинами, и множества У упорядоченных пар вершин, элементы которого называют дугами или ребрами. Если отрезки, соединяющие вершины графа, имеют направления, то граф называется ориентированным, а сами отрезки — дугами. Если же отрезки не имеют направления, то граф называется неориентированным, и в этом случае говорят, что вершины графа соединены ребрами.
Применение в экономике: задача выбора кратчайшего пути от пункта производства до пункта конечного потребления, задача выбора схемы подключения домов к системе кабельного телевидения, при которой общая длина всех участков минимальна, задача определения максимального объема информации, который можно передать от определенного отправителя к конкретному получателю, с учетом пропускных способностей каналов и узлов системы передачи данных.
Теория двойственности является центральной частью всего ЛП. Она имеет богатое экономическое содержание.
В рамках модели ЛП предприятия должна существовать внутренняя система оценки ресурсов, используемых им в процессе производства. Эти оценки связаны с технологическими особенностями данного производственного процесса, характеризуемыми матрицей условий A, со структурой и количеством ресурсов, отпущенных для производственного потребления, описываемых вектором B, а также со структурой внешних цен, на основе которых получается вектор прибылей C. Эти оценки называют расчетными оценками ресурсов. Расчетную оценку единицы ресурса не следует отождествлять с той ценой, по которой предприятию был отпущен этот ресурс. Последняя отражает общественно необходимые затраты на производство единицы ресурса, а расчетная цена показывает только сравнительную ценность этого ресурса на данном предприятии в данных конкретных условиях.
В зависимости от вида исходной задачи линейного программирования различают симметричные и несимметричные пары двойственных задач.
Если система ограничений исходной задачи состоит из неравенств и на все переменные хj наложено условие неотрицательности, то исходная задача и составленная по определенному правилу двойственная задача образуют симметричную пару двойственных задач.
Пусть исходная задача имеет вид: найти наибольшее значение функции
Правило составления двойственных задач
1. Каждому ограничению исходной задачи ставится в соответствие двойственная переменная yi, где .
2. Составляется целевая функция , коэффициентами которой будут свободные члены системы ограничений исходной задачи, а цель задачи меняется на противоположную:
(1)
3. Составляется система ограничений двойственной задачи, при этом матрица из коэффициентов системы ограничений исходной задачи транспонируется, знак неравенства меняется на противоположный, свободными членами будут являться коэффициенты из целевой функции исходной задачи:
(2)
4. Переменные yi в двойственной задаче также неотрицательны, т.е.
. (3)
Если двойственную задачу принять за исходную и по данному правилу составить двойственную задачу, то получим исходную задачу. Понятие двойственности является взаимным.
В несимметричном случае двойственная задача составляется по тем же правилам, что и в случае симметричной пары, но если двойственная переменная поставлена в соответствие ограничению уравнения, то эта переменная свободна по знаку.
Базисное решение является оптимальным тогда и только тогда, когда в уравнении среди коэффициентов Δ j при неизвестных нет ни одного отрицательного, т.е оценки Δ j ≥ 0. Так как двойственные оценки – это взятые с противоположным знаком коэффициенты выражения ц.ф. через свободные неизвестные. Значит, сами эти коэффициенты ≤ 0. Поэтому, как только любая из свободных неизвестных примет положительное значение – целевая функция уменьшается. А это и означает, что она максимальна при нулевых значениях свободных неизвестных, т.е. для данного базисного решения.
Допустим необходимо максимизировать целевую функцию 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).
Для решения такой задачи применяется симплексный метод линейного программирования.
Одним из допустимых решений задачи ЛП будет базисное неотрицательное решение системы (2): x1=h1, x2=h2,...xm=hm, xm+1=0,...xn=0 (4), ему соответствует значение целевой ф-ии равное:
L0=c1оh1+c2h2+...cmhm+cm+1*0+...+cn*0 = ci hi (5).
Надо исследовать, является ли базисное неотрицательное решение (4) оптимальным,т.е. является ли значение (5) наименьшим из всех возможных значений целевой ф-ии (1), отвечающих различным неотрицательным решениям системы (2).
Учитывая, что система уравнений (2) имеет предпочитаемый вид, находим для нее общее решение: xi=hi-gi,m+1xm+1-...-ginxn, i=1,2,...,m (6). Если свободным неизвестным придавать какие-нибудь неотрицательные значения, то будем получать различные решения системы (2), среди которых нас интересуют только неотрицательные. Подставляя их компоненты в линейную форму (1), можно подсчитать соответствующие значения целевой функции. Очевидно, чтобы легче было следить за поведением целевой функции, целесообразно выразить ее только через свободные неизвестные.
Если переписать выражение (1) в виде:
- L+c1x1+c2x2+...cmxm+ cm+1xm+1+...+cnxn=0 (7). Для того чтобы исключить базисные неизвестные из этого уравнения, достаточно умножить первое уравнение системы (2) на c1, второе на c2 и т.д., сложить полученные произведения и из результата вычесть уравнение (7). Получим L+∆m+1xm+1+...+∆nxn=L0 (8), где ∆j = c1g1j + c2g2j + ... + cmgmj - cj , j=1,2,...n (9) или ∆j = zj - cj, zj=cigij, j=1,2,...n (9a).
Из выражения следует, что базисное решение x1=h1, x2=h2,...xm=hm, xm+1=0,...xn=0 (2) является оптимальным решением задачи ЛП
Базисное решение является оптимальным решением задачи ЛП тогда и только тогда, когда в уравнении среди коэффициентов при неизвестных нет ни одного отрицательного, т. е. условие оптимальности имеет вид ∆j≥0 , j=1,2,…,n.
Если же хотя бы один из коэффициентов при свободных неизвестных равен нулю, то будут и небазисные оптимальные решения. Очевидно, оптимальных решений будет еще больше, если среди коэффициентов при свободных неизвестных в уравнении (8) окажется несколько нулевых.
22. Сформулировать и доказать критерий оптимальности решения задачи линейного программирования при отыскании минимума линейной функции симплексным методом.
Для того, чтобы базисное решение в задаче лп было оптимальным решением этой задачи необходимо и достаточно, чтобы в оценочном уравнении Z0-Z=Σ∆jxj выполнялось условие ∆j≤0 , j=1,2,…,n
Действительно, если в общем решении мы станем придавать различные неотрицательные значения свободным неизвестным так, чтобы соответствующие базисные неизвестные также принимали неотрицательные значения, то одновременно с частными неотрицательными решениями системы ограничений мы будет получать согласно выражению L=L0-∆m+1xm+1-...-∆nxn соответствующие им значения целевой функции. В частности, при нулевых значениях свободных неизвестных получится базисное решение x1=h1, x2=h2,...xm=hm, xm+1=0,...xn=0 и соответствующее ему значение линейной формы L0=Σcihi. Если хотя бы один из коэффициентов при неизвестных в последнем уравнении вспомогательной системы ,
например, Δm+1 положителен, то мы можем соответствующей свободной неизвестной xm+1 дать в общем решении какое-нибудь положительное значение, сохранив , и получить частное неотрицательное решение с меньшим значением линейной формы.
При выполнении условий оптимальности базисное решение будет единственным оптимальным решением задачи линейного программирования тогда и только тогда, когда все коэффициенты при свободных неизвестных в последнем уравнении вспомогательной системы строго отрицательны. Если же хотя бы один из коэффициентов при свободных неизвестных равен нулю, то будут и небазисные оптимальные решения. Действительно, если, например, , то как бы мы не изменяли в общем решении свободную неизвестную Xm+1 в ее неотрицательной области изменения при Xm+2 =…=Xn = 0 , целевая функция будет сохранять одно и то же значение, т. е. мы получим некоторую совокупность оптимальных решений задачи. Очевидно, оптимальных решений будет еще больше, если среди коэффициентов при свободных неизвестных в уравнении окажется несколько нулевых.
При выполнении условий оптимальности базисное решение будет единственным оптимальным решением задачи линейного программирования тогда и только тогда, когда все коэффициенты при свободных неизвестных в последнем уравнении вспомогательной системы строго отрицательны. Если же хотя бы один из коэффициентов при свободных неизвестных равен нулю, то будут и небазисные оптимальные решения. Действительно, если, например,
то как бы мы не изменяли в общем решении свободную неизвестную Xm+1 в ее неотрицательной области изменения при Xm+2=….=Xn=0, целевая функция будет сохранять одно и то же значение
т. е. мы получим некоторую совокупность оптимальных решений задачи. Очевидно, оптимальных решений будет еще больше, если среди коэффициентов при свободных неизвестных в уравнении окажется несколько нулевых.
Если есть хотя бы одна свободная неизвестная, такая, что коэффициент при ней в последнем уравнении системы положителен, а в первых уравнениях той же системы
среди коэффициентов при ней нет ни одного положительного, то задача линейного программирования неразрешима в силу неограниченности целевой функции на множестве неотрицательных решений системы ограничений. Действительно, если, например Δn>0, в уравнении L=L0-∆m+1xm+1-...-∆nxn, но g1n<=0 g2n<=0 в предпочитаемой форме
системы ограничений, то в общем решении системы ограничений мы можем переменную xm+1=…=xn-1 неограниченно увеличивать, положив xn, и тогда, как видно из выражения L=L0-∆m+1xm+1-...-∆nxn, целевая функция будет неограниченно убывать и, следовательно, оптимального решения не существует.
В каждом последовательном плане новое значение линейной функции приближается к оптимальному, пока не будет получено оптимальное решение или не будет доказана неограниченность линейной формы на множестве решений системы ограничений
Но это утверждение справедливо только при условии невырожденности рассматриваемой задачи, т. е. если ни на одном этапе процесса решения ни один из свободных членов системы уравнений (H i) не обращается в нуль.
При новое значение линейной формы строго меньше предыдущего и через конечное число шагов мы придем к оптимальному решению или докажем неразрешимость задачи, так как число шагов не может быть больше числа базисных решений , среди которых неотрицательных значительно меньше. В вырожденном случае на одном или нескольких этапах свободный член разрешающего уравнения может оказаться равным нулю, и значение линейной формы не изменится.
В частном случае общей задачи ЛП система уравнений имеет предпочитаемый вид, при этом правые части всех уравнений неотрицательны.
Допустим необходимо минимизировать целевую функцию 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. Сформулировать теорему о связи решений исходной и вспомогательной задач при решении задачи линейного программирования методом искусственного базиса.
S=Xn+1+…..+Xn+m к мин Вспомогательная задача всегда имеет оптимальное решение, т.к. решая симплексным методом через конечное число шагов найдем оптимальное решение т.к. 1) система совместна 2)S>=0. Если оптимальное решение дает Smin=0, тогда исходная задача либо имеет оптимальное решение, либо уходит в минус-бесконечность
симплексным методом в качестве начального базиса выбирают базис из дополнительных переменных, для которых сi, = 0, то оценки для всех небазисных (свободных) переменных
будут равны , а соответствующее значение целевой функции
При дополнительных переменных коэффициенты целевой функции равны 0
При базисном решении все свободные переменные равны нулю,
30. Для задачи линейного программирования:
получить выражение целевой функции z через свободные переменные общего решения системы ограничений
C3 П3 Н0 Х1 Х2 Х3 Х4 Х5 Х6 Х7
3 Х2 1
0 Х6 1
5 Х3 1
-z+1400 Двойственные оценки
Коэффициент выражения ц.ф-и через свободные переменные – это двойственные оценки (с точностью до знака)
Правило: столбец С3 * столбец матрицы, а затем вычетается верхнее значение наверху.
Док-во: правила вычисления двойственных оценок. Без ограничений общности, базисными стали Х1, Х2, Х3.
C3 П3 Н0 Х1 Х2 Х3 Х4 Х5 Х6 Х7
Х1 1 S
Х2 1
Х3 1
Двойственные оценки
F = CX= C1X1+ C2X2= C1*X1 + C2*X2= C1(H-SX2) + C2( H2) = C1H + (-C1S + C2)X2= Z0+(-C1S + C2)X2=Z0-(C1S- C2)X2=Z
Z= Z0-(C1S- C2)X2
40=X1+ 7X4+2X1
H=X1+SX2→X1=H-SX2
1)Ключевой столбец выбираем по минимальной двойственной оценке
2)Потом считается столбец альфа как отношение свободного члена к коэффициенту ключевого столбца
3)По минимальной альфа выбираем ключевую строку
В качестве разрешающей неизвестной можно принять любую неизвестную, при которой есть хоть один положительный коэффициент, а затем в качества разрешающего уравнения следует взять то уравнение, которое соответствует наименьшему среди отношений свободных членов уравнений к соответствующим положительным коэффициентам при выбранной неизвестной в этих уравнениях. Условимся говорить, что СЛАУ подвергается симплексным преобразованиям, если процесс исключения неизвестных осуществляется в соответствии с указанными правилами выбора разрешающей неизвестной и разрешающего уравнения. Остается заметить, что СЛАУ не будет иметь ни одного неотрицательного решения, если в процессе симплексных преобразований в ней появится уравнение, в котором свободный член строго положителен, а среди коэффициентов при неизвестных нет ни одного положительного.
32.Введение балансовых переменных в систему ограничений задачи ЛП: цель и правило введения
Если в математической модели конкретной задачи условия, которыми связаны переменные целевой функции, представляют собой систему линейных алгебраических неравенств, то ее можно заменить некоторой системой линейных
алгебраических уравнений с бóльшим числом неизвестных и привести задачу к каноническому виду основной задачи линейного программирования. Эти неизвестные называют балансовыми или дополнительными. Правило введения: если неравенство со знаком «≤» , то добавляем в левую часть +Хm+I,если «≥», то -Хm+i
33.Введение искусственных переменных в систему ограничений задачи ЛП при решении задачи ЛП методом искусственного базиса: цель и правило введения
Метод искусственного базиса применяется к решению задач линейного программирования в общем случае, когда система ограничений не имеет предпочитаемого вида.
Пусть требуется минимизировать (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, то возможна дальнейшая минимизация
34. В каком случае процесс решения задачи ЛП симплекс-методом является конечным?
В любом. Но при этом оптимальное решение будет достигнуто не всегда.
35. В каких задачах применяется симплекс-метод?
В задачах линейного программирования. Для задач, связанных с принятием решений в экономике, когда требуется достичь некоторой цели при ограниченных ресурсах. Если функция цели линейно зависит от переменных (размеров видов деятельности или производственных процессов) и расходы ресурсов также линейно зависят от переменных, то такая задача принятия решений сводится к задаче линейного программирования (ЛП)
36. Что представляет собой симплексная таблица?
Симплекс-таблица составляется из коэффициентов при x1, x2, x3, x4 и чисел, стоящих в правых частях уравнений-ограничений задачи: в первой строке записываются элементы уравнения (А), во второй - (В). В последней строке симплекс-таблицы записываются коэффициенты и правая часть целевой функции (С). Таким образом, симплекс-таблица содержит две строки коэффициентов (по числу ограничений задачи) и строку коэффициентов целевой функции. Число столбцов в симплекс-таблице равно числу переменных задачи плюс один столбец правых частей (b).
37. Запишите симметричную пару двойственных задач линейного программирования.
Z=c1x1+c2x2+…+cnxn → max F=b1y1+b2y2+….+bmym→min
A11x1+a12x2+…+a1nxn<=b1 a11y1+a21y2+…+am1ym>=c1
A21x1+…+a2nxn<=b2 ……………………………….
…………………… a1ny1+a2ny2+…+amnym>=cn
Am1x1+…+amnxn<=bm
Yi>=0
Xj>=0
Симметричность заключается в том, что в обеих задачах переменные неотрицательны и система ограничений является неравенствами.
38. Сформулируйте правила составления задачи, двойственной к данной задаче линейного программирования с ограничениями — неравенствами.
В общем случае принято называть двойственной задачей для произвольной задачи ЛП с ограничениями-неравенствами такую задачу ЛП, которая получается из данной задачи следующим образом: каждому ограничению-неравенству исходной задачи ставится в соответствие переменная двойственной задачи, принимающая неотрицательные значения; матрица коэффициентов при неизвестных транспонируется; правые части ограничений заменяются коэффициентами целевой функции; меняются направления неравенств, коэффициенты целевой функции заменяются правыми частями ограничений; от максимизации (минимизации) функции цели переходят к минимизации (максимизации). Говорят, что задачи ЛП обра-зуют симметричную пару.
39. Матричная запись пары двойственных задач ЛП (симметричная пара задач с ограничениями-неравенствами и несимметричная пара, где в одной из задач ограничения имеют вид равенств)
Прямая задача: матричная запись:
z = c1x1 + c2x2 + … + cnxn. →max cx→max
Ax≤b
xj≥0 (j=1,n)
(1)
xj ³0, j=1,n
Двойственная задача: (симметричная пара – ограничения явл-ся неравенствами и переменные неотрцательные)
F = b1y1 + b2y2 + … + bmym. →min матричная запись:
yb →min
yA≥c
yi≥0, (i=1,m)
yi ³0, i=1,m
Прямая задача: Матричная запись:
z = c1x1 + c2x2 + … + cnxn. →max cx→max
Ax=b
xj≥0 (j=1,n)
(1)
xj ³0, j=1,n
Двойственная задача (несимметричная): матричная запись:
F = b1y1 + b2y2 + … + bmym. →min yb →min
yA≥c
yi – любое число (i=1,m)
(1)
Пусть дана пара взаимодвойственных задач, тогда для любого решения Х=(х1, x2, … xn) исходной задачи и У=(у1….ум) двойственной задачи справедливо неравенство:
Доказательство:
40.Основное неравенство теории двойственности ЛП. Для любых допустимых решений и прямой и двойственной задач ЛП справедливо неравенство: . Для любого допустимого плана исходной задачи и для любого допустимого в-ра оценок ресурсов общая стоимость всего произведенного продукта не превышает суммарной стоимости ресурсов.
МАЛАЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ. Для существования оптимального решения любой из задач двойственной пары необходимо и достаточно существование допустимого решения для каждой из них.
Поскольку для любого допустимого решения х прямой задачи согласно т неравенству , а по усл. , то для любого допустимого х , т.е. - оптимальное решение прямой задачи. Точно так же, но , откуда , поэтому - оптимальное решение
42. Сформулировать и доказать теорему о достаточном условии оптимальности решений пары двойственных задач линейного программирования.
Теорема о достаточном условии оптимальности решений пары двойственных задач: Если и - допустимые решения пары двойственных задач, для которых выполняется равенство , то и - оптимальные решения соответствующих задач.
Согласно этой теореме, план производства продукции и вектор оценок ресурсов является оптимальным, если цена всей произведенной продукции и суммарная оценка ресурсов совпадают.
43.Сформулировать и доказать первую основную теорему двойственности. В чем состоит экономическое содержание первой основной теоремы двойственности?
Если одна из двойственных задач имеет оптимальное решение, то двойственная ей задача также имеет оптимальное решение, причем экстремумы целевых функций равны, т.е. .
Если одна из двойственных задач не имеет оптимального решения, то другая задача также не имеет оптимального решения, причем если одна из задач не имеет оптимального решения из-за неограниченности целевой функции, то другая из-за несовместности системы ограничений.
Д-во: Пусть существует оптимальное решение х* прямой задачи, тогда оптимальное базисное решение расширенной задачи лп существует и имеет вид:
Где B* - оптимальная базисная матрица.
Оптимальное значение функции цели расширенной задачи равно
. Но поскольку коэффициенты функции цели при дополнительных переменных расширенной задачи равны нулю, то это значение является одновременно и оптимальным значением целевой функции первоначальной задачи :
Докажем теперь, что существует оптимальное решение двойственной задачи P*/ Для этого докажем что решение двойственной задачи допустимо, а затем то, что оно оптимально. В самом деле, поскольку решение оптимальное базисное решение расширенной задачи, то для него все симплекс-разности неположительны . Но поскольку то . В первоначальной нумерации матрица неА и цены неС расширенной задачи имеют следующую структуру: неА=(А,Em) неС=(с,0). В соответствии с данной структурой неравенства разделяются на 2 части:
И , поэтому Ро допустимое решение двойственной задачи. Кроме того, в соответствии с , поэтому согласно теореме о достаточном условии оптимельности решений пары двойственных задач лп Po является оптимельным решением. Пусть теперь целевая функция прямой задачи не ограничена. Предположим, что двойственная задача имеет допустимое решение Р тогда по основному неравенству теории двойственности значения функции цели для всех допустимых решений прямой задачи были бы ограничены сверху величиной рb, но это противоречит тому. Что ф-я цели не ограничена, поэтому двойственная задача не имеет решения.
Экономическое содержание первой основной теоремы двойственности ЛП таково. В терминах оценок она может быть сформулирована следующим образом: если задача определения оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения минимальных оценок ресурсов, причем цена продукта, полученного реализацией оптимального плана, совпадает с суммарной оценкой имеющихся ресурсов.
44.Сформулировать и доказать вторую основную теорему двойственности. В чем состоит экономическое содержание второй основной теоремы двойственности?
Для того чтобы допустимые решения исходной и двойственной задач являлись оптимальными решениями соответствующих задач двойственной пары необходимо и достаточно выполнение следующих условий:
Т.е. если какое-либо нер-во системы ограничений одной из задач не обращается в точное равенство оптимальным решением этой задачи, то соответствующая компонента оптимального решения двойственной задачи должна быть равна 0. Если же какая-либо компонента оптимального решения положительна, то соотв-ее ей ограничение в двойственной задаче должно быть обращено в точное равенство.
Другими словами: 1)если хj0>0,то aijyi0=cj; 2)если aijyi0>cj , то xj0=0; 3)если yi0>0, то aijxj0=bi; 4)если aijxj0<bi,то yi0=0. j=, i=
Если по оптимальному плану расход i-того ресурса < его запасов, то оценка этого ресурса=0. Если же оценка>0, то расход этого ресурса равен его запасу. Таким образом, дефицитный (полностью используемый по оптимальному плану) ресурс имеет положительную оценку в двойственной задаче, а недефицитный – нулевую оценку.
С точки зрения пр-ва: если оценка ресурсов, расходуемых по j-ой технологии больше цены продукта, то j-ая технология не применяется (xj=0). Если же по некот. плану j-ая технология применяется (xj>0), то оценка ресурсов, расходуемых по данной технологии, равна цене продукта.
Док-во:
Оптимальные решения Х* и Y* как допустимые решения удовлетворяют следующим неравенствам: . Умножим первое из них на Y*, а второе на X*, тогда . Поскольку Y*B=CX*, то левые части неравенства равны и каждая равна нулю:
. В развёрнутой форме ; , что и требовалось доказать
Пусть дана пара двойственных несимметричных задач:
(i=1,m) , (j=1,n)
Предположим, что мы решили исходную задачу:
Zmax=Z0(X0)
Тогда предположим, что – оптимальное решение 2ой задачи.
Теорема: значения переменных Yi0 в оптимальном решении двойств. Задачи представляют собой оценки правых частей bi системы ограничений исходной задачи на величину максимума целевой функции:
Доказательство:
Экон.смысл: двойственная оценка ресурса – это приращение прибыли, приходящейся на единицу приращения этого ресурса. Здесь речь идет лишь о достаточно малых приращениях ресурсов, так как изменение величины в некоторый момент вызовет изменение оценок . Оценки позволяют выявить направление мероприятий по расшивке узких мест производства (ресурсы с положительной двойственной оценкой), обеспечивающих получение наибольшего экономического эффекта.
Из 2-ой и 3-ей теорем следует, что часть ресурсов, у которых двойственные оценки будут отличны от 0, необходимо будет пополнять для продолжения выпуска продукции. Недостающие ресурсы должны быть пополнены, причем в оптимальном количестве.
46.В чем состоит условие устойчивости двойственных оценок?
Область устойчивости решения у0 называется множество значений ресурсов, для кот. выполняется неравенство B`=B+T Н+
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.Постановка и математическая модель замкнутой транспортной задачи, число базисных неизвестных. Записать основные свойства этой модели.
Транс.задача формулируется следующим образом. Продукт, сосредоточенный в m пунктах производства в кол-ве a1, a2,...,am единиц, необходимо распределить между n пунктами потребления, которым необходимо b1,b2,..,bn единиц. Стоимость перевозки единицы продукта из i-го пункта пр-ва в j-ый пункт потр-ия равна cij. Необходимо составить план перевозок, при кот. запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах пр-ва и общие транспортные расходы по доставке были бы минимальны.
Обозначим xij кол-во груза, планируемого к перевозке от i-го поставщика j-му потребителю.При балансе произ-ва и потр-я =математическая модель тр. задачи выглядит так: найти план перевозок Х=(хij), i=1,2,..,m; j=1,2,..,n, минимизирующий общую стоимость всех перевозок L= ,при условии что из любого пункта вывозится весь продукт: , i=1,2,..,m. И любому потребителю доставляется необходимое количество груза: j=1,2,..,n,.. и по смыслу задачи x11>0,..,xmn>0.
Если оно не выполнено, то задача не закрыта. Чтобы ее закрыть, нужно ввести фиктивного потребителя.
Преобразование открытой модели в закрытую. Если общий объем производства превышает объем, требуемый всем потребителям, то модель задачи открытая. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления, равным разнице между объемом пр-ва и потр-я.
49.Постановка и математическая модель транспортной задачи, в которой суммарные запасы продукции меньше суммарных запросов на нее. Записать правила сведения такой модель к замкнутой задаче и записать полученную замкнутую модель транспортной задачи.
Если , то транспортная задача является незамкнутой. Пусть , т.е. суммарные запасы продукции меньше суммарных потребностей в ней и математическая модель открытой ТЗ имеет вид: найти наименьшее значение функции L= min при ограничениях: ,
, j=1,…,n,
= , i=1,…,m
, i=1,…,m; j=1,…,n.
Если безразлично, какой из потребителей недополучит продукцию, то ТЗ сводится к закрытой замкнутой модели путём введения дополнительного фиктивного (m+1)-ого поставщика с запасом продукции, равным = - . При этом значения тарифов полагаем равными нулю, что обеспечивает равенство целевых функций исходных и соответствующих им вспомогательных задач. В итоге получаем замкнутую модель ТЗ. Математическая модель ТЗ: найти план перевозок X=(), i=1,2,…,m; j=1,2,…,n, минимизирующий общую стоимость всех перевозок L= min при условии, что из любого пункта производства вывозится весь продукт: = , i=1,2,…,m и любому потребителю доставляется необходимое количество груза: , j=1,2,…,n, причём по смыслу задачи Решаем её, находим оптимальный план. При этом значения в решении вспомогательной задачи будут обозначать величину неудовлетворённого спроса j-ого потребителя.
50.Постановка и математическая модель транспортной задачи, в которой суммарные запасы продукции больше суммарных запросов на нее. Записать правила сведения такой задачи к замкнутой и записать полученную замкнутую модель транспортной задачи.
Пусть , т е суммарные запасы продукции больше суммарных потребностей в ней. Если безразлично, у кого из поставщиков останутся излишки продукции, то решение такой несбалансированной задачи сводится к решению замкнутой транспортной задачи путем введения дополнительного фиктивного (n-1)го потребителя, запросы которого составляют
Значение сi, n+1 полагаем равным нулю и решаем вспомогательную задачу с n+1 потребителем и m поставщиками. При этом продукция xi,n+1 , планируемая для перевозки к фиктивному потребителю, остается на i-м складе.
51.Записать правила построения первого базисного решения замкнутой транспортной задачи по методу северо-западного угла.
Первое базисное допустимое решение легко построить по правилу северо-западного угла. В соответствии с этим правилом, заполнение транспортной таблицы начинается с левой верхней клетки и состоит из однотипных шагов, на каждом из которых из рассмотрения исключается один поставщик или один потребитель:
Построение начинается с верхней левой коетки, в которую мы ставим максимально возможную поставку:
а1<b1 значит x11= min изменённый запрос: bi ʹ=b1-x11
а1>b1 значит x11= b1 изменённый запас: ai ʹ=a1-x11
а1=b1 значит x11= b1= a1 изменённый запас: bi ʹ=b1-x11=0
Запомнив х11, мы из дальнейшего рассмотрения первого базисного решения исключаем только одного участника. Во всех случаях после заполнения одной клетки мы исключаем одного участника и переходим к задаче с количеством участников m+n-1 (m-число поставщиков, n - потребителей )
Каждому поставщику ставится в соответствие потенциал pi, а каждому потребителю — потенциал qi. При этом каждой клетке соответствует некоторая оценка: .
Один из потенциалов можно выбрать произвольно, так как в системе одно уравнение линейно зависит от остальных. Обычно полагают p1=0. Остальные потенциалы вычисляются из условия, что для базисных клеток ∆ij=0.
Затем вычисляются оценки всех свободных клеток. Если хотя бы одна из оценок строго положительна, то базисное допустимое решение, содержащееся в данной транспортной таблице, не является оптимальным. Выбирается свободная клетка (r, s), соответствующая наибольшей положительной оценке .
Для выбранной свободной клетки строится цикл пересчета — замкнутая ломаная, одна из вершин которой находится в данной свободной клетке, а все остальные — в занятых клетках, соседние звенья взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы.
Так производится перераспределение поставок вдоль цикла пересчета, при котором происходит такой переход к новому базисному допустимому решению.
52.Записать правила построения первого базисного решения замкнутой транспортной задачи по методу минимального элемента в матрице тарифов.
При построении первого базисного решения по этому методу первой заполняется клетка с минимальным значением (тариф) и в нее заносится максимально возможное значение (кол-во груза к перевозке от i-го поставщика j-ому потр-лю). Далее по тем же правилам, что и в методе “северо-западного угла”, исключается один из участников (всегда только 1), находится минимальный из оставшихся элементов и в соответствующую клетку записывается максимально возможное для этой клетки значение . Процесс продолжается до получения базисного решения. При этом заполненными окажутся (m+n-1) клеток.
Замечание. Базисность допустимых решений, получаемых с помощью указанного выше метода,обеспечивается автоматически в случае выполнения следующих рекомендаций:
1)при заполнении очередной клетки необходимо присваивать соответствующей переменной максимально возможное значение;
2)после заполнения очередной клетки исключается из дальнейшего рассмотрения один и только один участник.
53.Записать математическую модель замкнутой транспортной задачи, составить двойственную к ней задачу и записать условия второй основной теоремы двойственности для получения пары взаимодвойственных задач линейного программирования.
Транспортная задача,в которой суммарные запасы продукции поставщиков = суммарным запросам потребителей, называется сбалансированной, закрытой или замкнутой.В этом случае удовлетворение запросов всех потребителей возможно, если от каждого поставщика вывозится вся продукция , а каждому потребителю продукция доставляется в количестве, соответствующем его запросам. Очевидно,что математической моделью закрытой транспортной задачи будет следующая задача ЛП:
( 1.3);(1,4)
Отметим 2 важных свойства задачи ():
1)задача всегда имеет решение
2)ранг матрицы коэффициентов системы уравнений равен m+n-1.
Задача,двойственная к транспортной задаче.
Пусть дана закрытая транспортная задача,математическая модель которой имеет вид (1.2)-(1.5).Составим двойственную задачу.Обозначим переменные двойственной задачи,соответствующие уравнениям (1.3) через Pi (i=1,...,m),а переменные, соответствующие уравнениям (1.4)-через Qj(j+1,…,n). Тогда задача,двойственная к задаче (1.2)-(1.5), примет вид
(1,6);(1,7)
Задача (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
54.Правила расчета потенциалов поставщиков и потребителей в транспортной задаче. Расчет оценочных коэффициентов для свободных клеток транспортной задачи. Условие оптимальности базисного решения.
Ui+Vj=Cij
Задается начальный потенциал,потом по кружкам вычисляют.
Условие: Базисное решение в транспортной задаче- определ вариант распределенных базисных поставок,число кружков=m+n-1.Кружки должны образовывать вычеркиваемую комбинацию.
Условие-хар-ки свободных клеток должны быть положительными.
55.Записать определение цикла пересчета в транспортной таблице. Использование цикла пересчета для получения нового (улучшенного) базисного решения.
Циклом пересчета, соответствующим данной свободной клетке транспортной задачи, называется замкнутая ломаная линия, одна вершина которой лежит в этой свободной клетке, а остальные вершины - в занятых базисных клетках транспортной таблицы. Полученная ломаная должна удовлетворять следующим условиям:
а) ее звенья параллельны строкам или столбцам таблицы;
б) в каждой вершине ломаной под прямым углом сходятся два ее звена.
Доказано, что для любой свободной клетки транспортной таблицы существует единственный цикл пересчета, который может быть представлен и самопересекающейся ломаной, но точки ее самопересечения по определению цикла пересчета не являются его вершинами.
Теорема. Если в транспортной таблице построено базисное реш-е, то для каждой свободной клетки этой табл сущ единственный цикл пересчёта.
Построим цикл пересчета для выделенной нами свободной клетки ( ).
Запишем в клетку с номером ( ) знак “+”, в соседнюю клетку с номером ( ) - знак “-“.Так, двигаясь вдоль цикла пересчета, будем в вершинах цикла поочередно ставить знаки “+” или знаки “-”.Очевидно, что число вершин цикла пересчета всегда четно. Поэтому не имеет значения, в какую из двух соседних клеток был осуществлен переход из клетки с номером ( ). Изменим теперь поставки в вершинах цикла пересчета в соответствии со знаками, находящимися в этих вершинах, на величину w. Тогда поставки примут значение
+w, 1-w, -w, …, -w, -w.
В вершинах цикла пересчёта, помеченных знаком «-» находим min поставку из старого базисного плана . Присвоим величине w значение, равное , и по вершинам цикла пересчёта согласно последовательности перераспред-ем поставки. При этом поставка - w окажется равной 0. Соответствующую неизвестную переводим в разряд свободных, а клетка с номером ( ) остается пустой. Если после пересчёта в нес-ких вершинах цикла поставки примут нулевые значения, то в разряд свободных переводим только 1-ну из соответствующих неизвестных, сохраняя остальные в базисном наборе с нулевыми знач-ями перевозок. В итоге будет получено новое базисное решение, в кот будет занято (m+n-1) клеток и кот исследуется на оптимальность тем же методом. Процесс продолж до получения оптимальн реш-ия.
56.Записать алгоритм решения транспортной задачи (перечислить по порядку этапы решения). Обосновать конечность метода потенциалов решения транспортной задачи.
Строится какое-нибудь базисное решение
Для построенного базисного решения рассчитываются потенциалы
Рассчитанные потенциалы для расчета оценочных коэффициентов ∆ij . Если все ∆ij ≤0, то задача решена и построенное базисное решение оптимально.
Если среди ∆ij >0, то выбирается положительный коэффициент, обычно, но не обязательно, max по величине и с помощью циклов пересчета строиться новое базисное решение, для которого повторяются пункты 2-3.
Конечность метода потенциалов – метод потенциалов всегда приводит к оптимальному плану
57.Объяснить смысл перевозок от фиктивного поставщика или к фиктивному потребителю в оптимальном решении транспортной задачи.
Для сведения открытой задачи к закрытой вводятся фиктивные пункты производства или потребления. Если суммарные запасы продукта у поставщиков строго больше, чем суммарные запросы потребителей, вводится фиктивный потребитель, у которого объем потребления равен разнице между объемом производства и объемом потребления; если же суммарные запасы продукта у поставщиков строго больше, чем суммарные запросы потребителей, то вводится фиктивный поставщик.
Обозначим через хij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю. При наличии баланса производства и потребления математическая модель транспортной задачи будет выглядеть так: найти план перевозок
Х = (хij), ;
минимизирующий общую стоимость всех перевозок при условии, что из любого
пункта производства вывозится весь продукт: и любому потребителю доставляется необходимое количество груза , причем по смыслу задачи х11 > 0 ,. . . ., xmn > 0.
поставки от фиктивного поставщика укажут объем неудовлетворенного спроса соответствующих потребителей, а поставки к фиктивному потребителю – остатки продукта у поставщиков.
58.Что такое целочисленное линейное программирование? Допустимое множество задачи ЦЛП.
К задачам ЦЛП относят задачи с линейной целевой функцией и линейными ограничениями, в которых на все переменные наложены условия целочисленности. Допустимое множество задачи ЦЛП или конечно, или состоит из множества изолированных точек.
59.Что такое параметрическое линейное программирование? Где может находиться параметр?
Параметрическое программирование представляет собой один из разделов математического программирования, изучающий задачи, в которых целевая функция или ограничения зависят от одного или нескольких параметров. Необходимость рассмотрения подобных задач обусловлена различными причинами. Одной из основных является та, что исходные данные для численного решения любой реальной задачи оптимизации в большинстве случаев определяются приближенно или могут изменяться под влиянием каких-то факторов, что может существенно сказаться на оптимальности выбираемой программы (плана) действий. Соответственно, разумно указывать не конкретные данные, а диапазон возможного изменения данных, что-бы в результате решения иметь наилучшие планы для любого варианта исходных данных. С математической точки зрения параметрическое программирование выступает как одно из средств анализа чувствительности решения к вариации исходных данных, оценки устойчивости решения. Заметим, что существуют различные подходы к подобному анализу (например, на основе постановки двойственной задачи). Здесь мы, не ссылаясь на двойственные оценки, рассмотрим самые простейшие варианты решения для самых простейших параметрических программ. 1) Коэффициенты целевой функции линейно зависят от некоторого единственного параметра λ (времени, температуры и т. п.). 2)В случае зависимости от параметра компонент вектора правых частей ограничений, т. е. решения задачи поиска экстремума функции
60.Что такое многокритериальная задача?
Задача с несколькими целевыми функциями. Она не имеет решения.
61.Что такое рекорд в методе ветвей и границ?
Рекорд - граничное значение целевой функции; наилучшее из найденных решений.
62.Приведите пример задачи целочисленного линейного программирования
Решить задачу ЦЛП:
f(x1,x2)= 2x1+3x2 → max,
5x1+7x2 ≤ 35,
4x1+9x2 ≤ 36,
x1, x2 ≥ 0,
x1,x2 - целые
Задачу решить можно методом прямого перебора. Организуем 2 цикла: 1-й по x1 от 0 до 9, 2-й, встроенный в первый, - по x2 от 0 до 5. Оператор тела цикла проверяет, удовлетворяет ли точка (x1, x2) обоим неравенствам, вычисляется значение функции f(x1, x2) и сравнивается с запомненным наилучшим решением
Параметрическое программирование представляет собой один из разделов математического программирования, изучающий задачи, в которых целевая функция или ограничения зависят от одного или нескольких параметров.
Рассмотрим задачу параметрического линейного программирования, в которой только коэффициенты целевой функции линейно зависят от некоторого единственного параметра λ (времени, температуры и т. п.):
Отыскать максимум (или минимум) функции:
при условиях:
64.Приведите пример многокритериальной задачи
Математически такая задача содержит область допустим реш-ий, кот может иметь любую природу, и нес-ко целевых ф-ций, значение которых должно максимизироваться или минимизироваться в данной области. Максимизация или минимизация целевых ф-ций сводится друг к другу умножением на -1, поэтому, не нарушая общности, можно считать, что данная задача имеет вид: (x)max (i=1,2,…,n),
xD, (1)
x - ?,
где D – область допустим реш-ий. При этом в задаче x может быть векторным параметром. Если кол-во целевых функций (x) в задаче (1) больше одной, то данная задача явл зад-ей многокритериальной оптимизации. В экономических задачах допустим обл обычно задаётся системой ур-ний и неравенств, к которой могут быть добавлены некотор дополнит ограничения, например, ограничения на целочисленность переменных.
Пример. Парикмахерская может производит 2 вида продукции: муж и жен причёски, причём мастера, работающие в парик-ой явл-ся универсалами. Жен прич отнимает 2 ч работы мастера и приносит 10 у.е. прибыли. Муж прич отним 1 ч раб-ы и приносит 4 у.е. прибыли. Общий рес-с работы мастеров сост 40ч. Соц заказ, установленный для парик-ой при её открытии, состоит в максимальном кол-ве обслуженных клиентов. Если через x1 и x2 обознач кол-во муж и жен причёсок, сделанных в прарик-ой за рассматрив промежутов времени, то матем модель задачи имеет след вид: z1= 4x1+10x2 → max
z2= x1 + x2 →max
x1+2x2 ≤ 40
x1, x2 Z
x1, x2 ≥0
x1, x2 - ?
В дан задаче оптимальность производстен плана парик-ой опред-ся по 2 критериям: критерию максим прибыли и критерию максим кол-ва обслуженных клиентов. Этим критериям соответствуют целевые ф-ции z1 и z2 .
В задаче многокритериальной оптимизации (1), как правило, нет решений, поскольку цели, выражен различн критериями, часто явл-ся противоположными. Поэтому оптимальные значения целевых ф-ций достигаются при разных допустим реш-ях, кот нужно сравнивать, чтобы выбрать 1 допустимый вариант.
65.Сформулируйте условие окончания ветвления при решении задач методом ВИГ.
Основная идея метода «ветвей и границ» состоит в разбиении множества допустимых решений на подмножества, которые, в свою очередь, разбиваются на подмножества и т.д. При этом среди возникающих подмножеств могут быть такие, которые не содержат допустимых решений или заведомо не содержат оптимальных решений. Если это удается определить на некотором этапе с помощью тех или иных оценок, то такие подмножества исключаются из дальнейшего рассмотрения. В результате решение находится частичным перебором.
Критерии окончания ветвления:
В задаче на максимум в начале решения граничное значение целевой функции, или рекорд, полается равным - ∞ .
1. Получена задача, не имеющая решения. Это становится все более вероятным с увеличением глубины ветвления, когда все большее число ограничений вида xi ≤ [{xi0] , или xi ≥ [{xi0] +1 добавляется к уже существующим ограничениям( так, что все более вероятным становится несовместимость системы ограничений получаемых задач).
2. Если находится новое целочисленное решение, то оно сравнивается с рекордом; если прежний рекорд превзойден, то запоминается новый рекорд, в противном случае остается старый.
3. Получаемое оптимальное нецелочисленное решение задачи на какой-то стадии ветвления сравнивается с рекордом; если это значение меньше, чем рекорд, то ветвление задачи прекращается, так как нет возможности побить рекорд.
Непобитый рекорд дает оптимальное решение исходной задачи ЦЛП.
66.Что такое решение, оптимальное по Парето в многокритериальной задаче.
Множество допустимых решений, для которых невозможно одновременно улучшить все частные показатели эффективности, принято называть областью Парето или областью компромиссов, а принадлежащие ей решения – эффективными или оптимальными по Парето.
67.Объясните, почему метод ВИГ принадлежит к методам отсечения?
При решении методом отсекающих плоскостей задачи при снятии условия целочисленности на переменные превращаются в обычные задачи ЛП. Основной этап решения задач при помощи этого метода состоит в последовательном решении получающихся друг из друга ряда задач ЛП. Каждая последующая задача формируется из предыдущей путём введения дополнительного к имеющимся ограничениям нового ограничения, называемым правильным отсечением. Правильным оно наз-ся потому, что отсекает от допустимой области предыдущей задачи её оптимальное решение, не отсекая в то же время ни одного допустимого реш-ия исходной задачи. Данный процесс прекращается, когда в очередной задаче либо получено оптимальное решение, принадлежащее области допустимых решений исходной задачи, либо установлена пустота области её допустимых решений.
Метод ВИГ позволяет отбрасывать достаточно большие подмножества допустимого множества D, состоящее из заведомо неоптимальных точек. Эта идея и положена в основу алгоритма метода ВИГ.
Из вышесказанного можно сделать вывод, что метод ВИГ принадлежит к методам отсечения.
Вообще, отсечение- отбрасывание части допустимой области. Применяется это тогда, когда нужно найти целочисленное решение.
Метод ВИГ принадлежит к методам отсечения потому, что при решении задачи этим методом, допустимая область делится на части и при решении задачи для каждой отдельной части, мы оставшиеся части временно не учитываем ( т.е. отсекаем).
68. Почему нельзя решать задачу целочисленного ЛП, решив ее сначала как обычную задачу ЛП без учета целочисленности, а затем округлив полученное решение?
1) Потому что не известно в какую сторону округлять( в большую или в меньшую)
2) Можно выйти за пределы допустимой области
3) Оптимальное целочисленное решение может быть не в соседней точке, а через одну, две, десять и т.д.
В случаях, когда имеется несколько целей, которые не могут быть отражены одним критерием (например, стоимость, надежность и т. п.) требуется найти точку области допустимых решений, которая минимизирует или максимизирует все эти критерии. Обозначим i-й частный критерий через, а область допустимых решений через Q. Учтем, что изменением знака функции всегда можно свести задачу минимизации к задаче максимизации, и наоборот, мы можем сформулировать кратко задачу векторной оптимизации следующим образом:
В идеальном случае в задаче (9.2.7)—(9.2.8) можно вести поиск такого решения, которое принадлежит пересечению множеств оптимальных решений всех однокритериальных задач. Но указанное пересечение обычно оказывается пустым множеством, и потому приходится рассматривать переговорное множество или множество Парето». Вектор называется эффективным решением, если не существует такого, что:
причем хотя бы для одного имеет место строгое неравенство. Множество допустимых решений, для которых невозможно одновременно улучшить все частные показа-тели эффективности, принято называть областью Парето или областью компромиссов, а принадлежащие ей решения — эффективными или оптимальными по Парето.
Операция Ei называется оптимальной по Парето, если не существует операций, которые бы ее доминировали. Отметим, что операции, оптимальные по Парето, не обязательно являются «самыми лучшими» (и даже просто «хорошими») — эти операции не являются худшими. Выбор операций среди оптимальных по Парето осуществляется на основе склонности лица, принимающего соответствующее решение, к риску.
Данный метод позволяет отбрасывать достаточно большие подмножества допустимого множества D, состоящие из заведомо неоптимальных точек. Рассмотрим задачу ЦЛП:
Р= схmax, (1)
Axb, (2)
x0, (3)
- целые. (4)
На первом этапе решаем «родительскую» задачу ЛП – задачу (1)-(3), но без учёта целочисленности (4), или требования целочисленности. Если её реш-ие целое, то оно и явл-ся реш-ем задачи (1) – (3). В противном случае выбираем любую нецелочислен компоненту, например . Далее разбиваем исходную задачу на 2 с помощью след дополнит ограничений: [], (5)
[]+1, (6)
где [] – целая часть числа .
Задачи (1) – (3), (5) и (1) – (3), (6) наз-ся «дочерними» задачами. Существен св-во процесса ветвления сост в том, что объединение допустимых множеств «дочерних» задач строго меньше допустимого множества «родительской» задачи, в то же время объединение допустимых множеств «дочерних» задач с учётом целочисленности в точности равно допустимому множеству «родительской» задачи с учётом целочисленности. Добавляемые ограничения представляют собой отсекающие плоскости, т.е оптимальное решение «родит» задачи не удовлетворяет каждому ограничению (5), (6). После «дочерних» задач решаем либо их обе, либо какую-то одну из них и продолжаем процесс ветвления.
Критерии окончания ветвления:
В задаче на максимум в начале решения граничное значение целевой функции, или рекорд, полается равным -∞.
1. Получена задача, не имеющая решения. Это становится все более вероятным с увеличением глубины ветвления, когда все большее число ограничений вида (5) или (6) добавляется к уже существующим ограничениям ( так, что все более вероятным становится несовместимость системы ограничений получаемых задач).
2. Если находится новое целочисленное решение, то оно сравнивается с рекордом; если прежний рекорд превзойден, то запоминается новый рекорд, в противном случае остается старый.
3. Получаемое оптимальное нецелочисленное решение задачи на какой-то стадии ветвления сравнивается с рекордом; если это значение меньше, чем рекорд, то ветвление задачи прекращается, так как нет возможности побить рекорд.
Непобитый рекорд дает оптимальное решение исходной задачи ЦЛП.
Динамическое программирование представляет собой математический аппарат, разработанный для решения некоторого класса задач математического программирования путем их разложения на относительно небольшие и, следовательно, менее сложные задачи. Специфика метода динамического программирования состоит в том, что для отыскания оптимального управления планируемая операция разделяется на ряд последовательных шагов или этапов. Соответственно и сам процесс планирования операции становится многошаговым и развивается последовательно, от этапа к этапу, причем каждый раз оптимизируется управление только на одном шаге.
В основе динамического программирования лежат 2 принципа:
Первый- принцип оптимальности Беллмана: каковы бы ни были начальное состояние системы и принятое решение, все последующие решения на остальных шагах должны составлять оптимальную стратегию относительно состояния, возникающего в результате первого решения.
Второй- принцип вложения: природа задачи, допускающая использование метода динамического программирования, не меняется при изменении числа шагов.
Структура процессов, исследуемых методом динамического программирования, должна удовлетворять следующим условиям:
небольшое число переменных
* управляемый процесс- Марковский, т.е. предыстория не имеет значения при определении будущих действий
* критерий эффективности J является аддитивным.
Состояние на каждом шаге характ-ся некоторой переменной величиной, кот. называется параметром состояния. Наилучший эффект на данном этапе вместе с уже рассмотренными шагами хар-ся функцией состояния. Решение конкретной задачи методом динамич. программирования сводится к выбору параметра состояния, составлению ф-ии состояния и рекурентных соотношений, связывающих ф-ии состояния для двух соседних последовательных этапов, и их применению для выбора оптимального управления.
Предприятие производит некоторое изделие, на которое оно имеет заказ на п месяцев.
Необходимо спланировать объем выпуска и хранения
продукции для каждого месяца его работы при условии, что суммарные затраты на производство и хранение продукции за п месяцев будут минимальными при полном удовлетворении спроса на продукцию. При этом уровень запасов к началу первого месяцазадан, а к концу последнего. Известны также спрос на продукцию в каждом j-м месяце и затраты на производство и хранение единиц продукции в каждом j-м месяце.
F(x1, x2, x3, x4) =f1(x1) + f2(x2) + f3(x3) + f4(x4)
x1+x2+x3+x4= Z(700)
gk= max( fk(xk) + gk-1 (Z-xk)) F= g4(Z)
xk= 0, 100, 200, 300, 400
|
G3 F3 |
0 100 200 300 400 |
|
0 100 200 300 400 |
95 97 105 101 99 |
g3(400) =105
73.Составить математическую модель и записать функциональное уравнение Беллмана
(рекуррентное соотношение), расшифровать все переменные и функции, входящие в него
для следующей задачи:
Предполагается, что принимают целые неотрицательные значения.
2). Пусть требуется загрузить в самолет грузоподъемностью W тонн груз, состоящий из предметов п различных типов, таким образом, чтобы стоимость всего груза была
максимальной. Для каждого предмета j-го типа, j= 1,2,. . . ,п, заданы вес в тоннах и
стоимость в тысячах рублей одного предмета этого типа, где все и -целые
положительные числа. Причем предметов каждого типа можно загружать в самолет по несколько штук.
Ур-ние Беллмана: Fk*(ξ) = max {fk (xk) + Fk-1(ξ-xk)} = fk() + F(ξ-)
0 xk ξ xk
0 ξb
Fk*(ξ) – max приращение прибыли по k предприятиям.
74.Составить математическую модель и записать функциональное уравнение Беллмана
(рекуррентное соотношение), расшифровать все переменные и функции, входящие в него
для следующей задачи:
Средства в размере b млн. рублей распределяются между п предприятиями в количествах,
кратных а млн. руб., причем - целое число. При выделении j-му предприятию млн. рублей оно приносит доход млн. рублей.Требуется распределить выделенные средства так, чтобы суммарный доход по всем предприятиям был максимальным.
Ур-ние Беллмана: Fk*(ξ) = max {fk (xk) + Fk-1(ξ-xk)} = fk() + F(ξ-)
0 xk ξ xk
0 ξb
Fk*(ξ) – max приращение прибыли по k предприятиям.
Обозначим через прирост мощности или прибыли на i-м предприятии, если оно получит рублей капитальных вложений. Требуется найти такое распределение капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли
при ограничении по общей сумме капитальных вложений причем будем считать, что все переменные принимают только целые неотрицательные значения: или или или
Функции мы считаем заданными, заметив, что их определение – довольно трудоемкая экономическая задача. Введем параметр состояния и определим функцию состояния. За параметр состояния примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния определим как максимальную прибыль на первых предприятиях, если они вместе получают рублей. Параметр может изменяться от до . Если из рублей -е предприятие получит рублей, то каково бы ни было это значение, остальные рублей естественно распределить между предприятиями от первого до -го так, чтобы была получена максимальная прибыль . Тогда прибыль предприятий будет равна . Надо выбрать такое значение между и , чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношениюдля . Если же , то (при условии, что функция возрастающая).
75. Составить математическую модель и записать функциональное уравнение Беллмана
(рекуррентное соотношение), расшифровать все переменные и функции, входящие в него
для следующей задачи:
Предприятие может производить п видов изделий, располагая некоторым ресурсом в объеме
b единиц (b - целое положительное число). Известны затраты ресурса на изготовление
одного изделия j-го вида, а также известна ожидаемая прибыль сj от реализации одного
изделия j-го вида (. - целые положительные числа), j = 1, 2,..., п.
Требуется составить план выпуска изделий, максимизирующий суммарную прибыль.
Требуется найти такой план выпуска изделий (x1,x2, ... , xn), которое максимизирует суммарную прибыль: z = c1x1 + c2х2 + ... + cnxn
при ограниченности ресурсов:
причем все переменные xj принимают только целые неотрицательные значения: xj = 0, 1, 2 ...
За параметр состояния принимаем количество ресурсов, выделяемых для производства нескольких видов изделий, а функцию состояния Сk() определим как максимальную прибыль при производстве k видов изделий, если для их производства имеется единиц ресурса, функцию Аk() как издержки при производстве k видов изделий, если для их производства имеется единиц ресурса. Параметр может изменяться от 0 до b.
Fk()=max{(ck-ak) xk + Сk-1(-xk)-A k-1(-xk)}, 0 xk
76. Составить математическую модель и записать функциональное уравнение Беллмана
(рекуррентное соотношение), расшифровать все переменные и функции, входящие в него
для следующей задачи:
Пусть п предприятиями некоторого объединения должен быть произведен определенный
продукт в количестве b единиц. При изготовлении хj единиц продукта на j-м предприятии
издержки составляют денежных единиц. Требуется спланировать производство
данного продукта на предприятиях объединения так, чтобы суммарные издержки объединения были минимальными.
дохода?
Принять, выработать решение в условиях определенности - это фактически найти экстремум известной функции при установленных ограничениях. Когда же некоторые существенные обстоятельства принятия решений известны не полностью или случайны, то говорят, что решение принимается в условиях неопределенности. Иными словами, неопределенность - это отрицание определенности. Не все случайное можно измерить вероятностью. Неопределенность - более широкое понятие. Неопределенность того, какой цифрой вверх ляжет игральный кубик, отличается от неопределенности того, каково будет состояние российской экономики через 15 лет. Иначе говоря, уникальные единичные случайные явления связаны с неопределенностью, а массовые случайные явления обязательно допускают некоторые закономерности вероятностного характере.
Предположим, что лицо, принимающее решение, может выбрать одну из возможных альтернатив, обозначенных номерами i = 1, 2, …, m. Ситуация является полностью неопределенной, т. е. известен лишь набор возможных вариантов состояний внешней (по отношению к лицу, принимающему решение) среды, обозначенных номерами j = 1, 2, …, n. Если будет принято i-e решение, а состояние внешней среды соответствует j-й ситуации, то лицо, принимающее решение, получит доход qij.
Ситуация с полной неопределенностью характеризуется отсутствием какой бы то ни было дополнительной информации. В ситуации с полной неопределенностью могут быть высказаны лишь некоторые рекомендации предварительного характера относительно того, какое решение нужно принять.
Предположим, что в рассмотренной схеме известны вероятности pj того, что реальная ситуация развивается по варианту j. Именно такое положение называется частичной неопределенностью.
Предположим, что ЛПР рассматривает несколько (i=1,…,m) возможных решений. Ситуация неопределенная, понятно лишь, что наличествует какой-то из вариантов j=1,…,n. Если будет принято i-е решение в j-й ситуации, то фирма, возглавляемая ЛПР, получит доход qij. Матрица Q=|| qij || называется матрицей последствий( возможных решений). Какое же решение нужно принять ЛПР? В ситуации полной неопределенности могут быть высказаны лишь некоторые рекомендации предварительного характера. Они не обязательно будут приняты ЛПР. Многое будет зависеть, например, от его склонности к риску. Но как оценить риск в данной схеме?
Допустим, мы хотим оценить риск, который несет в себе i-е решение. Нам неизвестна реальная ситуация. Но если бы мы ее знали, то выбрали бы наилучшее решение, т.е. приносящее наибольший доход, в j-й ситуации было бы принято решение, дающее доход qj= max{qij}. Значит, принимая i-е решение, мы рискуем получить не qj, а только qij и недобрать rij=qj-qi. Матрица R=|| rij || называется матрицей рисков.
редположим, что лицо, принимающее решение, рассматривает нес-ко (i = 1, 2, …, m) возможных решений. Ситуация неопределенна, понятно лишь, что наличествует какой-то из вариантов j = 1, 2, …, n. Если будет принято i-e решение в j-й ситуации, то фирма, возглавляемая ЛПР, получит доход qij. Матрица Q = ||qij || называется матрицей последствий (возможных решений).
В ситуации полной неопределенности могут быть высказаны лишь некоторые рекомендации предварительного характера относительно того, какое решение нужно принять. Эти рекомендации не обязательно будут приняты. Многое будет зависеть, например, от склонности к риску ЛПР. Но как оценить риск в данной схеме?
Допустим, мы хотим оценить риск, который несет в себе i-e решение. Нам неизвестна реальная ситуация. Но если бы мы её знали, то выбрали бы наилучшее решение, т. е. приносящее наибольший доход, - в j-ситуации было бы принято решение, дающее доход qj=max{qij} i
Значит, принимая i-e решение, мы рискуем получить не qj, а только qij и недобрать rij= qj - qij. Матрица R = ||rij|| наз-ся матрицей рисков.
Пример. Пусть матрица последствий есть
5 2 8 4
Q= 2 3 4 12
8 5 3 10
1 4 2 8
Составим матрицу рисков. Имеем q1= max{qi1}=8, q2=5, q3=8, q4=12
i
Следовательно, матрица рисков
3 3 0 8
R= 6 2 4 0
0 0 5 2
7 1 6 4
Правило крайнего пессимизма. Рассматривая i-е решение, будем полагать, что на самом деле ситуация складывается самая плохая, т.е. приносящая самый малый доход ai = minj{qij}. Но теперь среди ai выберем i0-е решение с наибольшим aij. Итак, правило Вальда рекомендует принять i0-е решение, такое, что
ПРАВИЛО СЭВИДЖА (правило минимальных сожалений или минимального риска). При применении этого правила анализируется матрица рисков R. Рассматривая i-e решение, будем полагать, что на самом деле складывается ситуация максимального риска , и выберем решение i0 с наименьшим bi. Итак, правило Сэвиджа рекомендует принять такое решение i0, что:
Правило Гурвица (взвешивающее пессимистический и оптимистический подходы к ситуации). Принимается i-е решение, при котором достигается max{λmin {qij} + (1-λ)max{qij}}, где 0 ≤ λ ≤1.
j j
Значение λ выбирается из субъективных соображений. Если λ →1, то правило Гурвица приближается к правилу Вальда (правило крайнего пессимизма), при λ →0 правило Гурвица приближается к правилу «розового оптимизма» (т.е. предполагается, что какое бы решение мы ни выбрали, реализуется самая лучшая ситуация – приносящая наибольший доход max{qij}).
j
Т.е. Гурвиц предлагает некоторую среднюю стратегию между самыми наихудшими условиями и «розовым оптимизмом».
ЛПР считает, что для него сложится самая благоприятная ситуация, т.е. он получит самый большой доход в результате своей деятельности ci = max qij. Теперь выберем решение i0 с наибольшим ci0. Итак, правило “розового оптимизма рекомендует принять решение i0 такое, что ci0 = max (max qij). Так, в вышеуказанном примере имеем с1 = 6, с2 = 22, с3 = 32, с4 = 10. Теперь из чисел 6, 22, 32, 10 берем максимальное. Это — 32. Значит, правило “розового оптимизма” рекомендует 3-е решение.
Существует ещё одно понимание риска. Рассмотрим какую-либо операцию, доход которой есть случайная величина Q. Как мы знаем средний ожидаемый доход- математическое ожидание случайной величины MQ а вот среднее квадратическое отклонение (СКО) σQ=√DQ- это мера разброса возможных значений дохода вокруг среднего ожидаемого дохода mQ.
Напомним что DQ=M(Q-MQ)².среднее квадратичное отклонение дохода от операции r1=√DQi в данном случае и будет служить определение меры риска.
Пусть на финансовом рынке имеется возможность осуществить несколько финансовых операций Q1, Q2, …, Qn, ожидаемые эффективности и риски которых известны и равны соответственно , ,…, и r1, r2, …, rn.
Говорят, что операция Qi доминирует операцию Qj, если , или ,
ri < rj ri rj .
Если из рассмотренных операций необходимо выбрать лучшую, то ее надо обязательно выбирать из операций, оптимальных по Парето. Для нахождения лучшей операции иногда применяют подходящую взвешивающую формулу. Для пар (q, r) данная формула дает одно число, по которому и определяют лучшую операцию.
Пусть взвешивающая формула есть Φ(q, r)= q-r
Вычисляем, получаем
Φ(Q1)= 4.83-1.77= 3.064 ; Φ(Q2)= 0.6; Φ(Q3)= 4.7; Φ(Q4)= 0.27
и лучшей операцией оказывается третья.
При многократном повторении всей ситуации, котор. применяется в этой операции, доход будет примерное равен рассчитанному среднему.
Доход, получаемый при принятии i-го решения, является случайной величиной Qi с рядом распределения:
Средний ожидаемый доход при принятии i-го решения оценивается математическим ожиданием M(Qi) соответствующей случайной величины Qi. Правило максимизации ожидаемого дохода рекомендует принять решение, приносящее максимальный средний ожидаемый доход.
Правило максимизации среднего ожидаемого дохода. Доход, получаемый фирмой при реализации i-го решения, является случайной величиной Qi с рядом распределения
qi1 … qin
p1 … pn
Математическое ожидание MQi есть средний ожидаемый доход. Рассматриваемое правило рекомендует принять решение, приносящее максимальный средний ожидаемый доход.
Если нужно выбрать 1 ход: 1ый игрок при анализе матрицы исходит из положения. Что на любой его ход 2о1 игрок ответит на ихудшим образом для 1го. Поэтому первый игрок в каждой строке выбирает мин эл- т 1ый игрок выбирает ту строку, для которой значение Соответственно альфа кА гарантирует выигрыш первому при любом поведении второго не меньше, чем альфа кА и альфа кА – нижняя цена игры или максимин. 2о1 игрок исходит из предположения, что 1ый ответит на любой ход второго наихудшим образом для него. Выбираем бета эс минимальное из всех по столбцам. «ой игрок гарантирует, что 1ый игрок выиграет не больше, чем бэта эс. Бэта эс-верхняя цена игры.
Если α= β, то говорят, что игра имеет седловую точку в чистых стратегиях. Общее значение α и β называется ценой игры и обозначается v= α= β . При этом стратегии игроков, соответствующие седлововой точке, называются оптимальными чистыми стратегиями, так как эти стратегии являются наиболее выгодными сразу для обоих игроков, обеспечивая первому игроку гарантированный выигрыш не менее v, а второму игроку- гарантированный проигрыш не более (-v), и отклоняться игрокам от этих стратегий невыгодно.
M(P, Q*) V M(P*, Q). Для того, чтобы P*, Q* необходимо и достаточно, чтобы для всех чистых стратегий выполнялось: M(Pi, Q*) V M(P*, Qj). Далее для каждой строки расписываем m неравенств и, если надо, для каждого столбца расписываем n неравенств. Потом решаем систему неравенств (относительно параметра).
PAGE \* MERGEFORMAT 14