Задача прикрепления потребителей к поставщикам (транспортная задача)

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

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

Продукт	Элементы
Белки	Углеводы	Жиры
П₁	a₁₁	a₁₂	a₁₃
П₂	a₂₁	a₂₂	a₂₃
П₃	a₃₁	a₃₂	a₃₃
П₄	a₄₁	a₄₂	a₄₃

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

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

L= с₁х₁+ с₂ х₂+ с₃ х₃+ с₄ х₄,

Или, короче,

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

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

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

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

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

Сырье	Изделия
U₁	U₂	U₃
s ₁	a₁₁	a₂₁	a₃₁
s ₂	a₁₂	a₂₂	a₃₂
s ₃	a₁₃	a₂₃	a₃₃
s ₄	a₁₄	a₂₄	a₃₄

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

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

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

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

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

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

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

Задача прикрепления потребителей к поставщикам (транспортная задача)

Рассмотрим проблему организации перевозки некоторого условного продукта между пунктами его производства, количество которых равно m, и n пунктами потребления. Каждый i –й пункт производства (i = 1,…, m) характеризуется запасом продукта а_i ≥0, а каждый j- ый пункт потребления (j = 1,…, n) – потребностью в продукте b_j ≥0. Сеть коммуникаций, соединяющая систему рассматриваемых пунктов, моделируется с помощью матрицы С размерности m×n, элементы которой (с_ij) представляют собой нормы затрат на перевозку единицы груза из пункта производства A_i в пункт потребления B_j. То есть задана таблица (матрица):

b_j а_i	B₁	B₂	…	B_n
A₁		c₁₁		c₁₂	…	c_1n	a₁

A₂		c₂₁		c₂₂	…	c_2n	a₂

…	…	…	…	…	…
A_m		c_m1		c_m2	…	c_mn	a_m

	b₁	b₂	…	b_n

Строки транспортной таблицы соответствуют пунктам производства А_i (в последней клетке каждой строки указан объем запаса продукта a_i), а столбцы – пунктам потребления В_j (последняя клетка каждого столбца содержит значение потребности b_j). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i –го пункта производства в j –ый пункт потребления.

План перевозки груза в данной транспортной сети представляется в виде массива элементов размерности m×n:

Ограничения на возможные значения х_ij имеют вид:

1) ограничения на удовлетворение потребностей во всех пунктах потребления:

(*)

2) ограничения на возможности вывоза запасов из всех пунктов производства:

(**)

3) условия неотрицательности компонент вектора плана х:

Существенной характеристикой описываемой модели является соотношение параметров а_i и b_j. Если суммарный объем производства равен суммарному объему потребления, а именно,

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

Предположим, что затраты на перевозку прямо пропорциональны количеству перевозимого груза. Тогда суммарные затраты на перевозку в системе примут вид:

Тогда модель транспортной задачи имеет вид:

или в подробном виде:

Если привести условия транспортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (m+n) ×mn. Ранг матрицы задачи равен m+n-1, и ее невырожденный базисный план план должен содержать m+n-1 ненулевых компонент.