Типичные злп и их математические модели

1. Задача об использовании сырья. Некоторое производство выпускает n видов продукции с использованием m видов сырья. Известны: a_ij - количество i -го вида сырья, затрачиваемого на выпуск единицы продукции j -го вида; b_i - запасы i -го вида сырья; c_j - прибыль от реализации единицы продукции j -го вида. Составить план производства продукции (то есть определить, в каком количестве выпустить каждого вида продукции), обеспечивающий максимальную прибыль.

Составим математическую модель задачи.

Обозначим через x_j количество выпускаемой продукции j -го вида; x ₁ - количество выпускаемой продукции 1-го вида, x ₂ - количество выпускаемой продукции 2-го вида и т.д. Тогда c ₁ x ₁ - прибыль от реализации всей произведённой продукции 1-го вида, и, вообще, c_jx_j - прибыль от реализации всей произведённой продукции j -го вида, c ₁ x ₁+ c ₂ x ₂+…+ c_nx_n - общая прибыль от реализации всей произведённой продукции. Это - целевая функция, максимум которой мы должны получить: c ₁ x ₁+ c ₂ x ₂+…+ c_nx_n ®max.

Количество сырья первого вида, затрачиваемого на выпуск единицы продукции первого вида, равно a ₁₁, x ₁ - количество выпускаемой продукции первого вида. Поэтому всего сырья первого вида на выпуск всей продукции первого вида уйдёт в количестве a ₁₁ x ₁. Аналогично, a ₁₂ x ₂ - общее количество сырья первого вида, которое уйдёт на впуск всей продукции второго вида и т.д. Всего же количество сырья первого вида, которое уйдёт на производство всех видов продукции, равно a ₁₁ x ₁+ a ₁₂ x ₂+…+ a _{1 n}x_n, и оно не может превосходить общие запасы сырья первого вида, то есть b ₁: a ₁₁ x ₁+ a ₁₂ x ₂+…+ a _{1 n}x_n ≤ b ₁. Аналогично рассуждая в общем случае относительно i -го вида сырья, получим неравенство a_{i 1} x ₁+ a_{i 2} x ₂+…+ a_inx_n ≤ b_i (i =1, 2, …, m). Наконец, количество выпускаемой продукции j -го вида не может быть отрицательным: x_j ≥0 (j =1, 2, …, n). И мы приходим к следующей математической модели задачи:

c ₁ x ₁+ c ₂ x ₂+…+ c_nx_n ®max

(1.4)

2. Задача о составлении рациона (задача о диете). Сельхозпредприятие занимается откормом скота. В откормочный рацион входит n видов продуктов, которые содержат m видов питательных веществ. Известны: a_ij - количество i -го вида питательного вещества в единице продукта j -го вида; b_i - необходимое количество питательного вещества i -го вида, содержащегося в рационе; c_j - стоимость единицы продукта j -го вида. Составить рацион (то есть определить, в каком количестве включить в рацион продукта каждого вида), при котором достигается минимальная стоимость рациона.

Составим математическую модель задачи.

Обозначим через x_j количество продуктов j -го вида, включаемого в рацион. Тогда c ₁ x ₁+ c ₂ x ₂+…+ c_nx_n - общая стоимость рациона, которая должна быть минимальной: c ₁ x ₁+ c ₂ x ₂+…+ c_nx_n ®min.

Количество питательного вещества первого вида, входящего в единицу продукта первого вида, равно a ₁₁, x ₁ - количество продукта первого вида, входящего в рацион. Поэтому всего питательного вещества первого вида, входящего в рацион с продуктами первого вида, составит a ₁₁ x ₁. Аналогично, a ₁₂ x ₂ - общее количество питательного вещества второго вида, входящего в рацион с продуктами второго вида, и т.д. Всего же количество питательного вещества первого вида, которое поступит в рацион со всеми видами продуктов, равно a ₁₁ x ₁+ a ₁₂ x ₂+…+ a _{1 n}x_n, и оно не может быть меньше положенного количества, то есть b ₁: a ₁₁ x ₁+ a ₁₂ x ₂+…+ a _{1 n}x_n ≥ b ₁. Аналогично рассуждая в общем случае относительно i -го вида питательных веществ, получим неравенство a_{i 1} x ₁+ a_{i 2} x ₂+…+ a_inx_n ≥ b_i (i =1, 2, …, m). Наконец, количество продуктов, входящих в рацион, не может быть отрицательным: x_j ≥0 (j =1, 2, …, n). И мы приходим к следующей математической модели задачи:

c ₁ x ₁+ c ₂ x ₂+…+ c_nx_n ®min

(1.5)

Упражнения.

1) Какие из следующих задач являются задачами линейного программирования, какие нет:

а) -2 x ₁+ x ₂+8 x ₃-2 x ₄®min б) -2 x ₁+ +8 x ₃-2 x ₄®min

в) -3 x ₁-2 x ₂+ x ₃®min(max) г) 4 x ₁+ x ₂®min(max)

д) -3 x ₁-2 x ₂+ x ₃®min(max) е) 4 x ₁+ x ₂®min(max)

ж) -3 x ₁+ x ₂+2 x ₃®max(min) з) -3 x ₁+2 x ₂+2 x ₃®max(min)

Решение. а) задача является задачей линейного программирования, так как и целевая функция -2 x ₁+ x ₂+8 x ₃-2 x ₄, и функции и в ограничениях линейные.

б) Задача не является задачей линейного программирования, так как целевая функция не является линейной - переменная x ₂ входит в функцию в квадрате: .

Составить математические модели следующих задач:

2) При производстве двух видов продукции используется три вида сырья. Составить план выпуска продукции, обеспечивающий максимум прибыли. Исходные данные приводятся в таблицах:

а)	Запасы сырья	Расход сырья на единицу продукции	б)	Запасы сырья	Расход сырья на единицу продукции
	№1	№2		№1	№2
	Прибыль				Прибыль

3) В рационе животных используется два вида кормов. Животные должны получать три вида питательных веществ. Составить рацион наименьшей стоимости. Исходные данные приводятся в таблицах:

а)	Необходимое количество пит. вещ-тв	Содержание пит. вещ-ва в ед-це корма	б)	Необходимое количество пит. вещ-тв	Содержание пит. вещ-ва в ед-це корма
	№1	№2		№1	№2
	Стоимость ед-цы корма				Стоимость ед-цы корма