лекции. Лекции_МО_20. Лекции по методам оптимизации Тема Общая постановка задачи линейного программирования (2часа)
 Скачать 254.78 Kb.
|
Лекции по методам оптимизацииТема 1. Общая постановка задачи линейного программирования (2часа)Задача об использовании ресурсов (задача планирования производ-ства). Для изготовления двух видов продукции Р1, Р2используют четыре ви- да ресурсов S1 S2 S3и S4. Запасы ресурсов, число единиц ресурсов, за- трачиваемых на изготовление единицы продукции приведены с следу- ющей таблице:
Прибыль, получаемая от единицы продукции Р1,Р2– соответственно 2 и 3 $. Необходимо составить такой план производства продукции, при кото- ром прибыль от ее реализации будет максимальной. Решение. Составим экономико-математическую модель задачи. Обозначим через x1и x2– что число единиц продукции соответственно Р1и Р2, запланированных к производству. Для их изготовления потребуется 1ּx1+3ּ x2единиц ресурса S1, 2х1+1ּ x2единиц ресурса S2,0ּ x1+1 x2=x2 единиц ресурса S3и 3х1единиц ресурса S4. Так как потребление ресурсов S1, S2, S3, S4не должно превышать иx запасы 18, 16, 5 и 21 единиц, то получим следующие ограничения в виде неравенств: x1 3x2 18 2x x 16 1 2 x 2 5 (1) 3x1 21 Также по сути х1≥0, х2≥0 (2) Суммарная прибыль Fсоставит 2x1$от реализации продукции Р1и 3x2$от реализации продукции Р2, т.е. F 2x1 3x2 (3) Тогда постановка задачи имеет следующий вид: Найти такой план выпуска продукции x= (x1, x2), удовлетворяющий системе ограничений ( неравенств) (1) и условию (2), при котором функции (3) имеет максимальное значение. Функция (3) в этой задаче называется целевой или критериальной функ- цией. Определение. В задачах минимизации или максимизации, функция, которую требуется минимизировать или максимизировать (одним словом оптимизи- ровать), называется целевой или критериальной функцией. Эту задачу можно обобщить на случай nвидов продукции с использованием mвидов ресурсов. Обозначим xj, (j=1,2,…,n) – число единиц продукции Pj, запланированной к производству; bi, (i=1,…,m) - запасы ресурсов со- ответственно, Si, (i=1,…,m) , aij- число единиц ресурса Si на изготов- ление единицы продукции Pj, Cj- прибыль от реализации продукции Pj, aij называются экологическими коэффициентами. Тогда экономико – математическую модель задачи об использовании ресур- сов в общей постановке имеет следующий вид: Найти такой план ющий системе: X (x1, x2 ,..., xn) выпуска продукции, удовлетворя- a11x1 a12x2 ... a1nxn b1 a 21x1 a22 x2 ... a2n xn b2 (6) ... a ... x ... a ... x .... ... a x b m1 1 m2 2 mn n m x1 0, x2 0,..., xn 0 (7) при котором целевая функция F C1 x1 C2 x2 ... Cnxn принимает максимальное значение. (8) Задачаобиспользованиимощностей(задачаозагрузкеоборудо- вания). Предприятию задан план производства продукции по времени и номенклату- ре: требуется за время Τвыпустить n1 , n2 ,..., nk единиц продукции . P1 , P2 ,..., Pk. . Продукция производиться на станках S1, S2 ,..., Sm. Для каждого станка извест- ны производительности aij(т.е. числа единиц продукции P , которое j можно произвести на станке Si ) и затраты bij на изготовление продукции Pj на станке Siв единицу времени. Необходимо составить такой план работы станков (т.е. так распределить вы- пуск продукции между станками), чтобы затраты на производство всей про- дукции были минимальными. Составим ЭММ задачи. Обозначим через xij - время, в течение которого станок Si будет занят изго- товлением единицы продукции Pj(i 1,2,..., m, j 1,2,..., k). Так как время рабо- ты каждого станка ограничено и не превышает T, то получим: x11 x12 ... x1k T x 21 x22 ... x2k T (9) ..... ... ... ... ... xm1 xm2 ... xmk T Для выполнения плана выпуска по номенклатуре необходимо выполнение следующих неравенств: a11x11 a21x21 ... am1xm1 n1 ax ax ... a x n 12 12 22 22 m2 m2 2 (10) ... ... ... ... ... ... ... ... a1kx1k a2kx2k ... amkxmk nk Кроме того xij 0, (i 1,..., m; j 1,..., k). (11) Затраты на производство всей продукции имеют вид: F b11x11 b12 x12 ... bmkxmk (12) ЭММ задачи об использовании оборудования имеет вид: Найти такое решение x (x11, x12 ,..., xmk), удовлетворяющее системам (9),(10) и (11), при котором функция целевая (12) имеет минимальное значение. Общаязадачалинейногопрограммирования Общая задача линейного программирования имеет следующий вид: Дана линейная функция по n переменным: F C1 x1 C2 x2 ... Cnxn и система из mуравнений с nпеременными: (13) a11x1 a12 x2 ... a1nxn ()b1 ax a x ... a x b 21 1 22 2 2n n 2 (14) ... ... ... ... ... ... ... ... ... ... ... am1 x1 am2 x2 ... amnxn bn, причем xij 0, (i 1,..., m; j 1,..., k). (15) Требуется найти максимальное (минимальное) значение линейной функции (13) при выполнении условий (14) и (15). Линейная функция (13) называется целевой функцией или критериальной функцией. Система уравнений (14) называется системой ограничений или просто ограничениями. Ограничения вытекают из природы экономической задачи. Область, определяемая системой ограничений (14) и неравенствами (15), называется допустимой областью. Задача линейного программирования, в которой система ограничений состо- ит лишь из одних неравенств, называется стандартной. Задача линейного программирования, в которой система ограничений состоит только из ра- венств, называется канонической. Любая задача линейного программирова- ния может быть приведена к канонической и к стандартной. Это выполняется введением дополнительных переменных. Например, пусть требуется привести систему ограничений (14) к канониче- скому виду. Для этого введем дополнительные неотрицательные переменные xn1, xn2, ..., xnm, и система ограничений имеет вид: a11x1 a12 x2 ... a1nxn xn1 b1 a 21x1 | ||||||||||||||||||||||