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

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

главное внимание обратим на их принципиальные основы.

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

W=W (a, x). (7.1)

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

x = (x₁, x₂, …, x_n).

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

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

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

 

 

¹) Слово «программирование» заимствовано из зарубежной литературы и попросту означает «планирование».

 

 

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

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

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

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

1. Задача о пищевом рационе. Ферма производит откорм скота с коммерческой целью. Для простоты допустим, что имеется всего четыре вида продуктов:

П₁, П₂, П₃, П₄; стоимость единицы каждого продукта равна соответственно с₁, с₂, с₃,, с₄. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков — не менее b₁ единиц; углеводов — не менее b₂ единиц; жиров — не менее b₃ единиц. Для продуктов П₁, П₂, П₃, П₄ содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано в таблице 7.1, где a_ij (i==1, 2, 3, 4; j=1, 2, 3) — какие-то определенные числа; первый индекс указывает номер продукта, второй — номер элемента (белки, углеводы, жиры)¹).

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

 

Таблица 7.1

Продукт	Элементы
белки	углеводы	Жиры
П1 П2 П3 П4	а11 а21 а31 а41	а12 а22 а32 а42	а13 а23 а33 а43

 

Составим математическую модель (в данном случае это очень просто). Обозначим х₁, х₂, x₃, x₄ количества продуктов П₁, П₂, П₃, П₄, входящих в рацион. Показатель эффективности, который требуется минимизировать,— стоимость рациона (обозначим ее L); она линейно зависит от элементов решения х₁, х₂, x₃,, x₄:

L = c₁x₁+c₂x₂+c₃x₃+c₄x₄,

или, короче,

L = (7.2)

 

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

 

(7.3)

Эти линейные неравенства представляют собой ограничения, накладываемые на элементы решения x₁, x₂, x₃, x₄,.

 

¹) Разумеется, мы могли бы для «оживления» материала задать как числа b₁, b₂, b₃,, так и числа а_ij вполне конкретными значениями, но это все равно не создало бы у читателя впечатления, что автор — специалист по откорму скота.

 

 

Таким образом, поставленная задача сводится к следующей: найти такие неотрицательные значения переменных х₁, x₂, x₃, x₄, чтобы они удовлетворяли ограничениям — неравенствам (7.3) и одновременно обращали в минимум линейную функцию этих переменных:

L ==

 

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

 

Таблица 7.2

Сырьё	Изделия
U1	U2	U3
s1 s2 s3 s4	а11 а12 а13 а14	а21 а22 а23 а24	а31 а32 а33 а34

 

2. Задача о планировании производства. Предприятие производит изделия трех видов: U₁, U₂, U₃. По каждому виду изделия предприятию спущен план, по которому оно обязано выпустить не менее b₁ единиц изделия

U₁, не менее b₂ единиц изделия U₂ и не менее b₃ единиц изделия U₃. План может быть перевыполнен, но в определенных границах; условия спроса ограничивают количества произведенных единиц каждого типа: не более соответственно единиц. На изготовление изделий идет какое-то сырье; всего имеется четыре вида сырья: s₁, s₂, s₃, s₄, причем запасы ограничены числами единиц каждого вида сырья. Теперь надо указать, какое количество сырья каждого вида идет на изготовление каждого вида изделий. Обозначим a_ij количество единиц сырья вида s_i (j = l, 2, 3, 4), потребное на изготовление одной единицы изделия U_j (j = 1, 2, 3). Первый индекс у числа a_ij — вид изделия, второй — вид сырья. Значения a_ij сведены в таблицу (матрицу) — см. таблицу 7.2.

При реализации одно изделие U₁ приносит предприятию прибыль c₁, U₂ — прибыль c₂, U₃ — прибыль c₃. Требуется так спланировать производство (сколько каких изделий производить), чтобы план был выполнен или перевыполнен (но при отсутствии «затоваривания»), а суммарная прибыль обращалась в максимум.

Запишем задачу в форме задачи линейного программирования. Элементами решения будут x₁, x₂, x₃, — количества единиц изделий U₁, U₂, U₃, которые мы произведем. Обязательность выполнения планового задания запишется в виде трех ограничений-неравенств:

 

x₁. b₁, x₂ b₂, x₃ b₃ (7.4)

 

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

(7.5)

 

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

 

 

(7.6)

 

Прибыль, приносимаяпланом (x₁, x₂, x₃), будет равна

 

L = c₁x₁ + c₂x₂ + c₃x₃. (7.7)

 

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

 

L = c₁x₁ + c₂x₂ + c₃x₃ =>max. (7.8)

 

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

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

3. Задача о загрузке оборудования. Ткацкая фабрика располагает двумя видами станков, из них N₁ станков типа 1 и N₂ станков типа 2. Станки могут производить три вида тканей: Т₁, Т₂, Т₃, но с разной производительностью. Данные я„ производительности станков даны в таблице 7.3 (первый индекс — тип станка, второй — вид ткани).

Каждый метр ткани вида Т₁ приносит фабрике доход с₁, вида Т₂ – доход с₂, Т₃ – доход с₃.

Фабрике предписан план, согласно которому она должна производить в месяц не менее b₁ метров ткани Т₁, b₂ метров ткани Т₂, b₃ метров ткани Т₃; количество метров каждого вида ткани не должно превышать соответственно метров. Кроме того, все без исключения станки должны быть загружены. Требуется так распределить загрузку станков производством тканей Т₁, Т₂, Т₃, чтобы суммарный месячный доход был максимален.

 

Таблица 7.3

Тип станка	Вид ткани
Т1	Т2	Т3
	а11 а21	а12 а22	а13 а23

 

На первый (легкомысленный) взгляд поставленная здесь задача — родная сестра предыдущей. Рука так и тянется обозначить x₁, х₂, х₃ количества тканей Т₁, Т₂, Т₃ в плане и максимизировать суммарный доход с₁ х₁ + c₂x₂ + c₃x₃. Но не торопитесь и спросите себя:

а где же тут возможности оборудования? Поразмыслив, мы увидим, что в этой задаче элементы решения — не количества тканей каждого вида, а количества станков типов 1 и 2, занятых производством тканей каждого вида. Здесь удобно обозначить элементы решения буквами х с двумя индексами (первый — тип станка, второй — вид ткани). Всего будет шесть элементов решения:

 

(7.9)

 

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

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

 

(7.10)

 

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

 

(7.11)

 

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

 

(7.12)

 

Теперь запишем суммарный доход от производства всех видов тканей. Суммарное количество метров ткани T₁, произведенное всеми станками, будет равно a₁₁x₁₁ + a₂₁x₂₁. и принесет доход с₁ (а₁₁ х₁₁ + а₂₁ х₂₁). Рассуждая аналогично, найдем суммарный доход фабрики за месяц при плане (7.9):

 

L = c₁ (a₁₁x₁₁ + a₂₁x₂₁) + c₂ (a₁₂x₁₂ + a₂₂x₂₂) + c₃ (a₁₃x₁₃ + a₂₃x₂₃),

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

 

 

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

L => max.

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

4. Задача о снабжении сырьем. Имеются три промышленных предприятия: П₁, П₂, П₃, требующих снабжения определенным видом сырья. Потребности в сырье каждого предприятия равны соответственно а₁, а₂, а₃ единиц. Имеются пять сырьевых баз, расположенных от предприятий па каких-то расстояниях и связанных с ними путями сообщения с разными тарифами. Единица сырья, получаемая предприятием П _i с базы Б _j обходится предприятию в c_ij рублей (первый индекс — номер предприятия, второй — номер базы, см. таблицу 7.4).

Таблица 7.4

Предприятие	База
Б1	Б2	Б3	Б4	Б5
П1 П2 П3	с11 с21 с31	с12 с22 с32	с13 с23 с33	с14 с24 с34	с15 с25 с35

 

Возможности снабжения сырьем с каждой базы ограничены ее производственной мощностью: базы Б₁, Б₂, Б₃, Б₄, могут дать не более b₁, b₂, b₃, b₄, b₅ единиц сырья. Требуется составить такой план снабжения предприятий сырьем (с какой базы, куда и какое количество сырья везти), чтобы потребности предприятий были обеспечены при минимальных расходах на сырье.

Опять поставим задачу линейного программирования. Обозначим х_ij количество сырья, получаемое i -м предприятием с j -и базы. Всего план будет состоять из 15 элементов решения:

 

(7.14)

 

Введем ограничения по потребностям. Они состоят в том, что каждое предприятие получит нужное ему количество сырья (ровно столько, сколько ему требуется):

 

(7.15)

 

Далее напишем ограничения-неравенства, вытекающие из производственных мощностей баз:

 

(7.16)

 

Наконец, запишем суммарные расходы на сырье, которые мы хотим минимизировать. С учетом данных табл. 7.4 получим (пользуясь знаком двойной суммы):

 

L = (7.17)

 

Опять перед нами задача линейного программирования: найти такие неотрицательные значения переменных x_ij которые удовлетворяли бы ограничениям-равенствам (7.15), ограничениям-неравенствам (7.16) и обращали бы в минимум их линейную функцию (7.17).

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