Езу9у. Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки
 Скачать 5.85 Mb.
|
|
2.2. Разные формы постановки задачи линейного программирования Как было сказано выше, линейное программирование изучает задачи опти- мизации линейных функций нескольких переменных при наличии ограничений в форме системы линейных уравнений и неравенств, т. е. является частным случаем задачи математического программирования. 54 Линейное программирование главным образом применяется в экономиче- ских задачах планирования, управления и распределения ресурсов. Наиболее популярны транспортные задачи, распределительные задачи, задачи об упа- ковке, раскрое, о смеси, задачи производственного планирования и различные смешанные постановки. Спектр решаемых данным методом задач действи- тельно широк. Для того чтобы привести более формализованную формулировку задачи линейного программирования, сначала приведемпостановку общей формы задачи математического программирования. Необходимо найти решение Х = (x 1 , x 2 , …, x n ) системы, обеспечивающее достижение экстремума (максимума или минимума) функции задачи: ( ) ( ) ( ) Х max min 1 2 , , , n Z f x x x = … → и удовлетворяющее системе ограничений (уравнений и неравенств): ( ) ( ) ( ) 1 2 1 2 1 2 , , , 0, 1,2, , , , , , 0, 1, 2, , , , , , 0, 1, 2, , . i n i n i n x x x i l x x x i l l m x x x i m m k ϕ … = = … ϕ … ≤ = + + … ϕ … ≥ = + + … В общем случае задача линейного программирования может быть записана в виде 2 1 1 2 ( ) max, n n Z X c x c x c x = + + + → ( ) ( ) ( ) ( ) ( ) ( ) 11 1 12 2 1 1 1 1 2 2 1 2 1 1 1 1 2 1 1 1 2 2 1 2 1 1 1 1 2 1 1 1 2 2 , , , , , , n n l l ln n l n l l l l n m m mn n m n m m m m n k k kn n k a x a x a x b a x a x a x b a x a x a x b a x a x a x b a x a x a x b a x a x a x b + + + + + + + + + + + = ……………………………… + + + = + + + ≤ ……………………………… + + + ≤ + + + ≥ ……………………………… + + + ≥ 0, 1, . j x j n ≥ ∀ = Функцию Z(X) называют целевой функцией, а приведенную выше систе- му — системой ограничений задачи, причем ограничения на неотрицательность переменных x j ≥ 0, 1, j n ∀ = еще называют прямыми ограничениями задачи, а остальные ограничения — функциональными. Решение Х = (x 1 , x 2 , …, x n ) T 55 системы ограничений называют планом (или допустимым решением) задачи линейного программирования. Все допустимые решения образуют область определения задачи, или область допустимых решений. Допустимое решение, которое доставляет максимум или минимум целевой функции, называется оптимальным планом задачи. Существуют разные формы записи задачи линейного программирования. Стандартная форма задачи линейного программированияимеет следую- щий вид: 1 1 2 2 ( ) max(min), n n Z X c x c x c x = + + + → 11 1 12 1 1 21 1 22 2 2 1 1 2 , , , 0, 1, . n n n n n n m m n mn n m j a x a x a x b a x a x a x b a x a x a x b x j n + + + ≤ + + + ≤ + + + ≤ ≥ ∀ = Канонической задачей линейного программирования будем называть следу- ющую задачу: 1 1 2 2 ( ) max(min) n n Z X c x c x c x = + + + → при ограничениях, имеющих вид равенств и неотрицательности переменных: 11 1 12 2 1 1 1 21 1 22 2 2 2 2 1 1 2 2 1 1 2 2 , , , , 0, 1, . j j n n j j n n i i ij j in n i m m mj j mn n m j a x a x a x a x b a x a x a x a x b a x a x a x a x b a x a x a x a x b x j n + + + + + = + + + + + = + + + + + = + + + + + = ≥ ∀ = При этом еще добавляется требование на неотрицательность чисел, стоя- щих в правых частях b i ≥ 0, 1, . i m ∀ = 56 2.3. Правила перехода от одной формы задачи линейного программирования к другой Выше были приведены несколько форм задачи линейного программирова- ния, и, естественно, может возникнуть вопрос, а возможно ли перейти от одной формы к другой, и если да, то как это сделать. Ответить на поставленный вопрос помогут правила перехода, которые приведены ниже. 1. Для перехода от задачи максимизации целевой функции к задаче мини- мизации достаточно взять все коэффициенты c j целевой функции с обратными знаками и решить полученную задачу на максимум. После нахождения макси- мума значение целевой функции надо взять с обратным знаком. Оптимальное решение останется прежним. 2. Для перехода от ограничения типа «меньше или равно» к равенству в него необходимо ввести дополнительную неотрицательную переменную со знаком «плюс»: 1 1 1 1 1 i ij j in n i i ij j in n n i a x a x a x b a x a x a x x b + + + + + ≤ ⇔ ⇔ + + + + + = 3. Для перехода от ограничения типа «больше или равно» к равенству в него необходимо ввести дополнительную неотрицательную переменную со знаком «минус»: 1 1 1 1 1 i ij j in n i i ij j in n n i a x a x a x b a x a x a x x b + + + + + ≥ ⇔ ⇔ + + + + − = При этом в каждое неравенство вводится своя (n + i)-я дополнительная переменная. 4. Все равенства, имеющие отрицательные свободные члены, делятся на −1 для того, чтобы выполнялось условие неотрицательности чисел, стоящих в пра- вой части. 5. Если на некоторую переменную x j не накладывается условие неотрица- тельности, то делают замену переменных , j j j x x x ′ ′′ = − 0, 0. j j x x ′ ′′ ≥ ≥ В преобра- зованной задаче все переменные неотрицательные. Таким образом, любая задача линейного программирования может быть сведена к общей, стандартной или канонической задаче. Пример 2.1.Преобразовать следующую задачу в каноническую форму. Целевая функция и система ограничений выглядят следующим образом: max 1 2 ( ) 3 3 , Z X x x = + → 57 1 2 1 2 1 2 8, 2 1, 2 2; x x x x x x + ≤ − ≥ − ≤ 1 2 0, 0. x x ≥ ≥ Введем в первое неравенство дополнительную переменную x 3 ≥ 0 со знаком «плюс», во второе x 4 ≥ 0 со знаком «минус» и в третье x 5 ≥ 0 также со знаком «плюс». В результате получим систему ограничений задачи в канонической форме: 1 2 3 1 2 4 1 2 5 8, 2 1, 2 2; x x x x x x x x x + + = − − = − + = 1,2,3,4,5 0. x ≥ При этих ограничениях нужно найти максимальное значение функции: max. 1 2 3 4 5 ( ) 3 3 0 0 0 Z X x x x x x = + + + + → В дальнейшем рассмотрим экономический смысл дополнительных пере- менных в канонической задаче оптимального использования ресурсов. 2.4. Построение экономико-математических моделей, сводящихся к задачам линейного программирования Теперь, когда мы познакомились с теоретической постановкой задачи ли- нейного программирования, стоит привести конкретные виды экономических проблем, сводящихся к подобным задачам. Перед тем как построить экономико-математическую модель реальной проблемы, нужно внимательно рассмотреть экономическую ситуацию, описан- ную в условии. Необходимо разобраться, что является искомыми величинами задачи, что планируется получить, т. е. какова цель задачи и какой параметр задачи (прибыль, время, издержки и т. д.) мы хотим оптимизировать. Также стоит задать вопрос: чем мы ограничены? Затем, когда ответы на вышезаданные вопросы получены, можно присту- пать к записи математической модели. А именно, вводим переменные — иско- мые величины, формулируем критерий оптимальности и составляем целевую функцию, определяем ограничения, накладываемые на переменные. 58 В процессе записи экономико-математической модели необходимо указы- вать единицы измерения переменных. Рассмотрим несколько конкретных постановок. Простейшая задача производственного планирования Пусть имеется некоторый экономический объект (предприятие, цех, артель и т. п.), который может производить некоторую продукцию n видов. В процессе производства допустимо использование m видов ресурсов (сырья). Приме- няемые технологии изготовления характеризуются нормами затрат единицы сырья на единицу производимого продукта. Обозначим через a lj количество i-го ресурса ( 1, , ), i m ∈ … которое тратится на производство единицы j-го продукта ( 1, , ). j n ∈ … Обозначим x j (j = 1, 2, …, n) — количество единиц продукции P j , запланиро- ванной к производству; b i (i = 1, 2, …, m) — запас ресурса S i ; a ij — число единиц ресурса, затрачиваемого на изготовление единицы продукции P j (числа a ij ча- сто называют технологическими коэффициентами); c j — доход от реализации единицы продукции P j Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной. Тогда экономико-математическая модель задачи об использовании ресур- сов в общей постановке имеет вид: найти такой план Х = (x 1 , x 2 , …, x n ) T выпуска продукции, удовлетворяющей ограничениям 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 , , n n n n m m mn n m a x a x a x b a x a x a x b a x a x a x b + + + ≤ + + + ≤ …………………………… + + + ≤ и условиям 1 2 0, 0, , 0, n x x x ≥ ≥ … ≥ при которых функция 1 1 2 2 n n Z c x c x c x = + + + принимает максимальное значение. Стоит отметить, что это одна из простейших постановок задачи планиро- вания производства, которую можно расширить. Например, при составлении плана производства нередко приходится учитывать не только ограниченность ресурсов, но и директивные задания по выпуску продукции (госзаказы или уже заключенные договоры по отдельным видам продукции). 59 Пример 2.2.Фабрика может выпускать два сорта мороженого: молочное и сливочное. При производстве мороженого используется три вида сырья: мо- локо, дешевые наполнители и дорогие наполнители, недельные запасы которых составляют 5 т, 3 т и 5,7 т соответственно. Известны удельные затраты сырья для каждого из сортов. Для молочного мороженого — 0,5 кг, 0,1 кг и 0,4 кг на 1 кг мороженого. Для сливочного мороженого — 0,2 кг, 0,3 кг и 0,5 кг на 1 кг моро- женого. Цена молочного мороженого 200 руб. за килограмм. Цена сливочного мороженого 300 руб. за килограмм. Требуется так спланировать производство, чтобы обеспечить максимум дохода. Составить экономико-математическую модель данной задачи. Решение. Для простоты формализации данной задачи занесем все имеющи- еся данные в табл. 2.1, внимательно отследив соответствие единиц измерения. Таблица 2.1 Вид сырья Количество единиц сырья, за- трачиваемых на изготовление единицы мороженого, кг Запасы сырья, кг молочного сливочного Молоко 0,5 0,2 5 000 Дешевые наполнители 0,1 0,3 3 000 Дорогие наполнители 0,4 0,5 5 700 Прибыль от единицы продукции, руб. 200 300 — Обратите внимание, что так как удельные затраты сырья у нас приведены в килограммах, то и запасы сырья необходимо перевести в килограммы. Далее задаемся вопросом, какова наша цель? Получить максимальный до- ход. Откуда доход? С продажи мороженого. Как найти доход? Умножить цену килограмма мороженого на предполагаемое количество. А нам как раз и нуж- но спланировать, т. е. понять, сколько нужно изготовить того или иного вида мороженого, чтобы получить максимальный доход. Значит, вводим перемен- ные: x 1 — планируемое количество молочного мороженого, x 2 — планируемое количество сливочного мороженого. Тогда целевая функция (она же функция дохода в данном случае) имеет вид: 1 2 1 2 , 20 3 ( ) 0 00 . Z x x x x = + У нее будем искать максимум. При этом мы ограничены запасами сырья. Составим эти ограничения. Например, известно, что на производство одного килограмма молочного мороженого затрачивается 0,5 кг молока, всего пла- нируется изготовить x 1 килограмм этого вида мороженого, значит, на произ- водство молочного мороженого уйдет 0,5x 1 кг молока, аналогично на изготов- ление сливочного мороженого потребуется 0,2x 2 кг молока. Следовательно, 60 весь расход молока на производство всего мороженого составит 0,5x 1 + 0,2x 2 , а всего запасов молока — 5 000 кг. Таким образом, имеем первое ограничение: 0,5x 1 + 0,2x 2 ≤ 5 000. Заметим, что для составления мы использовали данные из таблицы, расположенные в строке с заголовком «молоко». Аналогично со- ставим ограничения на дешевые и дорогие наполнители, получим: 1 2 1 2 0,1 0,3 3 000, 0,4 0,5 5 700. x x x x + ≤ + ≤ Помимо ограничений, которые явно описаны в условии, необходимо еще наложить ограничения, связанные с экономической спецификой, а именно, что планируемое количество мороженого не может быть отрицательно. Резюмируя, получаем следующую экономико-математическую модель дан- ной проблемы: 1 2 1 2 , 200 300 ma ) x ( , Z x x x x → = + 1 2 1 2 1 2 1 2 0,5 0,2 5 000, 0,1 0,3 3 000, 0,4 0,5 5 700, 0, 0. x x x x x x x x + ≤ + ≤ + ≤ ≥ ≥ Задача составления рациона (задача о диете, о смесях) Для формулировки задачи в общей постановке обозначим: x j (j = 1, 2, …, n) — число единиц смеси n-го вида; b i (i = 1, 2, …, m) — необходимый минимум содержания в рационе некоторого питательного вещества S i ; a ij — число единиц питательного вещества S i в единице смеси j-го вида; c j — стоимость единицы смеси j-го вида. Необходимо составить дневной рацион, имеющий минималь- ную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела. Тогда экономико-математическая модель задачи имеет вид: найти такой рацион Х = (x 1 , x 2 , …, x n ) T , удовлетворяющий ограничениям 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 , , n n n n m m mn n m a x a x a x b a x a x a x b a x a x a x b + +…+ ≥ + +…+ ≥ …………………………… + +…+ ≥ и условиям 1 2 0, 0, , 0, n x x x ≥ ≥ … ≥ |