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



страница1/3
Дата03.05.2016
Размер0.64 Mb.
  1   2   3
К.А.ДЖАФАРОВ

Методы и модели в экономике

Глава 1. Элементы математического программирования
Под принятием решений понимается сложный процесс, в котором можно выделить 4 основных этапа.

Построение качественной модели

Построение модели рассмотренной ситуации состоит из:

выделения наиболее важных факторов,

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

Построение математической модели

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

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

Экспертная проверка результатов

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

Возможны 2 случая: 1 - результаты сопоставления неудовлетворительны, отсюда, переходят ко второму циклу процесса, т.е. уточняется входная информация о моделируемом объекте и, в случае необходимости, уточняется постановка задачи, 2 - результаты сопоставления удовлетворительны „± модель принимается.

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

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

µ §


Эта система равенств и неравенств называется в задачах МП ограничением.

Общая задача МП заключается в минимизации (максимизации) скалярной функции µ § от векторного аргумента x„ЎX, т.е. на допустимом множестве X.

Основные разделы МП:

Линейное программирование

Целочисленное программирование

Динамическое программирование

Нелинейное программирование

Для начала займемся линейным программированием.

§1 Различные формы задач ЛП
1. Общая задача ЛП

µ § (1)


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

(3)


µ § (2)

Решения, удовлетворяющее ограничениям (2), называются возможными решениями задачи. Решения, удовлетворяющее ограничениям (2) и условиям (3), называются допустимыми решениями задачи. Решения, удовлетворяющее условиям (1),(2),(3), называются оптимальными решениями задачи.


2. Задача с ограничениями неравенствами

µ §,


µ §

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


3. Стандартная форма задачи ЛП (каноническая )

µ §,


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

µ §
Любую модель можно привести к стандартной форме. Рассмотрим ограничения:

Неравенства µ § можно представить в виде равенства, прибавляя остаточную переменную к левой части ограничения (вычитая избыточную переменную из левой части ограничения)

Пример µ §

Правую часть равенства всегда можно сделать неотрицательной, умножая обе части на (-1)

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

µ §

Эти изменения производятся везде, где участвует переменная.



Пример:

µ §
Целевая функция.- Перейдя к противоположному знаку можно перейти к противоположной задаче. (от max к min, и наоборот):

µ §,

Пример:


µ §

Нужно свести к стандартной форме:

Рассмотрим 2-ое ограничение µ §

3) µ §


µ §

Тогда: µ §

при ограничения: µ §

§2 Некоторые теоремы о решении задач ЛП


Рассмотрим общую задачу ЛП (1-3). Допустим, что µ § - решение.

Определение. Частное решение системы (2), соответствующие нулевым, не базисным переменным, называется базисным решением.

Базисное неотрицательное решение ((2)+(3)) называется опорным (начальным).

Без доказательств перечислим некоторые теоремы.

Теорема. Область допустимых решений системы (2) есть выпуклое множество.

Теорема. (о соответствии опорных решений и угловых точек)

Допустимое решение x является угловой точкой ОДР тогда и только тогда, когда оно опорное.

Система (2) может иметь не более чем n-r опорных решений, где n - число неизвестных , r ЁC ранг системы (2)

Теорема. (о представлении ограниченной области допустимых решений)

Если система (2),(3) имеет ограниченную область ДР, то любое ее допустимое решение представимо в виде выпуклой линейной комбинации всех ее опорных решений. Т.е., если µ §- опорные решения, то любое допустиое решение

µ §

Теорема. (о представлении неограниченной ОДР)



Если система (2),(3) имеет неограниченную ОДР, то любое допустимое решение представимо в виде:

µ §


где Rj ЁC направляющие векторы неограниченных ребер области решений.

Теорема. (о существовании опорного решения)

Если система (2),(3) имеет хотя бы одно допустимое решение, то среди этих решений имеется хотя бы одно опорное решение.

Теорема. (о существовании опорного решения в ограниченной области)

Если ОДР стандартной задачи ЛП ограничена, то оптимальное решение существует и совпадает с хотя бы одним опорным.

Теорема. (об оптимальном решении в неограниченной области)

Если ОДР стандартной задачи ЛП неограниченна, то оптимальное решение существует и совпадает с хотя бы одним опорным, если целевая функция ѓЪ(x) ограниченна сверху в задаче максимизации, и снизу ЁC в задаче минимизации.

Теорема. (фундаментальная в ЛП)

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

Теорема. (об альтернативном оптимальном решении)

Если целевая функция ѓЪ(x) достигает минимума (максимума) в нескольких опорных решениях µ §, то любое оптимальное решение является выпуклой линейной комбинацией альтернативных опорных решений, т.е.

µ §µ §


Фундаментальная теорема предлагает следующий алгоритм решения задач ЛП:

Найти все опорные решения

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

Выбрать наименьшее или наибольшее из них


§3. Графическое решение задач ЛП

Дадим графическое применение алгоритма на примере.

Пример. Небольшая фирма выпускает два вида красок для внутренних и наружных работ (I и E). Продукция обоих видов поступает в оптовую продажу. Для производства красок используется два продукта А и В.

Максимально возможные суточные запасы составляют 6 и 8 т. продуктов А и В соответственно. Расходы А и В на производство 1 тонны соответствующих красок приведены в таблице:


Исходный продуктРасходы продукта в т. на одну тонну красокМаксимальный запас. в т.IEA216B128Изучение рынка сбыта показало, что спрос на краску I никогда не превышает спроса на краску Е более чем на 1 тонну. Кроме того, установлено, что спрос на краску I никогда не превышает 2 т. в сутки. Оптовые цены 1 тонны краски I - $ 2000, E - $ 3000

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

Поставим математическую задачу.

Определим переменные :

x1 ЁC суточный объем производства краски I, в т.

x2 - суточный объем производства краски E, в т.

Целевая функция

ѓЪ(x) = 2x1 + 3x2 (в тыс $) µ §max

Ограничения:

µ §


Получили задачу ЛП о максимизации целевой функции ѓЪ(x) при указанных ограничениях.

Построим ОДР (область ОАВСDE на рис.).

Построим линию уровня целевой функции

µ § Пусть с=6

Двигаем ѓЪ(х) в сторону ОДР. Возможны 3 ситуации:

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

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

В направлении возрастания целевой функции ОДР неограниченна. В этом случае целевая функция может принимать любое значение, отсюда, задача на "max" не имеет решений.

В нашем случае ЁC одна точка D. Следовательно, задача имеет единственное решение. Координаты D найдем как точку пересечения 1 и 2 прямых.

µ §


Оптимальный план: производить 4/3 т. краски I, 10/3 т. краски E. И при этом максимальный доход будет:

µ § тыс. долларов


§4. Алгебраический метод решения задач ЛП (Симплекс метод)

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

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

Пример. µ §

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

µ §


Исходной точкой (см.рисунок) в методе станет точка О. Решение в этой точке называется начальным. От точки О можно переходить к точке А или Е. При x2 коэффициент больше, чем при x1 , µ §Поэтому выгодно увеличивать x2, т.е. двигаться к Е.

Выбор каждой последующей угловой точки определяется следующими правилами:

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

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

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

µ §


У нас 6 неизвестных, 4 уравнения, 6-4=2, приравниваем двух переменных к нулю и получаем базисное решение. В общем случае, если число неизвестных n , уравнений m, то n-m переменным придаем нулевые значения, и из ограничений получаем базисное решение. Если базисное решение удовлетворяет условию неотрицательности правых частей, то решение будет допустимым. Переменные, имеющие нулевые значения, называются не базисными. Остальные ЁC базисные.

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

Включаемая переменная ЁC небазисная в данный момент, которая будет включена в базис в следующей итерации.

Исключаемая переменная ЁC та базисная, которая на следующей итерации подлежит исключению из базиса.

Вычислительные процедуры "Симплекс-метода".

Состоит из следующих шагов:

Определение начального допустимого базисного решения. (Путем приравнивания к нулю n-m переменных)

В нашем примере: x1=x2=0.

µ § Это базисное решение соответствует точке О

x1=x2=0. ЁC небазисные, µ §µ § - базисные

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

Включаемая в базис переменная определяется условием оптимальности.

Условие оптимальности:

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

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

Если все коэффициенты при небазисных переменных в ѓЪ - уравнении неотрицательны (неположительны), то полученное решение является оптимальным.

3.Из числа переменных текущего базиса выбирается из условия допустимости исключаемая переменная, которая должна принять нулевое значение при введение в состав небазисных. Условие допустимости: в задачах max и min в качестве исключаемой выбирается та базисная переменная, для которой отношение постоянной правой части соответствующего ограничения к положительному коэффициенту при включаемой переменной минимально (в том же ограничении). В случае равенства выбор делается произвольно. Осуществляется поиск нового базисного решения методом Гаусса-Жордана. Этот процесс изменения базиса включает вычислительные процедуры двух типов.

Тип 1. (Формирование нового ведущего уравнения)

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

Тип 2. (Формирование остальных уравнений)

µ §

Продемонстрируем на нашем примере.



µ §

µ §


Составим начальную симплекс-таблицу.
Базисные переменныеx1x2s1s2s3s4Решениеs12110006(1)s21201008(2)s31-100101(3)s41000012(4)ѓЪ-2-300000Найдем включаемую переменную.

Ведущий столбец ЁC x2 (включаемая).

µ §, т.е. s2 исключаемая переменная

Тип 1. (2) µ §

Тип 2.(1) µ §

(3)µ §


(4)ЁC такое же, т.к коэффициент = 0

(ѓЪ)µ §


Базисные переменныеx1x2s1s2s3s4Решениеs13/201-1/2002(1)x21/2101/2004(2)s33/2001/2105(3)s41000012(4)ѓЪ-1/2003/20012(ѓЪ)Включаемая в базис переменная - x1

µ §исключаемая s1

Аналогичным путем получаем следующую таблицу.

Базисные переменныеx1x2s1s2s3s4Решениеx1102/3-1/3004/3(1)x201-1/32/30010/3(2)s300-11103(3)s400-2/31/3012/3(4)ѓЪ001/34/30038/3(ѓЪ)

Коэффициенты при небазисных ЁC неотрицательные.

По условию оптимальности решение оптимальное.

µ §

Теорема (об улучшении оптимального решения)



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

Если среди переменных в ѓЪ - уравнении окажется хотя бы один отрицательный коэффициент (в задаче max) и в таком столбце все элементы отрицательны, то задача имеет неограниченную область ДР.

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

Если в ограничениях задач ЛП есть знаки µ §, то для получения начального допустимого решения используются следующие методы:

М ЁC метод (метод больших штрафов), Двухэтапный метод.

Мы рассмотрим М-метод.

Рассмотрим пример.

µ §


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

µ §


Запишем в стандартной форме

µ §


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

µ §


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

µ §


Ri играют роль остаточных

За использование этих переменных вводится "штраф", приписывающий к R1 и R2 достаточно большой коэффициент М.

Тогда µ §

Замечание. В задаче max в целевой функции искусственные переменные пишутся (вводятся) со знаком "минус".

Задача сводится к

µ §


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

µ §


Получаем начальное базисное решение 6 ЁC 3 = 3, три переменные приравниваем к нулю.

µ § искусственное базисное решение

Для составления таблицы в целевой функции вместо R1 и R2 пишутся выражения, полученные из ограничений

µ §


Подставим: µ §

Получаем таблицу.

Базисные переменныеx1x2s1R1R2s2РешениеR13101003R243-10106s21200014ѓЪ7M-44M-1-M0009M

Задача решается симплекс-методом (3 итерации)

Получаем µ §

Замечание. Если М-задача не имеет решения, то исходная задача тоже не имеет решения.

§5. Двойственная задача ЛП.

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

Использование симплекс ЁC метода требует приведение задачи к стандартной форме. Двойственная задача будет получена из стандартной формы исходной задачи.

Пусть прямая задача задана в стандартной форме:

µ §

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



µ §

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

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

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

Каждой переменной прямой задачи соответствует ограничение двойственной задачи.

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

Остальные условия двойственной задачи:

Прямая задача в стандартной формеДвойственная задачаЦелевая функцияОграниченияПеременныеМаксимизацияminµ §не ограничены в знакеМинимизацияmaxµ §не ограничены в знаке

Примеры.

а) Прямая задача:

µ §

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



µ §

Приведем к стандартной форме:

µ §

µ §


x4 ЁC остаточная переменная

n = 4 переменные, m = 2 ограничения

y1, y2 ЁC переменные в двойственной задаче, ѓЪ(x) ЁC целевая функция.

µ §(по правилам 2)

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

µ §


y1, y2 ЁC не ограничены в знаке

y1µ §0, y2 - не ограничена в знаке


б) Если в исходной задаче ѓЪ - min, как изменятся условия двойственной задачи.

Тогда получим: µ §

µ §

2. а) Прямая задача



µ §

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

µ §

µ §


µ §

Стандартная форма: µ §

При ограничениях: µ §

µ §


Двойственная задача:

µ §


µ §

б) Если в исходной прямой задаче функция min, то в двойственной max.

Теорема.

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

µ §

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



Эта теорема основная теорема двойственности.

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

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

Прямая задача

µ §

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



µ §

Стандартная форма:

Отсюда,

µ §


µ §
Двойственная задача:

µ §


µ §

Стандартная форма двойственной задачи:

µ §

Целевая функция µ §



Решаем эти задачи симплекс-методом независимо друг от друга. Сначала прямую. Оптимальную таблицу получаем через три итерации.

Начальная симплекс-таблица:


Базисные переменныеx1x2x3x4RРешениеx41211010R 2-10318ѓЪ-5-2M-12+M-4-3M00-8M

Оптимальная таблица.

Базисные переменныеx1x2x3x4R Реше-ниеx201-1/52/5-1/512/5x1107/51/52/526/5ѓЪ003/529/5-2/5+M54*4/5µ §

Решаем обратную (двойственную) задачу (решение через 4 итерации).

Базис. перем.y1µ §µ §y3y4y5R1R2R3РешениеR112-2-1001005R22-110-1001012R313-300-10014ѓй-10+4M8+4M8-4M-M-M-M00021M

Базисные переменныеy1µ §µ §y3y4y5R1R2R3Решениеy5000-7/51/517/5-1/5-13/5µ §0-112/5-1/50-2/51/502/5y1100-1/5-2/501/52/5029/5ѓй000-26/5-12/5026/5-M12/5-M-M54Оптимальная таблица.


Для двойственной задачи решение выглядит так:

µ §


µ §Решение

Запишем утверждение, чтобы связать решения этих задач:

Для данной прямой задачи

х4 и R начальные базисные переменные,

µ § левые части.

Ограничения двойственной задачи, соответствующее переменным:

µ §

µ §


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

µ §


Из ѓЪ-уравнения: µ §

µ §


µ §

µ §


µ §

µ §


§6. Транспортная модель
Транспортная модель используется при разработке плана перевозок одного вида продукции из нескольких пунктов отправления в пункты назначения. Задача ЁC нахождение оптимального плана перевозок. При построении траспортной модели используются следующие величины:

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

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

Основное предположение:

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

Предположим, что

аi ЁC количество продукции, производимой в пункте i.

bj ЁC количество продукции, потребляемой в пункте назначения j.

Сij ЁC стоимость перевозки единицы продукции из пункта i в j.

xij ЁC количество продукции, перевозимой из i в j.

Сформулируем задачу; как задачу Л. П.

µ §


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

µ §


µ §- Если здесь равенство, то такая транспортная модель (Т.М.) называется сбалансированной.

§7. Решение транспортной задачи

Алгоритм решения:
Этап1: Найти начальное допустимое базисное решение. Базисных решений должно быть m+n-1.

Этап2: Найти включаемую в базис переменную. Если все небазисные переменные удовлетворяют условию оптимальности симплекс-метода, то вычисления заканчиваются. В противном случае перейти к третьему этапу.

Этап3: Найти исключаемую из базиса переменную. Найти новое базисное решение и вернуться к этапу 2.
Решаем транспортную задачу. Рассмотрим пример.

0

20



11

Пример: Дана таблица стоимостей

10

20

12



7

9
5


х11

10

х12


х13
х14

15
х21

5

х22


15

х23


5

х24


25

0

16



18

14
0

х31
х32
х33

5

х34



55151510

Решение по этапам.

Этап 1. Есть несколько методов нахождения базисного решения.

Самый удобный ЁC метод северо-западного угла.

Базисных переменных: 3+4-1=6 штук.

Приписывают переменной х11 максимальное значение, допустимое ограничениями на спрос и объем. (В данном случае это ЁC 5.)

После этого вычеркивают соответствующий столбец или строку. Это означает, что остальные элементы вычеркнутого столбца (строки) равны 0. Если ограничения выполняются одновременно, то выбор строки или столбца определяется произвольно.

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

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

В данном случае:

1) х11=5 Вычеркиваем столбец 1.

2) х12=10 Вычеркиваем строку 1.

3) х22=5 Вычеркиваем столбец 2.

4) х23=15 Вычеркиваем столбец 3.

5) х24=5 Вычеркиваем строку 2.

6) х34=5.

Этому решению соответствует ѓЪ:

µ §


Этап 2. Будем использовать Метод потенциалов.

В этом методе строке i и столбцу j ставятся в соответствие числа Ui и Vj, называемые потенциалом. Для каждой базисной переменной хij потенциалы должны удовлетворять уравнению:

µ §

Эти уравнения составляют систему из m+n-1 уравнений, неизвестных ЁC m+n.



Придавая одному из потенциалов (обычно U1) значение «0», получаем систему µ § и решая, находим остальные потенциалы.

µ § µ §


Для небазисных определим следующие величины:

µ §


µ § - небазисные

µ §


µ §

µ §


µ §

µ §


µ §

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

В данном случае, это µ § - включаемая.

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

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

уменьшить х11 на 1.

увеличить х12 на 1.

уменьшить х22 на 1.

увеличить х24 на 1.

уменьшить х34 на 1.

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

µ § выбираем исключаемую из базиса (произвольно)

Пусть будет х34. Т.е. х34 приравнивается нулю, µ § (приписано).

Остальные ЁC по таблице скорректируем.


10

0

20



11

20

0



12

7

9



16

14
0

х11

15

х12


х13
х14

15

0



х21
х22

15

х23



10

х24


25

18
5

х31
х32
х33

0

х34



55151510

Получили новое базисное решение µ §, µ §, µ §, µ §, µ §, µ §, а стоимость перевозки

µ §

Эту процедуру с самого начала продолжаем, ищем потенциалы. Алгоритм заканчивается, когда все значения µ § для данной итерации неположительны, так как решение оптимальное.



µ §, µ § µ §

µ §, µ § µ §

µ §, µ § µ §

µ §, µ §


µ §

µ §


Посчитаем µ §.

µ §


µ §

µ §


µ §

µ §


µ §

Наибольшее положительное „± х21 ЁC включаемая.

Строим цикл „± х11, х22 ЁC выбираем, х11 ЁC исключаем. х11=0 „± остальные значения не меняются.

Получили новое базисное решение:

µ §, µ §, µ §, µ §, µ §, µ §,

а стоимость плана - µ §

Требуется еще одна итерация.

µ § µ §


µ §

µ §


µ §

х14 ЁC вводимая в базис. Построим цикл „± исключаемая х24.

Получили оптимальное решение.

µ §, µ §, µ §, µ §, µ §, µ §,

и при этом стоимость плана ЁC $315.

Замечания.

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

2. Метод наименьшей стоимости. Метод северо-западного угла не всегда дает «хороший» начальный план. Из методов нахождения начального плана выделим метод наименьшей стоимости. Алгоритм этого метода: выбирается переменная, которой соответствует наименьшая стоимость во всей таблице стоимостей, и ей придается возможно большее значение, допустимое ограничениями на спрос и объем производства (если их несколько, то выбор осуществляется произвольно). Далее, вычеркивается соответствующий столбец или строка. Если ограничения по столбцу и строке выполняются одновременно, то вычеркивается либо строка, либо столбец. После вычисления новых значений спроса и объема производства для всех невычеркнутых строк и столбцов процесс повторяется при возможно большем значении той переменной, которой соответствует минимальная стоимость среди невычеркнутых. Процедура завершается, когда остается одна строка или один столбец.

Рассмотрим тот же пример, и найдем начальное решение методом минимальной стоимости.

10

0



20

11

20



0

12

7



9

16

18



14
0

х11


15

х12
х13

0

х14


15
х21
х22

15

х23



10

х24


25
5

х31
х32


х33
х34

55151510Данное решение найдено так:

1) х12=15 , вычеркиваем столбец 2.

2) х31=5 , вычеркиваем строку 3.

3) х23=15 , вычеркиваем столбец 3.

4) х11=0 , вычеркиваем столбец 1.

5) х14=0 , вычеркиваем строку 1.

6) х24=10.

Этому решению соответствует ѓЪ = $335.

3. Распределительный метод. Это один из методов отыскания оптимального решения после нахождения начального плана. Он состоит в непосредственном отыскании свободных клеток (соответсвующие небазисным переменным) в таблице стоимостей с отрицательной ценой цикла и в перенесении перевозок по этому циклу. Ценой цикла назовем алгебраическую сумму стоимостей, стоящих в вершинах цикла, причем стоимости, стоящие в вершинах со знаком «+» берутся со знаком «+», а стоимости, стоящие в вершинах со знаком «-» берутся со знаком «-». Сначала выбирается небазисная переменная с наименьшей стоимостью для включения в новый базис и строится цикл. Аналогично тому, как это делалось раньше, выбирается исключаемая из базиса переменная. Процедура продолжается, пока не получится цикл с неотрицательной ценой. Если циклов с отрицательной ценой больше не осталось, то дальнейшее улучшение плана невозможно, т.е. оптимальный план получен. Продемонстрируем этот метод на том же примере.

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

10

20



12

7

9


5

х11


10

х12
х13


х14

15
х21

5

х22


15

х23


5

х24


25

0

16



18

14

х31


х32
х33

5

х34



55151510

Начальный план: х11=5, х12=10, х22=5, х23=15, х24=5, х34=5.

Этому решению соответствует ѓЪ:

µ §


Возьмем свободную клетку, стоимость перевозки в которой минимальна, т.е. клетку с . х31 Эта переменная и будет включаемой в новый базис. Строим цикл, определим цену цикла : z = 0-18+20-7+0-10 = -15. Придаем . . х31 = 5 и из базиса исключим . х34. Получили новое базисное решение: х11=0, х12=15, х22=0, х23=15, х24=10, х31=5, а стоимость перевозки . µ §

Возьмем в качестве включаемой переменную с минимальной стоимостью перевозки - х14 и строим цикл.

10

20

12



7

9
0


х11

15

х12


х13
х14

15
х21

0

х22


15

х23


10

х24


25

0

16



18

14
5

х31
х32
х33
х34

55151510


Цена цикла: z = 11-20+7-0 = -2. В качестве исключаемой выбираем переменную х24. Получили новое базисное решение: х11=0, х12=5, х22=10, х23=15, х14=10, х31=5, а стоимость перевозки . µ §

Продолжаем процедуру. В качестве включаемой выбираем переменную х21 , строим цикл. Цена цикла z = 12-7+0-10=-5.

10

20

12



7

9
0


х11

5

х12


х13

10

х14



15
х21

10

х22



15

х23
х24

25

0

16



18

14
5

х31
х32
х33
х34

55151510


Получили новое базисное решение: х21=0, х12=5, х22=10, х23=15, х14=10, х31=5, а стоимость перевозки . µ §

В качестве включаемой выбираем х11 , и строим цикл. Цена цикла положительная z = 10-0+7-12 = 5. Это означает, что дальнейшее улучшение плана невозможно. Можно проверить ( проверьте самостоятельно), что любой другой цикл будет иметь положительную цену. Таким образом, получен оптимальный план, кстати совпадающий оптимальным планом, найденным методом потенциалов.

10

20

12



7

9

х11



5

х12
х13

10

х14


15

0

х21



10

х22


15

х23
х24

25

0

16



18

14
5

х31
х32
х33
х34

55151510

Глава 2. Элементы теории игр

§ 1. Введение

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

Всякая математическая модель социально-экономического явления должна отражать присущие ему черты конфликта, т.е. описывать

а) множество заинтересованных сторон (игроков);

б) возможные действия каждой из сторон (стратегии игроков);

в) интересы сторон, представленные функциями платежа для каждой из сторон.

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

Классификация игр.

Игры можно классифицировать:

по числу игроков;

по числу стратегий;

по свойствам функций платежей;

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

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

По числу стратегий различают конечные и бесконечные игры.

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

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


  1   2   3


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница