Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ (МИИТ)

Институт управления и информационных технологий

Кафедра «Логистические транспортные системы и технологии»

РЕШЕНИЕ ЗАДАЧ ТРАНСПОРТНОЙ ЛОГИСТИКИ МЕТОДАМИ ЛИНЕЙНОЙ АЛГЕБРЫ

Учебное пособие для студентов ИУИТ

ПАШКОВ Н. Н.

Москва, 2014



Оглавление

линейный уравнение математический аналитический

1. Математический аппарат

1.1 Матрицы и определители

1.2 Решение систем линейных уравнений

2. Матричные игровые задачи

3. Методы решения игровых задач

3.1 Метод обратной матрицы

3.2 Метод псевдообратной матрицы

4. Двойственность задач линейного программирования

Литература



1. Математический аппарат

Понимание и практическое применение современных аналитических методов для исследования свойств объектов предполагает хорошую математическую подготовку. Изучение характеристик объектов разными математическими методами повышает достоверность знаний о свойствах этого объекта. Эффективные аналитические методы решения задач транспортной логистики дает линейная алгебра, для освоения которой необходимы знания основных понятий и элементов теории матриц [1, 2]. Некоторые необходимые сведения из теории матриц, которые широко используются во многих современных вычислительных технологиях, приведены ниже.

1.1 Матрицы и определители

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

.

Такая таблица чисел называется числовой матрицей (в дальнейшем - просто матрицей). Числа , которые входят в матрицу, называются ее элементами. Индексы i и j элемента указывают соответственно номера строки и столбца, в которых расположен элемент . Матрицу, содержащую одну строку (или один столбец), называют также вектор-строкой (или вектор-столбцом).

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

Матрицей, транспонированной к матрице , называется матрица вида:

,

т. е. - строками матрицы являются столбцы , а столбцами - строки матрицы .

Если число строк равно числу столбцов (т = п), матрицу называют квадратной матрицей порядка п.

Элементы , , , …, образуют так называемую главную диагональ квадратной матрицы; элементы , , …, - побочную диагональ квадратной матрицы.

Рассмотрим некоторые действия над матрицами.

1. Произведением матрицы на число , (или, что то же самое, числа на матрицу ) называется матрица:

,

полученная из путем умножения каждого ее элемента на число .

2. Под суммой двух матриц:

,

понимается матрица:

,

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

Линейные операции над матрицами подчиняются обычным законам арифметики, например:

,

(все элементы матрицы 0 -- нули),

.

3. Произведением матрицы из т строк и п столбцов на матрицу из n строк и k столбцов называется матрица , имеющая т строк и k столбцов, элемент которой, расположенный в i-й строке и j-м столбце, равен сумме произведений элементов i-й строки матрицы на соответствующие элементы j-го столбца матрицы , т.е. находится по формуле скалярного произведения i-й вектор-строки матрицы на j-й вектор-столбец матрицы :

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

Для произведения матриц остаются в силе следующие законы арифметики:

1. Распределительный закон:

(А + В) С = АС + ВС, С (А + В) = СА + СВ.

2. Сочетательный (ассоциативный) закон:

(АВ) С = А (ВС).

С каждой квадратной матрицей определенным образом связано некоторое число, называемое ее определителем.

Рассмотрим определитель n-го порядка:

Выделим в нем некоторый элемент, например . Вычеркнем в определителе i-ю строку и j-й столбец, в которых расположен выделенный элемент . В результате останется определитель (n - 1)-го порядка. Этот оставшийся определитель называется минором элемента в определителе и обозначается .

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

Теорема (о разложении определителя). Определитель матрицы А равен сумме произведений всех элементов некоторого столбца (строки) на их алгебраические дополнения:

Приведем основные свойства определителей.

1. При транспонировании матрицы ее определитель не меняется. Это свойство свидетельствует о полном равноправии строк и столбцов матрицы. Следовательно, если некоторое утверждение справедливо относительно столбцов матрицы, то аналогичное утверждение справедливо и для её строк.

2. Если все элементы какого-либо столбца (строки) матрицы равны нулю, то определитель равен нулю.

3. При перестановке двух любых, столбцов (строк) матрицы, знак определителя меняется на противоположный, а абсолютная величина остается неизменной.

4. Определитель матрицы с двумя одинаковыми столбцами (строками) равен нулю.

5. Если j-й столбец (строка) матрицы является линейной комбинацией:

,

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

,

определителей и матриц, в которых столбцы (строки) j заменены соответственно на столбцы (строки) и . Остальные столбцы (строки) сохранены без изменения.

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

Среди квадратных матриц особую роль играет единичная матрица:

,

все элементы главной диагонали, которой, равны единице, а остальные - нулю. Легко проверить, что для любой матрицы:

.

Матрица называется обратной для матрицы , если . Матрица , обратная матрице , обычно обозначается через .

Обратная матрица может быть определена на базе следующей теоремы.

Теорема (об обратной матрице). Если матрица невырожденная (определитель матрицы не равен нулю):

,

то матрица имеет обратную матрицу , которая находится по формуле

где -- адьюнкта матрицы (присоединенная для матрицы ).

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

,

здесь:

- алгебраическое дополнение элемента матрицы ;

- минор элемента матрицы .

Алгебраическое дополнение элемента матрицы - скалярная величина (число), отличается от минора только знаком :

, если сумма индексов четная;

, если сумма индексов нечетная.

Наивысший порядок отличных от нуля миноров матрицы называется её рангом и обозначается символом . Прямоугольная матрица размера называется матрицей полного ранга, если:

.

1.2 Решение систем линейных уравнений

Рассмотрим систему п линейных уравнений с п неизвестными (такие системы уравнений называются определенными):

(1.1)

Определитель матрицы А, составленной из коэффициентов при неизвестных, называют определителем системы (1.1):

.

Решить систему уравнений (1.1) можно различными методами. Матричный аппарат позволяет найти решение линейной системы уравнений методом обратной матрицы.

Систему п линейных уравнений с п неизвестными (1.1) можно записать в матричном виде:

,

где - квадратная матрица порядка n, составленная из коэффициентов при неизвестных; x - вектор-столбец из неизвестных; b -- вектор-столбец свободных членов:

, ,

Если А - невырожденная матрица (ее определитель ), то существует обратная матрица . С учетом этого имеют место матричные соотношения:

или, с учетом того, что:

решение системы (1.1) может быть представлено в компактном виде:

. (1.2)

Таким образом, соотношение (1.2) лежит в основе решения системы уравнений (1.1) методом обратной матрицы.

Рассмотрим систему т линейных уравнений с п неизвестными (при т < п такие системы называются неопределенными):

(1.3)

или в векторной записи:

,

где , , …, ,

- соответствующие вектор-столбцы.

Запишем расширенную матрицу этой системы в виде:

Элементарными преобразованиями системы (1.3) (или матрицы ) называются следующие преобразования:

* перестановка любых двух уравнений;

* умножение обеих частей одного из уравнений на любое отличное от нуля число;

* прибавление к обеим частям одного уравнения соответствующих частей другого, умноженных на любое число, отличное от нуля;

* вычеркивание нулевой строки (уравнения с нулевыми коэффициентами и свободным членом, равным 0).

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

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

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

В процессе решения могут встретиться следующие случаи.

1. Получена матрица ', эквивалентная матрице , в левой части некоторой строки ее стоят нули, а в правой - число, отличное от нуля, что соответствует уравнению:

.

Это признак несовместности системы (3), и система не имеет положительных решений.

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

В этом случае система (2.17) совместная, определенная и имеет единственное решение:

3. На некотором этапе получилась расширенная матрица вида

Система совместная и имеет бесконечное множество решений.

Общее решение системы можно записать в виде:

…………………………………..

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

Неизвестные , ,…, называются базисными, или основными, они соответствуют линейно-независимым векторам.

Таким образом, любые r переменных называются базисными (основными), если определитель матрицы коэффициентов при них отличен от нуля, а остальные (п - r) переменных называются свободными, или неосновными. Базисным решением системы уравнений называется частное решение, в котором неосновные переменные имеют нулевые значения.

Число базисных переменных определяется рангом матрицы :

.

Каждому разбиению на основные и неосновные переменные соответствует одно базисное решение, а количество способов разбиения не превышает величины [3]:

Или

Если все компоненты базисного решения неотрицательны, то такое решение называется опорным.



2. Матричные игровые задачи

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

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

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

Напомним, кратко, основные положения и термины теории игр [2, 4]. Игрой называют конфликтные ситуации при совместной деятельности двух участников А и В, имеющих конечное число стратегий достижения противоположных целей.

Пусть игрок А имеет m стратегий: А₁, А₂, …, А_m, а игрок В - n стратегий: В₁, В₂, …, В_n. Каждой паре стратегий (А_i,В_j), когда А применяет свою стратегию А_i, а В - стратегию В_j, ставится в соответствие символ , числовое значение которого равно выигрышу игрока А у игрока В (если > 0), или проигрышу игрока А игроку В (если < 0).

Коэффициенты можно записать в виде таблицы, размером , где m - число строк, n - число столбцов таблицы. В этой таблице каждой стратегии А_i соответствует i-я строка, а каждой стратегии В_j - j-й столбец:

		B1	B2	…	Bn
	A1	a11	a12	…	a1n
A =	A2	a12	a22	…	a2n
	…	…	…	…	…
	Am	am1	am2	…	аmn

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

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

.

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

- дублирующие стратегии,

- очевидные невыгодные стратегии,

- седловые точки.

В матрице игры i-я стратегия дублирует j-ю стратегию, если:

для или для .

Невыгодные (проигрышные) стратегии определяются с помощью отношений доминирования. Если каждой стратегии игрока А поставить в соответствие вектор-строку матрицы А, то стратегия А_i, будет доминировать стратегию А_j, при выполнении следующего условия:

для .

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

Если каждой стратегии игрока В поставить в соответствие вектор-столбец платежной матрицы А, то стратегия В_j будет доминировать над стратегией В_i при выполнении следующего условия:

для .

В этом случае стратегия В_j будет заведомо невыгодной (проигрышной), и соответствующий столбец из платежной матрицы А удаляется.

Поиск седловых точек выполняется по следующей схеме. В каждой строке матрицы А находят минимальный элемент:

и среди них определяется максимальный: .

В каждом столбце матрицы А находят максимальный элемент:



и среди них определяется минимальный: .

Если , то - седловая точка. Соответствующая седловой точке пара стратегий (А_i, В_j) называется оптимальной чистой стратегией, которая определяет точку равновесия конфликтной ситуации (игры). Значение называется чистой ценой игры, или решением игровой задачи.

В общем случае, решения игры всегда имеют нижнюю границу и верхнюю границу :

.

Если седловой точки нет, то оптимальное решение в чистых стратегиях отсутствует и приходится искать его в смешанной стратегии, предполагая, что число повторений игры достаточно для ранжирования стратегий по вероятностям их применения (по средним «весам», по «долям», «пропорциям»). Задача состоит в определении набора таких стратегий игрока А, которые обеспечивают гарантированный выигрыш при наиболее вероятном действии противоположной стороны.

Обозначим вероятности применения игроком А своих стратегий А_i m-мерным вектор-столбцом x, где m - число стратегий игрока А:

.

Элементы x_i вектора x определяют вероятность применения игроком А своей i-й стратегии А_i. Для описания вероятностей применения стратегий В_j игрока В введём n-мерный вектор столбец y, где n - число стратегий В_j:

.

Элементы этих векторов должны удовлетворять условиям нормировки полной группы событий:

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

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

или в векторно-матричной форме:

,

где - транспонированный в строку вектор-столбец x.

Оптимальными смешанными стратегиями игроков А и В называются те стратегии, которые удовлетворяют следующим условиям:

.

Выигрыш, соответствующий оптимальным смешанным стратегиям, называется ценой игры :

. (2.1)

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

Эта теорема имеет большое практическое значение: она даёт конструктивные методы поиска оптимальных стратегий при отсутствии особенностей платёжной матрицы.



3. Методы решения игровых задач

3.1 Метод обратной матрицы

Этот метод позволяет находить решение игровых задач только с квадратными платежными матрицами размерности , содержащих только активные стратегии (по n стратегий c каждой стороны). Активными стратегиями игрока называются те смешанные стратегии с наибольшими весами или вероятностями, которые он неизменно и последовательно будет применять в игре.

Метод обратной матрицы применим в следующих условиях:

1. Из платёжной матрицы удалены дублирующие и доминирующие (заведомо невыгодные) стратегии.

2. Установлено отсутствие седловой точки.

Из теорем Фробениуса и Перрона следует, что положительные матрицы А (с элементами , не имеющие дублирующих или линейно зависимых строк и столбцов, являются невырожденными (определитель матрицы ).

Математическая модель игры, в этом случае, задаётся квадратной платежной матрицей размерности :

,

обратная матрица, которой, согласно теореме раздела 1.1, может быть вычислена по формуле:

где - адьюнкта матрицы :

,

здесь:

- алгебраическое дополнение матрицы ;

- минор элемента матрицы .

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

Для определения оптимальной смешанной стратегии игрока , составим систему уравнений в предположении, что применяет свою оптимальную смешанную стратегию, а - свои чистые стратегии:

,

и учтем условие нормировки . Для компактности, запишем эту систему уравнений в векторно-матричной форме:

, (3.1)

где - вектор-строка размерности , состоящий из одних единиц.

Умножим обе части равенства справа на :



.

Произведение матрицы и обратной матрицы равно единичной диагональной матрице :

. (3.2)

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

.

Рассмотрим новый вектор вспомогательных переменных :

Поскольку , справедлива цепочка равенств:

из которой следуют:

а) формула для расчета цены игры для игрока А:

б) формула для расчета вероятностей применения стратегий стороной :

Вывод формул вычисления цены игры и вероятностей стратегий стороны В аналогичен. Запишем систему уравнений для вероятностей стратегий в векторно-матричной форме:

,

или:

. (3.3)

Для игрока В вводятся вспомогательные переменные :

Формула вычисления цены игры через вспомогательные переменные для игрока В имеет вид:

Вероятности применения стратегий стороной вычисляются по формуле:



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

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

3.2 Метод псевдообратной матрицы

Для прямоугольных платежных матриц обратная матрица, в обычном смысле, не существует, поэтому для вычисления вероятностей стратегий и цены игры применяют обобщенные обратные матрицы - псевдообратные матрицы. Для прямоугольных матриц размера (), где m - число строк, n - число столбцов, формулы вычисления псевдообратной матрицы имеют следующий вид [2, 5 стр. 47]:

.

Число строк m и число столбцов n при транспонировании меняются местами: в транспонированной матрице n - число строк, m - число столбцов. Это необходимо учитывать при выборе формулы для вычисления псевдообратной матрицы.

Применение псевдообратной матрицы, для вычисления векторов и , дает также единственное решение игровой задачи [7]. Это решение, однако, является более точным решением, чем найденное методом обратной матрицы после удаления особенностей платежной матрицы, поскольку применяется для полной исходной платежной матрицы.

Методику применения методов обращения платежных матриц рассмотрим на примере.

Пример 1 [6, стр. 191]. Поставщик может поставлять три вида продукции: А₁, А₂ и А₃, получая при этом прибыль, зависящую от состояния спроса, В₁, В₂, В₃ и В₄. В таблице 1 даны коэффициенты , характеризующие прибыль в условных единицах, которую получит поставщик, поставляя продукцию , если состояние спроса .

Таблица 1

	B1	B2	B3	B4
A1	3,0	3,0	6,0	8,0
A2	9,0	10,0	4,0	2,0
A3	7,0	7,0	5,0	4,0

Требуется определить оптимальную стратегию поставок продукции, гарантирующую среднюю прибыль при любом спросе.

Решение. Рассмотрим процедуры вычисления оптимальных стратегий (пропорций) А₁, А₂, А₃ и В₁, В₂, В₃, В₄ двумя методами: методом обратной матрицы и методом псевдообратной матрицы, и сравним найденные решения.

1. Решим задачу методом обратной матрицы. Игровая модель задачи задается платежной матрицей размера :

	B1	B2	B3	B4
	3,0	3,0	6,0	8,0	А1
A=	9,0	10,0	4,0	2,0	А2
	7,0	7,0	5,0	4,0	А3

Очевидно, что дублирующих стратегий у игроков нет. Стратегия В₂ доминирует стратегию B₁. Это означает, что для игрока В стратегия В₂ невыгодна (средний проигрыш больше), поэтому столбец В₂ можно удалить. У игрока А доминирующих строк нет. В результате удаления столбца В₂, получаем квадратную платежную матрицу A размера :

	B1	B3	B4
	3,0	6,0	8,0	А1
A=	9,0	4,0	2,0	А2
	7,0	5,0	4,0	А3

Обратная матрица равна:

	0,273	0,727	-0,909
	-1,000	-2,000	3,000
	0,773	1,227	-1,909

Найдем по формуле (3.2) вспомогательный вектор :

		0,045	-0,045	0,182

где .

По определению , поэтому принимаем :

	0,045	0,0	0,182

и вычисляем сумму :

=	0,227.

Находим оптимальные вероятности (частоты) применения своих стратегий стороной А:

	0,20	0,00	0,80

где учтено, что цена игры равна:

	4,40.

Таким образом, гарантированный средний выигрыш игрока А, найденный методом обратной матрицы, составляет 4,40 условных единицы, при поставке 20% продукции А₁ и 80% продукции А₃, при любом спросе В_j.

2. Найдем решение методом псевдообратной матрицы. Полный ранг прямоугольной платежной матрицы размера должен быть:

.

В рассматриваемой задаче число строк m = 3, число столбцов n = 4, следовательно:

.

Поскольку , псевдообратная матрица вычисляется по формуле:

,

где: матрица - транспонированная матрица :

	A1	A2	A3
	3,0	9,0	7,0
AT =	3,0	10,0	7,0
	6,0	4,0	5,0
	8,0	2,0	4,0

Вычислим произведение матриц и :

	118,0	97,0	104,0
AAT =	97,0	201,0	161,0
	104,0	161,0	139,0

Вычислим обратную матрицу :

	0,439	0,710	-1,151
(AAT) -1 =	0,710	1,216	-1,940
	-1,151	-1,940	3,115

Вычислим псевдообратную матрицу :

	-0,350	-0,504	0,895
A+ =	0,360	0,713	-1,045
	-0,279	-0,575	0,911
	0,331	0,353	-0,627

Найдем по формуле (3.2) вспомогательный вектор :

	0,062	-0,013	0,134

По определению , поэтому принимаем :

	0,062	0,00	0,134

и вычисляем сумму :

=	0,196.

Находим оптимальные вероятности (частоты) применения своих стратегий стороной А:

	0,315	0,00	0,685

где учтено, что цена игры равна:

	5,098.

Таким образом, гарантированный средний выигрыш игрока А, найденный методом псевдообратной матрицы, составляет 5,098 условных единицы, при поставке 31,5% продукции А₁ и 68,5% продукции А₃, при любом спросе В_j.

Очевидно, что точное решение игровой задачи методом псевдообратной матрицы дает большее значение гарантированного среднего выигрыша 5,098 > 4,40 на 13,7%, за счет большей на 6,5% поставки продукции А₁ и меньшей на 6,5% поставки продукции А₃.



4. Двойственность задач линейного программирования

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

Прямая задача: Требуется найти максимальное значение целевой функции:

, (4.1)

в условиях следующих ограничений:

, (4.2)

. (4.3)

где:

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

- вектор коэффициентов целевой функции;

- вектор переменных прямой задачи;

? число переменных прямой задачи;

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

? число ограничений;

= - () матрица коэффициентов ограничений.

Двойственная задача: Требуется найти минимальное значение целевой функции:

, (1')

в условиях следующих ограничений:

, (2')

. (3')

где:

- скалярная целевая функция двойственной задачи ЛП;

- вектор коэффициентов целевой функции;

- вектор переменных двойственной задачи;

? число переменных двойственной задачи;

- вектор ограничений двойственной задачи;

? число ограничений;

= - () матрица коэффициентов ограничений.

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

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

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

На множестве допустимых решений:

,

рассмотрим выпуклый многогранник максимальных решений:

: .

Найдем максимальное значение вектора переменных прямой задачи ЛП из неравенства (2):

, (4)

где ? псевдообратная матрица.

Число строк m и число столбцов n при транспонировании меняются местами: в двойственной задаче матрица содержит n строк и m столбцов. Это необходимо учитывать при определении формул для вычисления псевдообратной матрицы.

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

. (5)

На множестве допустимых решений:

,

рассмотрим выпуклый многогранник минимальных решений:

: .

Найдем минимальное значение вектора переменных двойственной задачи ЛП из неравенства (2'):

, (4')

После подстановки правой части (4') в (1') найдем минимальное значение целевой функции двойственной задачи ЛП:

. (5')

Правые части неравенств (5) и (5') равны: , следовательно:

= . (6)

Что и требовалось доказать.

Теорема двойственности задач линейного программирования достаточно просто распространяется на линейные многокритериальные задачи [7].

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



Литература

1. Ефимов Н. В., Розендорн Э. Р. Линейная алгебра и многомерная геометрия. 3-е изд. М.: Физматлит, 2004. 464 с.

2. Стренг Г. Линейная алгебра и ее применения. М.: МИР, 1980. 460 с.

3. Горбатов В. А. Фундаментальные основы дискретной математики. М.: Наука, Физматлит, 2000. 544 с.

4. Карманов В. Г. Математическое программирование. М.: Физматлит, 2004. 264 с.

5. Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. М.: Наука, Гл. ред. физ.-мат. литературы, 1984. 320 с.

6. Кремер Н. Ш. Исследование операций в экономике: Учеб. пособие для вузов / Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман // Под ред. проф. Н. Ш. Кремера. М.: ЮНИТИ, 2005. 407 с.

7. Пашков Н. Н. Алгебраический метод решения линейной многокритериальной задачи / Современные технологии. Системный анализ. Моделирование. № 1 (41), 2014. С. 64 - 69.

Размещено на Allbest.ru