Задача о составлении оптимального рациона (на минимизацию)

Предположим, что нам необходимо составить оптимальный суточный рацион кормления на стойловый период для дойных коров. На 1 голову скота в сутки требуется не менее 16,1кг кормовых единиц и 1819г перевариваемого протеина. Рацион составляется из трёх видов кормов: комбикорма, сена, силоса. Содержание питательных веществ в единице каждого вида корма и себестоимость кормов приведены в таблице ниже.

Таблица 1. Содержание питательных веществ в 1 кг корма и себестоимость кормов

Согласно физиологическим особенностям животных в рационе должно содержаться не менее 31% концентрированных (комбикорм) и не более 26% грубых (сено) кормов от общей потребности в кормовых единицах.

Критерий оптимальности – минимум себестоимости рациона при выполнении условий по необходимому содержанию питательных веществ в рационе.

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

Целевая функция – общая стоимость суточного рациона кормления:

.

Составим систему ограничений:

1. условие по содержанию кормовых единиц в рационе:

;

2. условие по содержанию переваримого протеина в рационе:

;

3. условие по содержанию концентрированных кормовых единиц в рационе (не менее кг корм. ед.):

;

4. условие по содержанию грубых кормов (не более кг корм. ед.)

.

5. условие неотрицательности количества корма каждого вида:

.

Итак, общая система ограничений будет иметь вид:

Транспортная задача

Пусть имеется несколько поставщиков однородной продукции с некоторым запасом этой продукции и несколько потребителей этой продукции с известными потребностями. Задана сеть коммуникаций, связывающая каждого поставщика с каждым потребителем. Для каждой коммуникации известны затраты перевоза единицы продукции, т.е. известно какова цена перевоза единицы продукции от любого поставщика к любому потребителю.

Рис. 1

Если какой-либо коммуникации нет, то считаем, что она есть, но стоимость ее использования устанавливаем равной . Это автоматически сделает абсолютно невыгодным использование этой коммуникации и она будет исключена из плана перевозок.

Экономическая постановка транспортной задачи звучит следующим образом:

требуется составить план перевозок продукции от поставщиков к потребителям так, чтобы потребности потребителей были удовлетворены за счет вывоза запасов продукции со складов поставщиков. Цель – минимизация суммарных расходов на все перевозки.

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

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

Для примера, приведенного на рис. 1 суммарный запас составляет 190 ед., а потребность – 240 ед. Имеет место нехватка 50 ед. продукции на складах поставщика. Вводим фиктивного поставщика с запасом в 50 ед. Проводим от него фиктивные коммуникации с нулевыми стоимостями ко всем потребителям. Наша открытая транспортная задача в результате стала закрытой.

Рис. 2.

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

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

Далее будут рассмотрены только закрытые транспортные задачи.

Построим математическую модель транспортной задачи, как ЗЛП. Исходя из того, что план перевозок определяется указанием количества перевозимого груза по каждой коммуникации, обозначим через неизвестные – количество перевозимой продукции от поставщика номе к потребителю номер . Здесь параметр , где – число поставщиков и , где – число потребителей. Для примера на рис. 2 характерно и . Тогда неизвестных будет девять: . В общем случае число неизвестных составляет .

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

.

Значение затрат на перевозки должно быть минимальным!

В общем виде можно записать целевую функцию в виде

.

Здесь – элементы матрица стоимостей перевозок. Для примера эта матрица имеет вид:

.

Перейдем к формулировке ограничений. Как видно из экономической постановки, ограничения делятся на две группы:

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

2. условия полного удовлетворения потребностей каждого потребителя (число условий равно числу потребителей ).

Т.о. в ТЗ будет всего ограничений. Запишем ограничения первой группы. Они будут иметь структуру:

Вывоз продукции от поставщика = запасу

Для нашего примера будет характерно

Рис.3.

– вывоз продукции по всем поставщикам. Запас его равен 120 ед. Условие полного вывоза будет иметь вид: .

Аналогично выглядят ограничения по вывозу продукции для второго и третьего поставщиков:

, .

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

привоз продукции к потребителю = Потребности

Рис. 4.

Привоз продукции к первому потребителю составит: и этот привоз должен быть равен потребности, т.е. .

Аналогично для других потребителей:

, .

Окончательно, учитывая ограничения неотрицательности перевозимых объемов продукции , при и (для примера ), получаем математическую постановку ТЗ в виде ЗЛП:

,

В общем виде математическую постановку ТЗ можно записать так

,

Здесь – число поставщиков и потребителей; – стоимости перевозки единицы продукции от -го поставщика к -у потребителю; – запасы поставщиков; – потребности потребителей.