Типовые задачи линейного программирования

К типовым (классическим) задачам ЛП относят следующие: задача о пищевом рационе, задача о загрузке оборудования, задача о снабжении сырьем, транспортная задача. Необходимо понять, что перечисленные задачи достаточно универсальны и образуют "оболочки", с помощью которых пользователь может решать свои конкретные задачи, формально не имеющие ничего общего с рационом, сырьем или с транспортом.

7.2.2.1. Задача "о пищевом рационе"

Пусть ферма откармливает скот, используя 4 вида кормов. Стоимость единицы каждого вида корма равна с₁,с₂,с₃ и с₄. Из этих кормов требуется составить рацион, содержащий: белков - не менее b₁ единиц, углеводов - не менее b₂единиц, жиров - не менее b₃ единиц. Для видов кормов содержание белков, углеводов и жиров известно и представлено в таблице 7.1. Требуется составить такой рацион, чтобы условия по белкам, углеводам и жирам были выполнены при минимальной стоимости рациона.

Таблица 7.1

Формальная постановка задачи. Обозначим: х₁, х₂, х₃ и х₄ - искомые количества видов кормов; L - это стоимость рациона. Ее формула для рассматриваемого примера:

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

или, короче -

₄

L= ∑(c_i·x_i); (7.8)

ⁱ⁼¹

Исходя из условия задачи, запишем систему неравенств:

a₁₁·x₁+a₂₁·x₂+a₃₁·x₃+ a₄₁·x₄≥b₁;

a₁₂·x₁+a₂₂·x₂+a₃₂·x₃+a₄₂·x₄≥b₂; (7.9)

a₁₃·x₁+a₂₃·x₂+a₃₃·x₃+a₄₃·x₄≥b_3.

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

₄

L= ∑(c_i·x_i)→ min. (7.10)

ⁱ⁼¹

В поставленной задаче критерий эффективности L, а искомыми элементами решения являются х₁,х₂,х₃ и х₄. Математическая модель представляет собой зависимость (7.10), дополненную системой ограничений (7.9).

7.2.2.2. Задача "о планировании производства"

Пусть предприятие производит 3 вида изделий, по каждому из которых спущен план, по которому выпуск изделий по видам не может быть менее, соответственно b₁,b₂ и b₃. На изготовление изделий идет 4 вида сырья, запасы которого составляют, соответственно, s₁,s₂,s₃ и s₄. Одно изделие каждого вида приносит прибыль (по видам изделий): с₁,с₂,с₃. Потребный расход сырья на каждый вид изделия представлен в таблице 7.2. Требуется так спланировать производство (сколько и каких изделий выпустить), чтобы план был выполнен, а суммарная прибыль была бы максимальной.

Таблица 7.2

Формальная постановка задачи. Элементами решения будут х₁,х₂,х₃ - количества единиц изделий каждого вида. Условие выполнения плана представим в виде системы неравенств-ограничений:

x₁≥b₁,x₂≥b₂, x₃ ≥b₃; (7.11)

Ограниченность сырья на складе представим в виде системы неравенств-ограничений:

a₁₁·x₁+a₂₁·x₂+a₃₁·x₃≤s₁;

a₁₂·x₁+a₂₂·x₂+a₃₂·x₃≤s₂;(7.12)

a₁₃·x₁+a₂₃·x₂+a₃₃·x₃≤s₃;

a₁₄·x₁+a₂₄·x₂+a₃₄·x₃≤s₄;

Суммарную прибыль L выразим формулой:

L=с₁·х₁+с₂·х₂+с₃·х₃.

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

₃

L=∑(c_i·x_i)→ max. (7.13)

ⁱ⁼¹

В поставленной задаче критерий эффективности L, а искомыми элементами решения являются х₁,х₂,х₃. Математическая модель представляет собой выражение (7.13), дополненное системой ограничений (7.11) и (7.12).

7.2.2.3. Задача "о загрузке оборудования"

Пусть фабрика располагает двумя видами станков, соответственно n₁ и n₂ штук каждого вида. Станки могут производить 3 вида тканей с производительностью, указанной в таблице 7.3. Каждый метр ткани (по их видам) приносит доход, соответственно, c₁,c₂ и c₃. Фабрике предписан план, согласно которому она должна производить в месяц (по видам ткани) не менее b₁,b₂ и b₃ метров ткани. Для исключения затоваривания торговли объем выпуска тканей не должен превышать (по видам ткани) d₁,d₂ и d₃ метров. Кроме того, все без исключения станки должны быть загружены. Требуется так спланировать загрузку станков, чтобы суммарный месячный доход L был максимален.

Таблица 7.3

Формальная постановка задачи. Элементами решения являются не количество ткани по видам, а количество станков, занятых производством той или иной ткани. Так как видов станков 2, а видов ткани 3, то удобнее элементы решения обозначить двумя индексами (первый - вид станка, второй - вид ткани): х₁₁,х₁₂,х₁₃,x₂₁,х₂₂,х₂₃.

Ограничения по обеспечению плана имеют вид:

a₁₁·x₁₁+a₂₁·x₂₁≥b₁;

a₁₂·x₁₂+a₂₂·x₂₂≥b₂; (7.14)

a₁₃·x₁₃+a₂₃·x₂₃≥b_3.

Ограничения по исключению затоваривания имеют вид:

a₁₁·x₁₁+a₂₁·x₂₁≥d₁;

a₁₂·x₁₂+a₂₂·x₂₂≥d₂; (7.15)

a₁₃·x₁₃+a₂₃·x₂₃ ≥ d_3.

Ограничения, связанные с наличием станков и необходимостью их полной загрузки имеют вид:

х₁₁+х₁₂+х₁₃=n₁;

x₂₁+x₂₂+x₂₃=n₂. (7.16)

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

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

или короче:

_{2 3}

L=∑(c_j) ·∑(a_ij·x_ij). (7.17)

^{j=1 i=1}

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

_{2 3}

L=∑(c_j) ·∑(a_ij·x_ij)→ max. (7.18)

^{j=1 i=1}

Математическая модель представляет собой (7.18) и систему ограничений (7.14, 7.15, 7.16).

7.2.2.4. Задача "о поставке сырья"

Пусть имеются 3 предприятия, требующих, соответственно, а₁,а₂ и а₃ единиц сырья. Имеются 5 складов сырья, обеспечивающих стоимости поставок сырья, указанные в таблице 7.4. Запас сырья на базах равен, соответственно, b₁,b₂,b₃,b₄ и b₅ единиц сырья. Требуется составить такой план снабжения предприятий сырьем (с какой базы, куда и сколько сырья везти), чтобы потребности предприятий были обеспечены при минимальных расходах на сырье.

Таблица 7.4

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

x₁₁,x₁₂,x₁₃,x₁₄,x₁₅,x₂₁,x₂₂,x₂₃,x₂₄,x₂₅, x₃₁,x₃₂,x₃₃,x₃₄,x₃₅.

Ограничения-равенства по потребностям:

x₁₁+x₁₂+x₁₃+x₁₄+x₁₅=a₁;

x₂₁+x₂₂+x₂₃+x₂₄+x₂₅=a₂; (7.19)

x₃₁+x₃₂+x₃₃+x₃₄ +x₃₅=a₃.

Ограничения-неравенства, вытекающие из возможностей складов:

x₁₁+x₂₁+x₃₁≤b₁;

x₁₂+x₂₂+x₃₂≤b₂;

x₁₃ +x₂₃+x₃₃≤b₃; (7.20)

x₁₄ +x₂₄+x₃₄≤b₄;

x₁₅+x₂₅+x₃₅≤b₅.

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

_{3 5}

L=∑ ∑(с_ij·x_ij)→ min. (7.21)

^{i=1 j=1}

Математическая модель представляет собой (7.21) и систему ограничений (7.19, 7.20), а поставленная задача сводится к нахождению неотрицательных значений элементов решения x_ij, при условии, что они удовлетворяют системе ограничений.

7.2.2.4. Транспортная задача (задача "о перевозках")

Пусть имеются m пунктов отправления, в которых сосредоточены грузы в количестве, соответственно, a₁,a₂,...,a_m единиц. Кроме того, имеются n пунктов назначения, требующих, соответственно, b₁,b₂,...,b_n единиц груза. Сумма всех заявок равна сумме всех запасов. Известны стоимости c_ij перевозки единицы груза от каждого пункта отправления, до каждого пункта назначения. Требуется составить такой план перевозок (откуда, куда и сколько единиц), чтобы все заявки были выполнены, а общая стоимость всех перевозок минимальна.

Формальная постановка задачи. Обозначим через x_ij количество единиц груза, отправляемого из i-го пункта отправления в j-й пункт назначения. Совокупность чисел x_ij будем называть "планом перевозок", а сами величины x_ij - "перевозками". Эти неотрицательные переменные должны удовлетворять следующим условиям:

1. Суммарное количество груза, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу груза в данном пункте. Это дает m ограничений-равенств:

x₁₁+x₁₂+ ... +x_1n=a₁;

x₂₁+x₂₂+ ... +x_2n=a₂; (7.22)

...

x_m1+x_m2+ ... +x_mn=a_m.

2. Суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно заявке, поданной данным пунктом. Это дает нам n ограничений-равенств:

x₁₁+x₂₁+ ... +x_m1=b₁;

x₁₂+x₂₂+ ... +x_m2=b₂; (7.23)

...

x_1n+x_2n+ ... +x_mn=b_n.

3. Суммарная стоимость всех перевозок, то есть сумма величин x_ij, умноженных на соответствующие стоимости c_ij, должна быть минимальной:

_{m n}

L=∑ ∑(с_ij·x_ij)→ min. (7.24)

^{i=1 j=1}

Знак двойной суммы означает, что суммирование производится по всем комбинациям индексов i и j, т.е. по всем парам пунктов назначения и пунктов отправления.

Математическая модель представляет собой (7.24) и систему ограничений (7.22, 7.23), а поставленная задача сводится к нахождению неотрицательных значений элементов решения x_ij, при условии, что они удовлетворяют системе ограничений.

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