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

 

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

Эти правила сводятся к следующему:

§ все ограничения исходной задачи приводят к одному виду: в случае ограничения должны иметь вид неравенств типа “ ”, в случае - типа “ ”. Неравенства, не соответствующие этому условию, умножают на (- 1);

§ выписывают матрицу коэффициентов при неизвестных и транспонируют ее ;

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

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

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

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

 

	- 1	- 2	- 4
	- 5	- 1	- 5
	- 1
	- 2

 

Запись одной задачи идет по строкам, другой – по столбцам.

 

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

 

Например, в рассмотренной задаче имели:

 

-строка		-8/3				-1/6	-7/6

 

Дополнительными были столбцы , , , поэтому получаем:

.

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

 

 

Анализ матричной игры

Теория игр – это математическая теория конфликтных ситуаций. Игра – конфликтная ситуация, регламентированная определенными правилами:

§ порядок выполнения ходов;

§ порядок выполнения каждого хода;

§ количественный результат игры.

Наиболее изучены матричные игры. Например,

 

 

 

В этой игре два участника – сторона и сторона , у каждого участника по 3 стратегии. Будем полагать, что матрица характеризует выигрыш стороны (и соответственно проигрыш стороны ).

 

Решить игру – значит, дать рекомендации каждом из сторон относительно использования их стратегий. Предварительно игру анализируют по “принципу мини-макса”. Он состоит в выборе наиболее осторожной стратегии, исходя из наихудшего образа действия другой стороны.

а) Анализируем игру с позиций стороны . Если игрок выбирает стратегию , то его гарантированный выигрыш (или самое худшее, что его ожидает) равен 3. Если он выбирает вторую стратегию, то гарантированная величина выигрыша равна 2. Наконец, если он использует стратегию , то гарантирует себе выигрыш 2. Эти величины являются минимальными в строках. Очевидно, что из этих гарантированных выигрышей сторона постарается выбрать наибольшее значение – это 3. Данную величину называют нижней ценой игры или максимином и обозначают: .

б) Анализируем игру с позиции стороны . Если игрок выбирает стратегию , то самое худшее для него – проигрыш 5. Если он остановится на стратегии , то худший исход – проигрыш 6. Если же он выберет стратегию , то наихудший для него результат – проигрыш 5. Эти величины являются максимальными в столбцах. Конечно, игрок выберет стратегию или , чтобы уменьшить гарантированный проигрыш – это число 5. Эту величину называют верхней ценой игры или минимаксом и обозначают: .

в) Цена игры – это величина, отражающая объективное соотношение сил, она всегда удовлетворяет условию: . В данном примере: .

Если , то игра имеет решение в конкретных стратегиях, называемых оптимальными. Эти оптимальные стратегии являются устойчивыми, обеспечивают равновесие в игре, а цена игры называется “ седловой точкой ”. Если такой ситуации нет, то оптимальные стратегии будут выглядеть так:

; .

где – вероятности стратегий стороны ;

– вероятности стратегий стороны .

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

Анализ матричной игры проводится в два этапа:

§ формируются двойственные задачи, решают одну из них симплекс-методом и записывают решение обеих двойственных задач;

§ определяют решение игры.

1. Запишем две двойственные задачи на основе приведенной платежной матрицы:

а) для участника	б) для участника

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

Данная задача приобретет вид:

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

 

Базис			– 1	– 1	– 1
-строка
		2/5		11/5	19/5			–3/5
		3/5		24/5	16/5			–2/5
	– 1	1/5		3/5	2/5			1/5
-строка	–1/5		2/5	3/5			–1/5
	– 1	2/19		11/19		5/19		–3/19
		5/19		56/19		–16/19		2/19
	– 1	3/19		7/19		–2/19		5/19
-строка	–5/19		1/19		–3/19		–2/19
	– 1	3/56				24/56	–11/56	–10/56
	– 1	5/56				–16/56	19/56	2/56
	– 1	7/56					–7/56	14/56
-строка	–15/19				–8/56	–1/56	–6/56

 

Решение будет иметь вид:

а)

 

б)

 

2. Найдем решение игры:

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

.

б) найдем вероятности стратегий:

; .

; ; .

; ; .

в) составим оптимальные стратегии для участников

; .

Как видим, для достижения оптимального результата стороне рекомендуется из 15 раз стратегию использовать 3 раза, стратегию – 5 раз, стратегию – чаще всего, а именно 7 раз. Для стороны стратегию – рекомендуется использовать реже всего – 1 раз из 15, гораздо чаще нужно применять стратегию – 6 раз из 15, и более всего – стратегию . Если кто-то из участников отклонится от этих рекомендаций, то он ухудшит только свое собственное положение.

 

 

Метод потенциалов

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

§ необходимым и достаточным условием существования решения является баланс между спросом и предложением;

§ по загруженным клеткам определяют систему потенциалов:

,

где – потенциал строки;

– потенциал столбца;

– тариф соответствующей клетки.

§ в оптимальном распределении сумма потенциалов строки и столбца не должна превосходить тариф соответствующей незагруженной клетки;

§ количество поставок должно быть равно величине , где - число поставщиков, - число потребителей.

Метод потенциалов осуществляется в три этапа:

1. Построение первоначального опорного плана (начальное распределение грузов).

2. 0ценка оптимальности распределения грузов с помощью системы потенциалов.

3. Улучшение плана перевозок, если оно возможно.

Второй и третий этапы повторяются до тех пор, пока решение не станет оптимальным.

 

I этап. Построение начального опорного плана

Начальное распределение можно выполнять различными способами: способом северо-западного угла, способом наименьших тарифов, двойного предпочтения, способом Фогеля, способом Лебедева-Тихомирова и др. Наиболее простым и легко реализуемым на ЭВМ является способ северо-­западного угла. Он заключается в том, что от каждого поставщика, начиная с первого, вывозят весь груз с учетом запросов потребителей. Распределение завершено, если весь груз от поставщиков вывезен, а каждый потребитель получил требуемый объем.

Рассмотрим пример: имеется три поставщика и три потребителя , указаны мощности поставщиков, спрос потребителей и тарифы на перевоз груза (табл. 1).

Таблица 1

 

Поставщики	Мощность
			50 –	+ (4)
		(3)		(1)	– 1
		(2)	50 +	– 200	– 2
					–

 

Установим, прежде всего, наличие баланса между спросом и предложением

250 + 150 + 250 = 650

200 + 250 + 200 = 650

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

.

 

II этап. Оценка оптимальности решения

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

; ;

; ; .

Имеем систему из 5 уравнений с 6 неизвестными, поэтому один из потенциалов примем равным 0. Обычно берут и находят все остальные потенциалы:

; ; ; ; .

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

; ;

; .

Условие оптимальности ни для одной из пустых клеток не выполняется. Следует улучшить решение.

 

III этап. Построение нового распределения

Из всех клеток, для которых условие оптимальности не выполняется, выбирают ту, в которой расхождение наибольшее. Если таких клеток несколько, то выбирают клетку с меньшим тарифом. Ее отмечают знаком “+”. Начиная от выбранной клетки, строят прямоугольную фигуру, все остальные вершины которой располагаются в заполненных клетках. Знаки вершин чередуют.

Прямоугольные фигуры могут быть следующих видов:

Реже встречаются фигуры такого вида:

 

 

Вид фигуры предопределен распределением поставок.

Из всех клеток, отмеченных знаком минус, выбирают наименьший груз. Его перемещают вдоль прямоугольной фигуры, прибавляя, если стоит знак “+”, и, вычитая, если стоит знак “–”. Все изменения отражают в новой таблице. Величины, не участвующие в перераспределении, в новую таблицу переносят без изменения. Обратимся к примеру: в таблице 1 знаком “–” отмечены две клетки, выбирают наименьший груз 50 и перемещают его вдоль прямоугольной фигуры. Все изменения отражают в табл. 2. Получено новое распределение: необходимо оценить его, поэтому возвращаемся ко II этапу алгоритма.

Таблица 2

 

Поставщики	Мощность
		200 –	.	+ 50
		(7) +	– 150	(1)
		(6)	+ 100	– 150
					–

 

.

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

1. В 1 строке берем 0.

2. Неизвестный потенциал столбца равен разности между издержками заполненной клетки и известным потенциалом строки.

3. Неизвестный потенциал строки равен разности между издержками заполненной клетки и известным потенциалом столбца.

Чередуя эти правила, найдем потенциалы.

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

В нашем примере самое большое расхождение между суммой потенциалов и тарифами – в клетке (2;1). Строим прямоугольную фигуру и замечаем, что две клетки, отмеченные знаком “–”, имеют одинаковую наименьшую величину 150, – этот факт ведет к вырожденному распределению. И действительно, после перемещения получим таблицу 3, в которой число загруженных клеток равно 4.

Таблица 3

 

Поставщики	Мощность
		50 –	+ (2)
			l	l	– 4
		0 +	– 250	l	– 4
				–

 

Вырожденность может появиться и исчезнуть при переходе от таблицы к таблице. Чтобы продолжить решение в случае вырожденной задачи, вводят нулевые поставки, соответствующие клетки считают условно заполненными. Нулей будет столько, сколько недостает поставок. Их вписывают в клетки, имеющие малые издержки, и при этом следят, чтобы не получался замкнутый цикл (прямоугольная фигура, во всех вершинах которой - заполненные клетки). В данном примере следует вписать один ноль и лучше всего в клетку (3; 1). В остальном решение обычное: находят потенциалы, проверяют условие оптимальности. После очередного перераспределения получим таблицу 4.

Таблица 4

 

Поставщики	Мощность
		l
			l	l	– 2
				l	– 2
				–

Задача вновь стала невырожденной - число загруженных клеток равно 5. Условие оптимальности выполняется. Размещение грузов видно из таблицы. Найденные суммы издержек на каждом этапе решения: , , , . На каждом этапе получали решение лучше предыдущего.

Замечание 1. Если мы имеем дело с открытой транспортной задачей, то для ее решения необходимо первоначально обеспечить баланс между спросом и предложением. Для этого вводят дополнительного поставщика, если спрос превышает предложение, в противном случае вводят дополнительного потребителя. Если добавляют поставщика, то его “мощностью” будет величина, недостающая до баланса, транспортные тарифы берут равными нулю. Аналогично поступают, если добавляют потребителя. В дальнейшем решение проводят по изложенному выше алгоритму. Введение дополнительного поставщика или потребителя имеет вполне определенное экономическое объяснение. В первом случае мы определяем, какому потребителю выгоднее недопоставить груз, исходя из интересов всех участников, во втором случае – у какого поставщика целесообразнее всего оставить часть груза.

Замечание 2. Ранее был подробно рассмотрен способ северо-западного угла для начального распределения грузов. Число итераций (таблиц) можно уменьшить, если воспользоваться способом наименьших тарифов. Он заключается в анализе всей матрицы тарифов, выборе наименьших значений и максимальном заполнении соответствующих клеток таблицы. Эти действия выполняются до тех пор, пока не будет распределен весь груз и удовлетворен спрос всех потребителей. В результате заполнения одной из клеток исключается из рассмотрения какой-то поставщик или потребитель. При этом условные участники транспортной задачи принимаются во внимание в последнюю очередь.

Рассмотрим пример транспортной задачи.

 

 

Поставщики	Мощность

 

Баланса между спросом и предложением нет, необходимо ввести условного поставщика с мощностью 150 тыс. единиц. Распределение выполним способом наименьших тарифов

 

Поставщики	Мощность
			-	-	-
		-
				-	-	-2
			-	-	-
			-1		-

 

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

 

 

Задачи о назначении

 

Проблема, состоящая в том, чтобы правильно распределить наличные людские ресурсы в соответствии с профессиональными требованиями, актуальна в разных сферах – в армии, в промышленности, в кадровой политике любой структуры. Математическое программирование является одним из важных инструментов в области рационального использования персонала. Центральное место в указанной проблеме занимает задача о назначении. В ней переменные интерпретируются как назначение соответствующего человека на определенную работу. Каждая переменная может принимать лишь значения, равные единице (претендент выбран) или нулю (претендент не выбран). Математическая структура этой задачи следующая:

,

или ,

где – показатели затрат (или эффективности)

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

§ приходится вписывать большое число нулей, что вызывает некоторые затруднения;

§ прямоугольная фигура перераспределения величин иногда бывает достаточно сложной.

Пример.

Семь претендентов распределяются на 7 участков деятельности. Решается задача на минимум затрат. Последовательность использования претендентов и перераспределения отражены в таблицах 1 – 3.

Таблица 1

 

места   претендент
1
								–3
								–1
	+
								–

 

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

 

Таблица 2

 

места   претендент
								–3
								–1
								–2
								–3
		+
								–

 

В таблице 2 распределение нуждается в улучшении. .

Таблица 3

 

места   претендент
								–1
								–

 

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

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

§ распределение следует вести по наибольшим показателям эффективности;

§ располагать нули также следует в клетки с большими тарифами;

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

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

Таблица 1

 

места   претендент
1
1
							+
								–

 

Таблица 2

 

места   претендент
								–4
								–

.