Задачи линейного программирования

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

W = W ( a , as ).

Напомним, что в числе заданных условий а фигу­рируют и ограничения, налагаемые на элементы реше­ния. Пусть решение х представляет собой совокупность п элементов решения х1 , х2, ..., х n (иначе — n -мерный вектор):

Требуется найти такие значения х1 x 2 , ..., х n ко­торые обращают величину W в максимум или в мини­мум (оба слова в математике объединяются под одним термином «экстремум»).

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

Трудности, возникающие при решении задач мате­матического программирования, зависят: а) от вида функциональной зависимости, связывающей W с эле­ментами решения, б) от «размерности» задачи, т. е. от количества элементов решения x 1 , x 2 , ..., xn , и в) от вида и количества ограничений, наложенных на эле­менты решения.

Среди задач математического программирования са­мыми простыми (и лучше всего изученными) являются так называемые задачи линейного програм­мирования. Характерно для них то, что: а) пока­затель эффективности (целевая функция) W линей­но зависит от элементов решения x 1 t x 2 ..... xn и б) ограничения, налагаемые на элементы решения, имеют ннд линейных равенств или неравенств относитель­но x 1, x 2 , .. ., xn .

Такие задачи довольно часто встречаются на прак­тике, например, при решении проблем, связанных с распределением ресурсов, планированием производст­ва, организацией работы транспорта и т. д. Это и ес­тественно, так как во многих задачах практики «рас­ходы» и «доходы» линейно зависят от количества за­купленных или утилизированных средств (например, суммарная стоимость партии товаров линейно зависит от количества закупленных единиц; оплата перевозок производите)! пропорционально весам перевозимых гру­зов н т. д.).

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

Приведем несколько примеров задач линейного про­граммирования.

1. Задача о пищевом рационе. Ферма производит откорм скота с коммерческой целью. Для простоты до­пустим, что имеется всего четыре вида продуктов: П1, II 2, П3, П4; стоимость единицы каждого продукта равна соответственно с1, с2, с3, c 4 Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков — не менее Ь\ единиц; углеводов — не менее Ь 2 единиц; жиров — не менее Ь 3 единиц. Для продуктов П1, П2, П3, П4 содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано в таблице 7:1 , где aij ( i = l , 2, 3, 4; j = 1, 2, 3) — какие-то определенные числа; первый индекс указывает номер продукта, второй — номер элемента (бел­ки, углеводы, жиры)').

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

Составим математическую модель (в данном случае это очень просто). Обозначим х1, х2 , х3, х4 количества про­дуктов П1, П2, П3, П4, входя­щих в рацион. Показатель эффективности, который тре­буется минимизировать,— стоимость рациона (обозна­чим ее L ); она линейно зависит от элементов решения

х1,х2,х3, х4

L = с1х1 + с2х2 + с3х3 + с4х4 или, короче,

Итак, вид целевой функции известен и она линей­на. Запишем теперь в виде формул ограничительные условия по белкам, углеводам и жирам. Учитывая, что в одной единице продукта П1 содержится а11 единиц белка, в х1 единицах — а1х1, единиц белка, в х2 еди­ницах продукта С2 содержится а21х2 единиц белка и т. д., получим три неравенства:

« iA + « iA + « sA + ««X» > К « w * i + «»А + « jA + а а х А > b,.

Эти линейные неравенства представляют собой ог­раничения, накладываемые на элементы решения х1 x 2 x 3 x 4.

Таким образом, поставленная задача сводится к следующей: найти такие неотрицательные значения пе­ременных х1 , х2 , х3, х4 , чтобы они удовлетворяли огра­ничениям — неравенствам (7.3) и одновременно обра­щали в минимум линейную функцию этих переменных;

Перед нами — типичная задача линейного програм­мирования. Не останавливаясь покуда на способах ее решения, приведем еще три примера аналогичных задач.

2. Задача о планировании производства. Предприятие производит изделия трех ви­дан: U 1, U 2, U 3. По каж­дому виду изделия предприя­тию спущен план, по кото­рому оно обязано выпустить м« менее Ь1единиц изделия U 1, не менее Ь2 единиц изделия U 2 и не менее b 2, единиц изделия U 3. План может быть не перевыполнен, но в определенных границах; условия спроса ограничивают количества произведенных единиц каждого типа: не более соответственно B 1, B 2, B 3 единиц. На изготовле­ние изделий идет какое-то сырье; всего имеется четы­ре вида сырья: S 1 S 2 S 3 S 4, причем запасы ограничены числами Y 1 Y 2 , Y 3 , Y 4 единиц каждого вида сырья. Теперь надо указать, какое количество сырья каждого вида идет на изготовление каждого вида изделий. Обозначим au количество единиц сырья вида s , ( i = 1, 2, 3, 4), потребное на изготовление одной едини­цы изделия U , ( i =1, 2, 3). Первый индекс у числа а„ — вид изделия, второй — вид сырья. Значения a ti г ведены в таблицу (матрицу)

При реализации одно изделие U 1 приносит пред­приятию прибыль c 1,U 2 — прибыль с 2 , U 3 — прибыль c 3. Требуется так спланировать производство (сколько каких изделий производить), чтобы план был выпол­нен или перевыполнен (но при отсутствии «затовари­вания»), а суммарная прибыль обращалась в максимум Запишем задачу в форме задачи линейного програм­мирования. Элементами решения будут х1, х 2 , хn — ко­личества единиц изделий U 1, U 2, U 3, которые мы про­изведем. Обязательность выполнения планового зада­ния запишется в виде трех ограничений-неравенств:

Отсутствие излишней продукции (затоваривания) даст нам еще три ограничения-неравенства:

Кроме того, нам должно хватить сырья. Соответст­венно четырем видам сырья будем иметь четыре ограничения-неравенства:

Прибыль, приносимая планом (х1, х2, х3), будет равна

Таким образом, мы снова получили задачу линей­ного программирования: найти (подобрать) такие не­отрицательные значения переменных x 1 , x 2, x 3, чтобы они удовлетворяли неравенствам-ограничениям (7.4), (7.5), (7.6) и, вместе с тем, обращали в максимум ли­нейную функцию этих переменных:

Задача очень похожа на предыдущую, разница в том, что неравенств-ограничений здесь больше и вме­сто «минимума» стоит «максимум» (а мы уже знаем, что это несущественно).

В следующей задаче мы уже встретимся с другого вида ограничениями.

3. Задача о загруаке оборудования. Ткацкая фаб­рика располагает двумя видами ставков, из них N1 станков типа 1 иN2 станков типа 2. Станки могут про­изводить три вида тканей: T 1, T 2, T 3 , но с разной про­изводительностью. Данные a ( J производительности станков даны в таблице 7.3 (первый индекс — тип станка, второй — вид ткани).

Каждый метр ткани вида Ti приносит фабрике до­ход c 1, вида Т2 — доход с2, Т3 — доход с3.

Фабрике предписан план, согласно которому она должна производить в месяц не менее b 1 метров тка­ни T 1, Ь2 метров ткани Т2, Ь3 метров ткани T 3 3 ;

коли­чество метров каждого метра ткани не должно превы­шать соответственно B 1, B 2, B 3 метров. Кроме того, все без исключения станин должны быть загружены. Требуется так распределить загрузку станков производством тканей Т1, Т2, Т3,чтобы суммарный месячный доход был максимален.

На первый (легкомысленный) взгляд поставленная адрес задача — родная сестра предыдущей. Рука так и тянется обозначить x lt x 2 , х n количества тканей T 1 t l ' i , Тз в плане н максимизировать суммарный доход c 1 x 1+ c 2 x 2+ c 3 x 3 . Но не торопитесь и спросите себя: а где же тут возможности оборудования? Поразмыслив, мы увидим, что в этой задаче элементы решения — не количества тканей каждого вида, а количества станков типов 1 н 2, занятых производством тканей ни ж дого вида. Здесь удобно обозначить элементы ре­шения буквами х с двумя индексами (первый — тип станка, второй — вид ткани). Всего будет шесть эле­ментов решения:

Здесь x 11 — количество станков типа 1, занятых изготовлением

ткани T 1, x 12 — количество станков типа 1, занятых изготовлением ткани Т2, н т. д.

Перед нами — еще одна задача линейного программирования. Запишем сначала условия-ограничения, на­ложенные на элементы решения хi .Прежде всего обес­печим выполнение плана. Это даст нам три неравенства - ограничения:

После этого ограничим перевыполнение плана; это даст нам еще три неравенства-ограничения:

Теперь запишем ограничения, связанные с нали­чием оборудования и его полной загрузкой. Суммар­ное количество станков типа 1, занятых изготовлени­ем всех тканей, должно быть равно Л N1; типа 2 — N 2 - Отсюда еще два условия — на этот раз равенства:

Теперь запишем суммарный доход от производства всех видов тканей. Суммарное количество метров тка­ни Т\, произведенное всеми станками, будет равно a 11 x 11+ a 21 x 21 и принесет доход c 1( a 11 x 11+ a 21 x 21). Рас­суждая аналогично, найдем суммарный доход фабри­ки за месяц при плане

или, гораздо короче,

Эту линейную функцию шести аргументов мы хо­тим обратить в максимум:

.

Перед нами — опять задача линейного программи­рования: найти такие неотрицательные значения пере­менных x 11 , x 12 , ..., x 23, которые, во-первых, удовлет­воряли бы ограничениям-неравенствам (7.10), (7.11), во-вторых — ограничениям-равенствам (7.12) и, нако­нец, обращали бы в максимум линейную функцию этих переменных (7.13). В этой задаче линейного про­граммирования шесть ограничений-неравенств и два ограничения-равенства.

Не нашли, что искали? Воспользуйтесь поиском по сайту: