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

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

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

Выше мы уже упоминали о самых простых задачах, где выбор показателя эффективности (целевой функции) 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

Составим математическую модель (в данном случае это очень просто). Обозначим х₁, х₂, 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

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

На первый (легкомысленный) взгляд поставленная здесь задача — родная сестра предыдущей. Рука так и тянется обозначить 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

Возможности снабжения сырьем с каждой базы ограничены ее производственной мощностью: базы Б₁, Б₂, Б₃, Б₄, могут дать не более 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).

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