Двойственные задачи и оценки.

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

Допустим, есть несколько станков: А₁ , А₂ , … , А_m , причем для каждого станка задано максимальное время его использования: b₁ , b₂ , … , b_m . На этих станках можно изготавливать детали нескольких видов : B₁ , B₂ , … , B_n , причем для каждого изделия известна величина прибыли, получаемая при его продаже: c₁ , c₂ , … , c_n . Известны также показатели, характеризующие затраты времени станка А_i на выпуск одной детали B_{j ,} записанные в виде матрицы чисел a_ij . Требуется установить, сколько деталей каждого вида x₁ , x₂ , … , x_n .надо выпускать, чтобы получать максимум прибыли. Прямая постановка задачи при этих условиях математически формулируется следующим образом:

F = c₁x₁+ c₂ x₂ + … + c_j x_j + … + c_n x_n → max ;

a₁₁x₁ + a₁₂ x₂ + … + a_1j x_j + … + a_1n x_n < b₁;

a₂₁x₁ + a₂₂ x₂ + … + a_2j x_j + … + a_2n x_n < b₂;

……………………………………………………

a_m1x₁ + a_m2 x₂ + … + a_mjx_j + … + a_mnx_n < b_m

Рассмотрим теперь двойственную постановку этой задачи. Допустим, мы хотим арендовать эти станки и нам надо определиться, по каким ценам рассчитываться за каждый станко-час. Мы стремимся уплатить как можно меньше за аренду, но при этом должны учитывать, что при слишком низких ценах арендодатель может отказать в аренде станков. Чтобы не допустить этого, необходимо установить цены, выгодные как арендатору, так и арендодателю. Это произойдет в случае, если при умножении цен за аренду станков на часы работы станков, потребных для выпуска каждой детали B_j , получилась сумма не меньшая, чем величина прибыли при продаже каждой этой детали.

При такой постановке задачи цель заключается в том, чтобы минимизировать общую сумму затрат на оплату аренды v_i , всех станков. Цены, отвечающие данным условиям, называются оптимальными. Обозначим величины цен через v_i , т.е. v₁ - цена аренды за 1 час работы на станке А₁, v₂ - цена аренды за 1 час работы на станке А₂ , и т . д.

Сумма произведений возможного времени работы каждого станка на соответствующую цену аренды должна быть минимальной:

F = b₁v₁+ b₂v₂ + … + b_iv_i + … + b_mv_m → min

Для того чтобы ввести ограничения, рассмотрим суммы произведений часов работы каждого станка для производства одной детали на соответствующие цены деталей при продаже. Каждая такая сумма должна быть не меньше размера прибыли от продажи одной детали. Для выпуска одной детали типа B₁ расходуется a₁₁ часов работы на станке типа А₁, a₂₁ часов работы на станке типа А₂ , и т. д. Значит, за время, достаточное для выпуска детали типа B₁ арендная плата должна составить величину a₁₁v₁+ a₂₁v₂ + … + a_i1v_i + … + a_m1v_m . Общая сумма при этом должна быть не меньше прибыли от продажи одной детали B₁

В этой двойственной формулировке система ограничений имеет вид:

a₁₁v₁ + a₂₁ v₂ + … + a_i1 v_i + … + a_m1 v_m < c₁;

a₁₂v₁ + a₂₂ v₂ + … + a_i2 v_j + … + a_m2 v_m < c₂;

……………………………………………………

a_1nv₁ + a_2n v₂ + … + a_inv_i + … + a_mnv_m < c_n

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

Транспортная задача.

Рассмотрим теперь транспортную задачу, непосредственно примыкающую к задаче линейного программирования и хорошо иллюстрирующую общие принципы оптимизации производственных систем [7]. Предположим, на предприятии имеется m складов, которые назовем «поставщиками». На этих складах находится однотипная или взаимозаменяемая продукция, которую потребляют в n цехах.

Количество запасов продукции на каждом складе A_i назовем «мощностью» и обозначим a_i (i = 1, 2, …, m). Потребности цехов B_j в заданной продукции будем рассматривать как «спрос» и обозначать b_j (j = 1, 2, …, n). Склады находятся от цехов на разных расстояниях. Обозначим эти расстояния через c _ij . Количество продукции, перевозимое от каждого склада-поставщика до цеха-потребителя, обозначим через x _ij.

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

Поставщики Ai и их мощность ai	Потребители Bj и их спрос bj
В1	…….	Вj	…….	Вn
	…….		……..
A1			……..		……..
…….	……..	……	…….	…….	…….	……..
Ai			……..		……..
…….	..….	…..	…….	..…..	…….	………
Am			……..		…….

Условия этой задачи заключаются в следующем:

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

, .

2. Каждый потребитель должен получить столько продукции, сколько требуется, т. е.

, .

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

.

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

.

5. Мощность и спросы должны быть неотрицательны

.

6. Не должны рассматриваться отрицательные поставки

.

7. Показатели c_ij (если это не является бессмысленным) могут принимать отрицательные значения.

Данная задача характеризуется тем, что уравнений в ней меньше, чем неизвестных. Это означает, что в ней имеется множество вариантов плана. Каждый план, который удовлетворяет условиям 1-6, называется допустимым. Решение транспортной задачи начинается с составления базисного плана.

Базисный план должен быть как можно ближе расположенным к оптимальному плану. Существует несколько методов составления базисного плана.

1. Метод Северо-Западного угла.

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

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

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

3. Наименьший элемент в матрице. В этом случае выбирается наименьший элемент в матрице, а затем наименьший из оставшихся элементов и т. д.

Допустим, мы имеем следующую матрицу поставщиков, потребителей и расстояний с _ij между ними (усл. ед.):

b 1 = 45	b 2 = 55	b 3 = 51	b 4 = 49
	а 1 = 20	с 11 = 10	с 12 = 1	с 13 = 2	с 14 = 8
	a 2 = 30	с 21 = 8	с 22 = 3	с 23 = 21	с 24 =1
	a 3 = 40	с 31 =6	с 32 = 5	с 33 = 6	с 34 =4
	a 4 = 50	с 41 =4	с 42 = 7	с 43 = 9	с 44 =6
	a 5 = 60	с 51 =3	с 52 = 4	с 53 = 2	с 54 = 8

Составим первый опорный план методом северо-западного угла, т. е. записывая в клетки поставки продукции x_ij , начиная с левого верхнего угла:

Перемножая c_ij и x_ij в совпадающих клетках таблицы и складывая, получаем для этого плана функцию цели, равную:

F = 20∙10 + 25∙8 + 5∙3 + 40∙5 + 10∙7 + 40∙9 + 11∙2 + 49∙8 = 1459

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

Для этого плана функция цели равна:

F = 45∙3 + 20∙1 + 30∙3 + 5∙4 + 40∙6 + 1∙9 + 10∙2 + 49∙6

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

Для этого плана функция цели равна: .

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

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

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

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

– критерий оптимальности (равный показателю с _ij из условий задачи для вошедших в опорный план клеток).

Сумма потенциалов строки и столбца должна быть равно показателю оптимальности , т. е.

, , .

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

Таблица 5.4.1 Исходная матрица.

Потребители						Мощность запасов
Потребности Потребителей

Решение:

1. Составляем первый опорный план, например, используя метод северо-западного угла.

Таблица 5.4.2. Опорный план № 1.

Поставщики и их мощность	Потребители и их спрос
B1 = 80	B2 = 50	B3 = 60	B4 = 20	B5 = 50
A1 = 40	40
A2 = 120
A3 = 60
A4 = 40

Для первого плана целевая функция оказывается равной:

F₁ = 40×5 + 40×10 + 50×7 + 30×9 + 30×6 + 20×4 + 10×12 + 40×4 = 1760.

2. Определяем потенциалы для первого опорного плана.

	4 = 5 – 1	1 = 7 – 6	3 = 9 – 6	1 = 4 - 3	9 = 12 – 3
6 = 10 - 4
3 = 6 – 3
(-5) = 4 - 9

- значения в клетках переносятся из условий задачи и равны .

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

			из условий задачи (табл. 5.4.1) 3
		2 8 -6
………….	…………..	……………	…………..

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

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

Таблица 5.4.3

			2 8 -6	4 3	2 10 -8	10 4
					7 6	15 5
		7 7	4 3
	-5	-1 6 -7	-4 3 -7	-2 11 -13	-4 5 -9

4. Отыскиваем максимальное значение характеристики свободных переменных (E _max). В нашем примере она находится в клетке A2-B5 и равна 10 (это значение обведено кружком).

Вводим свободную переменную в клетку A2-B5 (см. опорный план № 1, Табл. 5.4.1). Обозначим ее через .

Таблица 5.4.4 Изменение плана № 1.

Поставщики и их мощность	Потребители и их спрос
B1 = 80	B2 = 50	B3 = 60	B4 = 20	B5 = 50
A1 = 40
A2 = 120			30 -		+ .
A3 = 60			30 +		10 - .
A4 = 40

Правило 1: Абсолютная величина поставки должна быть в точности равна величине возможных ликвидируемых поставок. В нашем случае она равна: .

Правило 2: Баланс поставок по столбцам и строкам не должен нарушаться.

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

Баланс по строке A2 этим самым восстановлен, но нарушен баланс во столбцу B3. Восстанавливая его, в A3-B3 введем , и в A3-B5 переменную . Эта процедура носит название построение цепей. Очевидно, что цепи должны быть замкнуты.

5. Составляем план перевозок № 2.

Таблица 5.4.5

Получаем F₂ = 1660, что на 100 единиц меньше, чем в первом плане. Для каждой итерации приращение функции цели всегда равно .

Вновь составляем таблицу потенциалов, далее составляем новый план, и т. д. Эта процедура повторяется вновь и вновь до тех пор, пока не получится устойчивое решение. Для окончательного решения рассматриваемой задачи достаточно составить всего 8 планов перевозок. В итоге получаем следующее оптимальное решение: F₈ = 1430 = min. При этом оптимальный план перевозок № 8 имеет вид:

Таблица 5.4.6

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

Контрольные вопросы к главе 5.

1. Какое значение имеет решение задач линейного программирования при моделировании систем и процессов?

2. Что такое функция цели в оптимизационных задачах?

3. Как вводятся ограничения в оптимизационных задачах?

4. Как формулируется задача линейного программирования в общем виде?

5. В чем отличие формулировок задачи линейного программирования и транспортной задачи?

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

7. Что такое многоугольник решений и линия постоянного уровня?

8. Как формулируется транспортная задача?

9. Как формулируется двойственная задача линейного программирования?

10. Что представляет собой план перевозки в транспортной задаче?

11. Что является оптимальным планом перевозки в транспортной задаче?

12. Как математически формулируется функция цели в транспортной задаче?

13. Что такое базисный план и как его составить методом северо-западного угла?

14. Для чего служит метод потенциалов и в чем он заключается?

15. Сколько итераций требуется произвести при решении задач линейного программирования?

Задания к главе 5.

Примечание. При расчете вручную ограничиться тремя переменными.

Вариант 1

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

Оборудование типа I может работать не более 90 часов, а оборудование типа II-не более 70 часов. Необходимо изготовить не менее 200 изделий Т₁, 150 изделий - типа T₂ , 180 - типа Т₃ и не менее 210 - типа Т₄. Сколько времени и на каком оборудовании следует изготовлять каждое изделие при условии минимальных затрат на производство?

Вариант 2

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

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

Вариант 3

Решить транспортную задачу, заданную следующей матрицей расстояний между поставщиками и потребителями:

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

Вариант 4

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

Составить план производства изделий с максимально полной ценой.

Вариант 5

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

Найти план выпуска продукции, дающий максимальную прибыль.

Вариант 6

Решить транспортную задачу, заданную следующей матрицей расстояний между поставщиками и потребителями:

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

Вариант 7

При выплавке металла из руды и известняка готовится шихта. Завод имеет запас руды 300 т. и известняка 200 т. При загрузке печи положено обеспечить не менее 15 т металла, не более 6 т щелочи и не более 1 т серы. Содержание компонентов в шихте задано таблицей:

Исходя из средней цены (12 тыс.р. за 1т. металла), определить загрузку печи для получения максимальной прибыли. Если цена не учитывается, определить загрузку с минимальными затратами.

Вариант 8

Прутки длиной 100 см требуется разрезать на заготовки длиной 43, 33 и 47 см. Заказано по 30, 25 и 15 заготовок каждого типа. Сколько прутков по каждому варианту необходимо разрезать для получения заготовок при условии минимальных отходов? При разрезе прутков возможны следующие варианты:

Поиск по сайту: