Лекция 6. Метод искусственного базиса решения задачи линейного программирования

План.

6.1. Метод искусственного базиса.

6.2. Применение метода искусственного базиса.

6.1. Метод искусственного базиса

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

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

,

.

Из этой задачи составим вспомогательную задачу следующим образом:

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

2) целевая функция равна алгебраической сумме искусственных переменных, взятых с коэффициентом (-1);

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

Математическая модель вспомогательной задачи:

,

.

Система ограничений вспомогательной задачи приведена к единичному базису, поэтому она имеет решение:

= (0, 0, , 0, b₁, b₂, , b_n),

при этом  0.

Между оптимальным решением вспомогательной задачи и опорным решением исходной задачи существует зависимость:

1) если = 0 достигается при= (l₁, l₂, , l_n, 0, 0, , 0), то = (l₁, l₂, , l_n) является исходным опорным решением;

2) если max  0, то ограничения исходной задачи несовместны.

6.2. Применение метода искусственного базиса

Применение метода искусственного базиса рассмотрим на следующем примере²⁰:

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

Решение. Составим вспомогательную задачу:

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

Решим вспомогательную задачу симплексным методом:

сi	БП	0		0		0		-1		-1
		х1		х2		х3		х4		х5		bi
-1 -1	х4 х5	2 2		1 -1		1 2		1 0		0 1		1 2
j			-4		0		-3		0		0		-3
0 -1	х1 х5	1 0		½ -2		½ 1		½ -1		0 1		½ 1
j			0		2		-1		2		0		-1
0 0	х1 х3	1 0		3/2 -2		0 1		1 -1		½ 1		0 1
j			0		0		0		1		1		0

Решение вспомогательной задачи:

= (0, 0, 1, 0, 0), = 0,

Исходное опорное решение данной задачи:

= (0, 0, 1).

Проверим это решение на оптимальность:

сi	БП		4		-4	2
			х1		х2	х3	bi
4 2	х1 х3		1 0		3/2 -2	0 1	0 1
j		0		6		0	2

Ответ: = (0, 0, 1),= 2.

Лекция 7. Двойственные задачи линейного программирования

План.

7.1. Двойственная задача для стандартной задачи.

7.2. Основные теоремы двойственности.

7.3. Метод одновременного решения пары двойственных задач.

7.1. Двойственная задача для стандартной задачи

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

Рассмотрим задачу выбора оптимальной производственной программы. Пусть предприятие № 1 имеет запасы материально-сырьевых ресурсов в объемах b_i (), гдеm – число видов ресурсов. Как и раньше будем считать, что a_ij – это объем материально-сырьевых ресурсов вида i, необходимых для производства одной единицы продукции вида j, c_j – прибыль от выпуска и реализации единицы продукции вида j ().

Далее будем считать, что предприятие № 2 решило купить все материально-сырьевые ресурсы у предприятия № 1 по некоторым оптимальным ценам на эти ресурсы, которые обозначим как y₁, , y_m. Естественно, что предприятие № 2 заинтересовано в том, чтобы затраты на приобретение материально-сырьевых ресурсов были минимальными, т.е.

.

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

Для изготовления единицы продукции вида 1 расходуется a₁₁ ресурсов первого вида, a₂₁ ресурсов второго вида, , a_i1 ресурсов i-го вида. Поэтому для того чтобы удовлетворить требованиям продавца (предприятие № 1), затраты на ресурсы, используемые для изготовления одной единицы продукции первого вида, должны быть не менее ее цены с₁. Иными словами, необходимо выполнение неравенства следующего вида:

.

Аналогично можно представить ограничения по всем остальным видам продукции 2, 3, , n. Экономико-математическая модель и содержательная интерпретация получаемой таким образом задачи представлена в правой части табл. 7.1.

Таблица 7.1

Исходная (прямая) задача (I)	Двойственная задача (II)
(7.1) при ограничениях: (7.2) и условие неотрицательности (7.3) составить такой план выпуска продукции , при котором прибыль (выручка) от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов	(7.4) при ограничениях: (7.5) и условие неотрицательности (7.6) найти такой набор цен ресурсов , при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации продукции

Цены ресурсов y₁, , y_m в экономической литературе получили различные названия: учетные, неявные, теневые. Смысл их названий состоит в том, что в отличие от цен на полученную продукцию, которые достаточно точно могут прогнозироваться, цены ресурсов y₁, , y_m являются внутренними, так как они задаются не извне, а определяются в результате решения задачи, поэтому их часто называют оценками ресурсов.

Исходная и двойственная задачи обладают следующими характеристиками.

1. В первой задаче определяется максимум линейной целевой функции, во второй – минимум.

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

3. Каждая из задач задана в стандартной форме, при этом в задаче максимизации все неравенства вида «меньше или равно», а в задаче минимизации все неравенства вида «больше или равно».

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

Для задачи I .

Для задачи II .

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

6. Условие неотрицательности переменных имеются в обеих задачах.

Задачи (I и II) линейного программирования, обладающие указанными характеристиками, называются симметричными взаимодвойственными задачами. Далее будем называть их двойственными задачами. Задачу (I) еще называют исходной или прямой паре двойственных задач. Исходя из описанных характеристик двойственных задач можно сформулировать следующее правило формирования двойственной задачи.

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

2. Составить расширенную матрицу А₁, в которую включить матрицу коэффициентов при переменных А, столбец правых частей исходной системы ограничений и строку коэффициентов при переменных в целевой функции.

3. Сформировать матрицу А₁, транспонированную к матрице А₁.

4. Сформировать двойственную задачу на основании полученной матрицы А₁ и условия неотрицательности переменных.

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

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

.

Решение.

1. Так как исходная задача на максимум, то обе части первого и четвертого неравенства умножим на (1). Получим:

.

2. Составим расширенную матрицу системы:

.

3. Найдем матрицу А₁, транспонированную к матрице А₁:

.

4. Сформулируем двойственную задачу

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

.