Тема 2. Задача составления рациона (задача о смесях)

Из 4 видов кормов необходимо составить рацион, в состав которого должно входить не менее: 12 ед. вещества V₁, 6 ед. вещества V₂ и 9 ед. вещества V₃. Количество единиц вещества, содержащегося в 1 кг корма каждого вида, указано в соответствующей таблице. В ней же приведена цена 1 кг корма каждого вида. Другие исходные данные сведены в таблицу.

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

таблица

Питательные вещества	Количество питательных веществ в единице корма
	К1	К2
V1 V2 V3	3 1 3	2 2 1
Стоимость единицы корма	2	3

Обозначим: x₁- количество корма К₁;

x₂- количество корма К₂, тогда

Стоимость всего корма К₁ → 2x₁(руб.).

Стоимость всего корма К₂ → 3x₂(руб.).

Стоимость всего корма f= 2x₁+ 3x₂ (руб.).

Так как нужно обеспечить заданную питательность смеси, необходимо выполнение следующих неравенств:

Задача может быть представлена в виде модели:

Рассмотрим задачу в общем виде.

• Имеется n видов кормов.

• В каждой порции смеси содержится m питательных веществ в количествах не менее b_i (i=1,2,…m).

• Известно: a_ij (i=1,2,…m, j=1,2,…n) – количество i-го питательного вещества, содержащееся в единице корма j-го вида.

• с_j (j=1,2,…n) – стоимость единицы корма j-го вида.

Требуется: смешать имеющиеся корма так, чтобы обеспечить заданную питательность при минимальных затратах на корма.

Обозначим: x_j (j=1,2,…n) - количество корма j-го вида.

Задача в общем виде может быть описана моделью:

Тема 3. Общая задача линейного программирования

Общая задача линейного программирования имеет вид:

Линейная функция называется целевой функцией задачи. Все остальное, за исключением условий неотрицательности переменных x_j, - ограничения.

Тема 4. Матричная форма записи задачи линейного программирования

• Обозначим: C(c₁,c₂,…c_n) – матрица-строка коэффициентов при неизвестных в целевой функции f;

• Матрица системы ограничений;

• Матрица-столбец свободных членов ограничений;

• Матрица-столбец неизвестных.

Задача об использовании ресурсов имеет вид:

Задача о смесях имеет вид;

Существуют задачи:

Перечисленные задачи – это частные виды задач линейного программирования.

Тема 5. Геометрический метод решения задач линейного программирования

Геометрический метод решения задач ЛП применим к задачам с двумя переменными.

Пусть дана задача ЛП в виде:

Каждое ограничение геометрически определяет полуплоскость, следовательно, множество допустимых решений Х представляет собой пересечение конечного числа полуплоскостей, т.е. если Х (не пустое множество), то Х есть либо многоугольник, либо многоугольное множество.

Рассмотрим возможные варианты множества X.

а)
В ы в о д: множество .	Рис.1. Множество Х допустимых решений

б)
В ы в о д: Множество - многоугольник ABDE.	Рис.2. Множество допустимых решений

в)
В ы в о д: Множество Х - многоугольное множество.	Рис.3. Множество допустимых решений

Рассмотрим целевую функцию f(x)=c₁x₁+c₂x₂. Линии уровня c₁x₁+c₂x₂=α (α R) образуют семейство параллельных прямых. Вектор является вектором нормали к этим прямым и показывает направление возрастания целевой функции. Вектор будет показывать направление убывания целевой функции.

Теорема Целевая функция задачи ЛП достигает своего экстремального значения в угловой точке многогранника решений.

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

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