Задача использования ресурса и задача о составлении рациона питания

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Задача использования ресурса и задача о составлении рациона питания

Вступление

Метод элементарных систем уравнений прост как в ручном использовании, так и в машинном. Рассмотрены алгоритм и несколько примеров решения этих задач.

1. Постановка задач

1.1 Постановка задачи использования ресурса

Для изготовления нескольких видов продукции P₁, Р₂,..., Р_n используют m видов ресурсов S₁, S₂,..., S_т. Это могут быть различные материалы, электроэнергия, полуфабрикаты и т.п. Объем каждого вида ресурсов ограничен и известен (b₁,. b₂, …, b_m).

Известно также a_ij (i = 1, 2, …, m, j = 1, 2,..., n) - количество каждого i - го вида ресурса, расходуемого на производство единицы j - го вида продукции. Кроме того, известна прибыль, получаемая от реализации единицы каждого вида продукции (с₁, с₂,..., с_n),

Условия задачи можно представить в виде таблицы (табл. 2.1.1.).

Питательное	Объем	aij
вещество	ресурсов	P1	P2	…	Pn
S1	b1	a11	a12	…	a1n
S2	b2	a12 aij	a22	…	a2n
...	…	…	…	…	…
Sт	bm	am1	amІ	…	amn
Прибыль	c1	c2	…	cn

Пусть х_j (j = 1, 2, …, n.) - количество каждого вида продукции, которое необходимо произвести.

Для первого ресурса имеет место неравенство-ограничение

a₁₁ х_{1 +} a₁₂ х _{2 + … +} a_1n х_n >= b₁

Аналогичные неравенства будут и для остальных видов ресурсов.

Следует учитывать также, что все значения

х_j > 0, j = 1,2,..., n.

Общая прибыль, получаемая от реализации всей продукции, может быть представлена как функция

Z(Х) = c₁ х₁ + с₂х₂ +... + с_nх_n

Если необходимо эту функцию максимизировать, то математическая модель задачи использования ресурсов запишется в виде

Z(Х) = c₁ х₁ + с₂х₂ +... + с_nх_n max,

a₁₁ х_{1 +} a₁₂ х _{2 + … +} a_1n х_n <= b₁

a₂₁ х_{1 +} a₂₂ х _{2 + … +} a_2n х_n <= b₂

………………………………………

a_m1 х_{1 +} a_mІ х _{2 + … +} a_mn х_n <= b_m

х_j >= 0, j = 1, 2, …, n.

В более компактной форме целевую функцию и систему ограничений можно записать, используя знак суммирования,

Z(Х)= (2.1.1.)

, (2.1.2.)

i=1, 2, …, m.

1.2 Постановка задачи составления рациона питания

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

Каждый вид корма содержит разную комбинацию этих веществ. Известна цена единицы веса каждого корма.

Пусть имеются n различных кормов (продуктов) P₁, Р₂,..., Р_n и перечень из т необходимых питательных веществ S₁, S₂,..., S_т. Обозначим через a_ij содержание (в весовых единицах) i - го питательного вещества в единице j - го корма, а через b_i - минимальную суточную потребность животного в i - ом питательном веществе. Через х_j обозначим количество каждого вида корма в ежедневном рационе. Очевидно, что х_j >= 0.

Условия задачи можно представить в виде таблицы (табл.2.2.1.)

Питательное		Суточная
вещество	P1	P2	…	Pn	потребность
S1	a11	a12	…	a1n	b1
S2	a12 aij	a22	…	a2n	b2
...	…	…	…	…	…
Sт	am1	amІ	…	amn	bm
Стоимость 1 кг	c1	c2	…	cn	-
1 кг корма

Для первого вида питательного вещества неравенство-ограничение примет вид

a₁₁ х_{1 +} a₁₂ х _{2 + … +} a_1n (2.2.1.)

х_n >= b₁

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

Z(Х)=c₁ х₁ + с₂х₂ +... + с_nх_n (2.2.2.)

Если эту функцию необходимо минимизировать, то математическая модель задачи составления рациона питания имеет вид

Z(Х) = c₁ х₁ + с₂х₂ +... + с_nх_n min,

a₁₁ х_{1 +} a₁₂ х _{2 + … +} a_1n х_n >= b₁

a₂₁ х_{1 +} a₂₂ х _{2 + … +} a_2n х_n >= b₂

………………………………………

a_m1 х_{1 +} a_mІ х _{2 + … +} a_mn х_n >= b_m

х_j >= 0, j = 1, 2, …, n.

2. Алгоритм решения

1. Выявляем очередную элементарную систему уравнений.

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

3. Если в системе ограничений остаются еще не определенные неизвестные, то, используя значения неизвестных, определенных в п.2, определяем их величины.

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

5. Действия по п.1 - п.4 выполняются до тех пор, пока все элементарные системы уравнений не будут решены, а по результатам этих решений - не будут определены все величины целевой функции.

6. Выбираем максимальное значение целевой функции, определённые для неё неизвестные при решении задачи использования ресурсов и минимальное - при решении задачи о составлении рациона питания.

Задача использования ресурсов

Пример 1. Решить задачу использования ресурсов

Z(X) = 2x₁ + 4x₂ max,

- 2x₁ + 3x₂ <= 12,

x₁ + x₂ <= 9,

3x₁ - 2x₂ <= 12.

x₁ >= 0, x₂ >= 0.

В системе ограничений выявим все возможные элементарные системы уравнений (выделены жирным шрифтом)

- 2x₁ + 3x₂ <= 12,

x₁ + x₂ <= 9,

3x₁ - 2x₂ <= 12.

- 2x₁ + 3x₂ <= 12,

x₁ + x₂ <= 9,

3x₁ - 2x₂ <= 12.

- 2x₁ + 3x₂ <= 12,

x₁ + x₂ <= 9,

3x₁ - 2x₂ <= 12.

Решим каждое из выделенных элементарных систем уравнений.

(Порядок их решения элементарен. Поэтому он не приводится, а приводятся лишь полученные результаты)

- 2x₁ + 3x₂ = 12,

x₁ + x₂ = 9.

X₁= (3, 6).

Z₁(X₁) = 2 · 3 + 4 · 6 = 30.

- 2x₁ + 3x₂ = 12,

3x₁ - 2x₂ = 12.

X₂= (12, 12).

Это решение не подходит, т.к. оно не соответствует второму уравнению системы ограничений.

x₁ + x₂ = 9,

3x₁ - 2x₂ = 12.

X₃ = (6, 3).

Z₃(X₃) = 2 · 6 + 4 · 3 = 24.

Решены все элементарные системы уравнений.

Условию задачи и ограничениям соответствует решение

X₁ = (3, 6).

Z₁(X₁) = 2 · 3 + 4 · 6 = 30.

Значит, оно и является оптимальным.

Пример 2. Решить задачу

Z(X) = 9x₁ + 5x₂ + 4x₃ + 3x₄ + 2x₅ max,

x₁ - 2x₂ + 2x₃ <= 6,

x₁ +2x₂ + x₃ + x₄ = 24,

2x₁ + x₂ - 4x₃ + x₅ = 30.

x_j >= 0, j = 1, 2, 3, 4, 5

Для удобства систему ограничений перепишем в виде

1x₁ - 2x₂ + 2x₃ + 0x₄ + 0x₅ <= 6,

1x₁ +2x₂ + 1x₃ + 1x₄ + 0x₅ = 24,

2x₁ +1x₂ - 4x₃ + 0x₄ + 1x₅ = 30.

x_j >= 0, j = 1, 2, 3, 4, 5

Система ограничений состоит из 30 элементарных систем уравнений, решение каждой из которых дает определенный результат. Но нет нужды приводить здесь решение всех 30-ти элементарных систем уравнений.

Достаточно привести лишь три из них, дающие оптимальное, неоптимальное и неприемлемое решения. Для этого выделим и решим следующие элементарные системы уравнений (выделены жирным шрифтом):

1x₁ - 2x₂ + 2x₃ + 0x₄ + 0x₅ <= 6,

1x₁ +2x₂ + 1x₃ + 1x₄ + 0x₅ = 24,

2x₁ +1x₂ - 4x₃ + 0x₄ + 1x₅ = 30.

Перед решением этой элементарной системы уравнений все значащие неизвестные второй и третьей строк, не вошедшие в нее, принимаем равными нулю, т.е. x₂ = 0, x₄ = 0, x₅ = 0.

Решив данную элементарную систему уравнений, получим значения

x₁ = 21, x₃ = 3.

Подставим эти значения в первое уравнение. Тогда

x₁ - 2x₂ + 2x₃ = 6

1 · 21 - 2 · 0 + 2 · 3 = 27

X₁ = (21, 0, 3, 0, 0).

Решение неприемлемо, т.к. оно не соответствует первому уравнению системы ограничений.

1x₁ - 2x₂ + 2x₃ + 0x₄ + 0x₅ <= 6,

1x₁ +2x₂ + 1x₃ + 1x₄ + 0x₅ = 24,

2x₁ +1x₂ - 4x₃ + 0x₄ + 1x₅ = 30.

Перед решением этой элементарной системы уравнений все значащие неизвестные первой и второй строк, не вошедшие в нее, принимаем равными нулю, т.е. x₂ = 0, x₃ = 0.

Решив данную элементарную систему уравнений, получим значения

x₁ = 6, x₄ = 18.

Подставим эти значения в третье уравнение. Тогда

2x₁ + x₂ - 4x₃ + x₅ = 30.

2 · 6 + 1 · 0 - 4 · 0 + x₅ = 30.

x₅ = 18.

X₂ = (6, 0, 0, 18, 18).

Решение приемлемо. Вычислим целевую функцию

Z₂(X₂) = 9x₁+5x₂+ 4x₃+3x₄+2x₅ = 9*6 + 5*0 + 4*0 + 3*18 + 2*18 = 144

1x₁ - 2x₂ + 2x₃ + 0x₄ + 0x₅ <= 6,

1x₁ +2x₂ + 1x₃ + 1x₄ + 0x₅ = 24,

2x₁ +1x₂ - 4x₃ + 0x₄ + 1x₅ = 30.

Перед решением этой элементарной системы уравнений все значащие неизвестные первой и второй строк, не вошедшие в нее, принимаем равными нулю, т.е. x₁ = 0, x₄ = 0.

Решив данную элементарную систему уравнений, получим значения x₂ = 7, x₃ = 10.

Подставим эти значения в третье уравнение. Тогда

2x₁ + x₂ - 4x₃ + x₅ = 30

2 · 0 +1 · 7 - 4 · 10 + x₅ = 30

-33 + x₅ = 30

x₅ = 63

X₃ = (0, 7, 10, 0, 63).

Решение приемлемо. Вычислим целевую функцию

Z₃(X₃) = 9x₁ + 5x₂ + 4x₃ + 3x₄ + 2x₅ = 9*0 + 5*7 + 4*10 + 3*0 + 2*63 = 201

Решение X₃ = (0, 7, 10, 0, 63) соответствует условиям задачи, значит оно и является оптимальным (с учетом и тех оставшихся, непоказанных решений).

Ниже приведены исходные данные и результаты решения некоторых задач использования ресурсов (табл. 3.1.).



3. Исходные данные и результаты решения некоторых задач об использовании ресурсов

Таблица 3.1

№ п/п	Исходные данные к задаче	Оптимальные решения
1	Z(X) = 10x1 + 12x2 max 3x1 + x2 <= 12 x1 + 2x2 <= 5	X* = (19/5, 3/5) Z(X) = 45,2
2	Z(X) = 3x1 + 2x2 + x3 - 8x4 max 3x1 + 3x2 + 4x3 - 7x4 = 10 2x1 + x2 + x3 - 2x4 = 2	X* = (0, 0, 6, 2) Z(X) = -10
3	Z(X) = -2x1 - 3x2 - 4x3 max x1 + x2 + x3 >= 3 x1 + 2x2 + 2x3 >= 4 2x1 + x2 + 2x3 >= 4	X* = (2, 1, 0) Z(X) = - 7
4	Z(X) = 5x1 + 3x2 + 4x3 - x4 max x1 + 3x2 + 2x3 + 2x4 = 3 2x1 + 2x2 + x3 + x4 = 3	X* = (1, 0, 1, 0) Z(X) = 9
5	Z(X) = 2x1 + 4x2 max -2x1 + 3x2 <= 12 x1 + x2 <= 9 3x1 - 2x2 <= 12	X* = (3, 6) Z(X) = 30
6	Z(X) = x1 + x2 + 5x3 + 3x4 max x1 + 2x2 + 3x3 + 3x4 = 9 x1 + x2 + x3 + 3x4 = 5	X* = (3, 0, 2, 0) Z(X) = 13
7	Z(X) = x1 - 3x2 + 5x3 + 2x4 max x1 + x2 + x3 = 15 2x1 + 2x3 + x4 = 8	X =(0, 37/3, 8/3, 0) Z(X) = - (23 + 2/3)
8	Z(X) = x1 - 4x2 - 2x3 + 3x4 max 3x1 + x2 + 8x3 + x4 = 35 x1 + x3 + x4 < = 6	X= (0,0,29/7,13/7) Z(X) = - (2 + 5/7)
9	Z(X) = 2x1 + 3x2 - 4x3 + 5x4+ 6x5 + 7x6 max x1 + 2x2 + 3x3 + x4 = 10 2x1 - x2 - 4x3 + x5 = 20 3x1 - 2x2 + 5x3 + x6 = 30	X = (0,5,0,0,25,40) Z(X) = 445
10	Z(X) = 9x1 + 5x2 + 4x3 + 3x4 + 2x5 max x1 - 2x2 + 2x3 <= 6 x1 + 2x2 + x3 + x4 = 24 2x1 + x2 - 4x3 + x5 = 30	X* = (0,7,10,0,63) Z(X) = 201

Задача о составлении рациона питания

Пример 1. Решить задачу

Z(X) = x₁ + x₂ + 5x₃ + 3x₄ min,

x₁ + 2x₂ + 3x₃ + 3x₄ = 9,

x₁ + x₂ + x₃ + 2x₄ = 5.

x_j >= 0, j = 1, 2, 3, 4.

В системе ограничений выявим все возможные элементарные системы уравнений (выделены жирным шрифтом):

x₁ + 2x₂ + 3x₃ + 3x₄ = 9,

x₁ + x₂ + x₃ + 2x₄ = 5.

x₁ + 2x₂ + 3x₃ + 3x₄ = 9,

x₁ + x₂ + x₃ + 2x₄ = 5.

x₁ + 2x₂ + 3x₃ + 3x₄ = 9,

x₁ + x₂ + x₃ + 2x₄ = 5.

x₁ + 2x₂ + 3x₃ + 3x₄ = 9,

x₁ + x₂ + x₃ + 2x₄ = 5.

x₁ + 2x₂ + 3x₃ + 3x₄ = 9,

x₁ + x₂ + x₃ + 2x₄ = 5.

Решим каждое из выделенных элементарных систем уравнений. (Порядок их решения элементарен. Поэтому он не приводится, а приводятся лишь полученные результаты)



x₁ + 2x₂ = 9,

x₁ + x₂ = 5,

X₁ = (1, 4, 0, 0)

Z₁(X₁) = 1 · 1 + 1 · 4 = 5

2x₂ + 3x₃ = 9,

x₂ + x₃ = 5,

X₂ = (0, - 4, 17/3, 0)

Это решение не подходит, т.к. в решении есть отрицательная переменная x₂ = -4.

3x₃ + 3x₄ = 9,

x₃ + 2x₄ = 5.

X₃ = (0, 0, 1, 2).

Z₃(X₃) = 5 · 1 + 3 · 2 = 11.

x₁ + 3x₃ = 9,

x₁ + x₃ = 5.

X₄ = (3, 0, 2, 0).

Z₄(X₄) = 1 · 3 + 5 · 2 = 13.

2x₂ + 3x₄ = 9,

x₂ + 2x₄ = 5.

X₅ = (0, 3, 0, 1).

Z₅(X₅) = 1 · 3 + 3 · 1 = 6.

x₁ + 3x₄ = 9,

x₁ + 2x₄ = 5.

X₆ = (-3, 0, 0, 4).

Это решение неприемлемо, т.к. в нем есть отрицательная переменная

x₁ = -3.

Условиям задачи соответствует решение

X₁ = (1, 4, 0, 0).

Z₁(X₁) = 1 · 1 + 1 · 4 = 5.

Значит, оно и является оптимальным.

Пример 2. Решить задачу

Z(X) = 2x₁ + 3x₂ - 4x₃ + 5x₄ + 6x₅+ 7x₆ min,

x₁ + 2x₂ + 3x₃ + x₄ = 10,

2x₁ - x₂ - 4x₃ + x₅ = 20,

3x₁ - 2x₂ + 5x₃ + x₆ = 30.

x_j >= 0, j = 1, 2, 3, 4, 5, 6

Для удобства выбора элементарных систем уравнений систему ограничений перепишем в виде

1x₁ + 2x₂ + 3x₃ + 1x₄ + 0x₅ + 0x₆ = 10,

2x₁ - 1x₂ - 4x₃ + 0x₄ + 1x₅ + 0x₆ = 20,

3x₁ - 2x₂ + 5x₃ + 0x₄ + 0x₅ + 1x₆ = 30.

x_j >= 0, j = 1, 2, 3, 4, 5, 6

Система ограничений состоит из 45 элементарных систем уравнений.

Но здесь достаточно привести лишь три из них - оптимальное, неоптимальное и неприемлемое. Для этого выделим и решим следующие элементарные системы уравнений (выделены жирным шрифтом):

1x₁ + 2x₂ + 3x₃ + 1x₄ + 0x₅ + 0x₆ = 10,

2x₁ - 1x₂ - 4x₃ + 0x₄ + 1x₅ + 0x₆ = 20,

3x₁ - 2x₂ + 5x₃ + 0x₄ + 0x₅ + 1x₆ = 30.



Перед решением этой элементарной системы уравнений все значащие неизвестные первой и второй строк, не вошедшие в нее, принимаются равными нулю, т.е. x₁ = 0, x₂ = 0, x₅ = 0.

Решив данную элементарную систему уравнений, получим значения

x₃ = - 5, x₄ = 25.

Решение неприемлемо, т.к. одно из неизвестных (x₃ = -5) имеет отрицательную величину.

1x₁ + 2x₂ + 3x₃ + 1x₄ + 0x₅ + 0x₆ = 10,

2x₁ - 1x₂ - 4x₃ + 0x₄ + 1x₅ + 0x₆ = 20,

3x₁ - 2x₂ + 5x₃ + 0x₄ + 0x₅ + 1x₆ = 30.

Перед решением этой элементарной системы уравнений все значащие неизвестные второй и третьей строк, не вошедшие в нее, принимаются равными нулю, т.е. x₁ = 0, x₂ = 0, x₃ = 0.

Решив данную элементарную систему уравнений, получим значения

x₅ = 20, x₆ = 30.

Подставим эти значения в первое уравнение. Тогда

x₁ + 2x₂ + 3x₃ + x₄ = 10

1 · 0 + 2 · 0 + 3 · 0 + x₄ = 10

x₄ = 10

X₂ = (0, 0, 0, 10, 20, 30).

Решение приемлемо. Вычислим целевую функцию.



Z₂(X₂) = 2x₁ + 3x₂ - 4x₃ + 5x₄ + 6x₅+ 7x₆

Z₂(X₂) = 2 · 0 + 3 · 0 - 4 · 0 + 5 · 10 + 6 · 20 + 7 · 30 = 380

1x₁ + 2x₂ + 3x₃ + 1x₄ + 0x₅ + 0x₆ = 10,

2x₁ - 1x₂ - 4x₃ + 0x₄ + 1x₅ + 0x₆ = 20,

3x₁ - 2x₂ + 5x₃ + 0x₄ + 0x₅ + 1x₆ = 30.

Перед решением этой элементарной системе уравнений все значащие неизвестные первой и второй строк, не вошедшие в нее, принимаются равными нулю, т.е. x₁ = 0, x₃ = 0, x₄ = 0.

Решив данную элементарную систему уравнений, получим значения

x₂ = 5, x₅ = 25.

Подставим эти значения в третье уравнение. Тогда

3x₁ - 2x₂ + 5x₃ + x₆ = 30.

3 · 0 - 2 · 5 + 5 · 0 + x₆ = 30.

x₆ = 40.

X₃ = (0, 5, 0, 0, 25, 40). Решение приемлемо. Вычислим целевую функцию

Z₃(X₃) = 2x₁ + 3x₂ - 4x₃ + 5x₄ + 6x₅+ 7x₆

Z₃(X₃) = 2 · 0 + 3 · 5 - 4 · 0 + 5 · 0 + 6 · 25 + 7 · 40 = 445

Решение X2 = (0, 0, 0, 10, 20, 30) соответствует условиям задачи. Это значит, что оно является оптимальным (с учетом и тех оставшихся, непоказанных решений).

Ниже приведены исходные данные и результаты решения задач о составлении рациона питания (табл. 3.2).



Таблица 3.2 Исходные данные и результаты решения некоторых задач о составлении рациона питания

№ п/п	Исходные данные к задаче	Оптимальные решения
1	Z(X) = 4x1 - x2 + 2x3 min - x1 + 2x2 + 2x3 <= 15 2x1 + x2 - 3x3 = 4 x1 + 2x2 - x3 >= 8	X* = (0, 53/8, 7/8) Z(X) = - 39/8
2	Z(X) = 10x1 - 5x2 min 2x1 - x2 >= 3 x1 + x2 >= 2 x1 + 2x2 >= -1	X* = (5/3, 1/3) Z(X) = 15
3	Z(X) = 2x1 + 4x2 + 9x3 min 2x1 + 3x2 + x3 >= 4 -3x1 + x2 + x3 <= 4 - x1 + x2 + 2x3 >= 6	X* = (0, 2, 2) Z(X) = 26
4	Z(X) = 3x1 + 2x2 - 3x3 min 2x1 - x2 + x3 <= 12 2x1 - x2 - 2x3 = 3 - x1 + 2x2 + x3 >= 6	X* = (4, 5, 0) Z(X) = 22
5	Z(X) = 4x1 - 6x2 - 8x3 + 10x4 min x1 + x2 + x3 + x4 = 10 - x1 + x2 + 3x3 - 3x4 = 2	X* = (0, 8, 0, 2) Z(X) = - 28

Разработаны программы:

esu_raspred_resurs.exe - программа решения задачи, в Интернете искать по адресу smetod1.narod.ru/esu_raspred_resurs.zip;

esu_raspred_resurs_instruk.doc - инструкция по применению программы решения задачи, в Интернете искать по адресу

smetod1.narod.ru/esu_raspred_resurs _instruk.doc;

4. Глоссарий

задача ресурс рацион переменный

Переменные задачи - величины x₁, x₂, …, x_n, которые полностью характеризуют экономический процесс;

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

Целевая функция - функция переменных задачи, которая характеризует качество выполнения задачи и экстремум которой требуется найти;

Элементарная система уравнений - система из двух уравнений с двумя неизвестными.

a₁₁x₁ + a₁₂x₂ = b₁

a₂₁x₁ + a₂₂x₂ = b₂

Размещено на Allbest.ru