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

ДВОЙСТВЕННАЯ ФОРМУЛИРОВКА ЗАДАЧИ О ЗАГРУЗКЕ ОБОРУДОВАНИЯ

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

Есть несколько станков: А₁, А₂, …, А_m.

Задано максимальное время использования каждого из них: b₁, b₂, …, b_m.

На станках можно выпустить детали нескольких видов: В₁, В₂, …, В_n.

Известна величина прибыли, получаемой при продаже каждого изделия: с₁, с₂, …, с_j, …, c_n.

Известны показатели, характеризующие затраты времени станка А_i на выпуск одной детали В_j – матрица чисел (a_ij).

Требуется установить, сколько и каких деталей выпускать, т.е. найти значение неизвестных х₁, х₂, …, х_n.

Математически задача формулируется так:

F = c₁x₁ + c₂x₂ + ….+ c_jx_j +….+ c_nx_n  max.

Двойственная постановка этой задачи естественна и ее легко объяснить.

Допустим, что мы хотим арендовать станки и надо решить, по каким ценам рассчитываться за каждый станко-час.

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

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

Обозначим величины цен через , т.е.- цена за 1 час аренды станка А₁, - цена за 1 час аренды станка А₂ и т.д.

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

.

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

Для выпуска одной детали расходуется а₁₁ часов работы станка А₁, а₂₁ часов работы станка А₂ и т.д. Значит за время, достаточное для ее выпуска, плата за аренду должна составить

.

Общая сумма должна быть не меньше прибыли при продаже им оной детали В₁.

Тогда система ограничений имеет вид

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

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

Ответы к вариантам:

Вар.1 S1-D1/40/, S2-D1/10/, S2-D2/10/, S2-D3/30/, S3-D3/40/, S4-D3/30/, S4-D4/20/.

Вар.2 S1-D1/90/, S2-D2/10/, S2-D2/50/, S3-D2/10/, S3-D3/80/, S3-D1/10/, S4-D4/20/.

Вар.3 S1-D1/20/, S2-D1/30/, S2-D2/40/, S3-D2/20/, S3-D3/10/,S4-D3/40/, S4-D4/40/.

Вар.4 S1-D1/40/, S2-D1/30/, S2-D2/30/, S3-D2/30/, S3-D3/10/, S4-D3/60/, S4-D4/20/.

Вар.5 S4-D1/30/, S1-D1/20/, S1-D2/40/, S2-D2/30/, S2-D2/30/,S3-D3/10/, S3-D4/40/.

Вар.6 S2-D1/60/, S1-D1/10/, S1-D2/30/, S4-D2/30/, S3-D3/20/, S3-D4/10/, S4-D4/60/.

Вар.7 S2-D1/20/, S1-D2/50/, S4-D2/50/, S2-D3/10/, S3-D4/10/, S4-D4/30/, S2-D4/10/.

Вар.8 S4-D1/20/, S2-D1/10/, S3-D1/70/, S3-D2/60/, S1-D3/80/, S3-D4/20/, S1-D4/10/.

Вар.9 S2-D1/10/, S4-D1/40/, S4-D3/10/, S3-D4/20/, S1-D3/80/, S3-D2/10/, S3-D3/10/.

Вар.10 S4-D1/20/, S2-D1/10/, S3-D2/60/, S1-D1/70/, S3-D3/80/, S1-D4/20/, S3-D4/10/.

Вар.11 S1-D3/50/, S2-D4/40/, S1-D2/10/, S3-D1/30/, S3-D2/30/, S4-D2/20/, S2-D2/10/.

Вар.12 S1 –D2/50/, S2-D1/40/, S2-D3/30/, S3-D3/10/, S3-D4/10/, S4-D4/50/, S1-D4/10/.

Вар.13 ЦФ=940, число итереций=5.