Для проверки плана на оптимальность используют систему оценок (потенциалов) строк и столбцов, которые рассчитываются по правилу: для любой заполненной ячейки сумма потенциалов соответствующей строки и столбца должна доривнюватися оценке (стоимость перевозки единицы груза или расстояние) этой клетки.
Ui + Vj = Cij
Где: Cij — оценка ячейки;
I — строки (I = 1, 2, …, M),
J — Столбики ( J= 1, 2, …, H)
Ui — оценка I-Й строки (I = 1, 2, … M)
Vj — Оценка J-Го столбца (J = 1, 2, … H)
То есть, если известен потенциал Ui, То Vj = Cij-Ui, а если известен Vj, то Ui = Cij — Vj . При этом один из строк или один из колонок получает произвольную оценку, а оценки последних строк и столбцов надо рассчитать по указанным формулам.
Пусть U1 = 0, тогда потенциалы первого и второго столбцов будут составлять:
V1 = C11-U1 = 6-0 = 6 для В1
V2 = C12-U1 = 4-0 = 4 для В2
Теперь можно определить потенциал второй строки:
U2 = C22 — V2 = 17 — 4 = 13
Определим потенциалы для В3, В4 И Вфикт:
V3 = C23-U2 = 28 — 13 = 15 для В3
V2 = C24-U2 = 3 — 13 = -10 для В4
V2 = C25-U2 = 0 — 13 = -13 для Вфикт
Теперь можно определить потенциал А3:
U3 = C35 — V5 = 0 — (-13) = 13
Во всех занятых клетках условие оптимальности выполняется, а для свободных клеток выполняются расчеты по проверке плана на оптимальность:
Для Х13 сумма потенциалов U1 + V3 = 0 + 15 = 15, £ 15
Для Х14 сумма потенциалов U1 + V4 = 0 + (-10) = -10, что £ 19
Для Х15 сумма потенциалов U1 + V5 = 0 + (-13) = -13, что£ 0
Для Х21 сумма потенциалов U2 + V1 = 13 + 6 = 19,> 13
Для Х31 сумма потенциалов U3 + V1 = 13 + 6 = 19,> 5
Для х32 сумма потенциалов U3 + V2 = 13 + 4 = 17, £ 20
Для х33 сумма потенциалов U3 + V3 = 13 + 15 = 28,> 6
Для Х34 сумма потенциалов U3 + V4 = 13 + (-10) = 3, что £ 10
Следовательно, данный план перевозок не является оптимальным, так как в ячейках Х21, Х31, Х33 не выполняется требование Ui + Vj £ Cij. Необходимо перейти к следующему плану.
Для этого выбирается клетка, в которой сумма потенциалов наиболее превышает отметку, это клетка Х33 и она называется клеткой Пересчета.
Начиная с клетки пересчете строится по занятым клеткам фигура пересчета (замкнутый контур, вершины которого находятся в занятых клетках), которая может иметь вид (некоторые варианты фигуры):
Клетки, которые вошли в фигуры пересчета отражаются поочередно знаками +, -, +, -, … , Начиная с клетки пересчета.
Заполняется новая транспортная таблица:
-количество груза в клетках, которые не вошли в фигуры пересчета переносится в новую таблицу без изменений;
-для клеток фигуры пересчета: количество груза в клетках со знаком + увеличивается, а в ячейках со знаком — уменьшается на одну и ту же величину, а именно, на наименьшее количество груза в ячейках, обозначенных знаком -.
Исправленный таким образом план перевозок записывается в соответствующую таблицу и исследуется на оптимальность, как и предыдущий.
При таком плане перевозок общее количество тонно-километров будет составлять:
FMin = 14 * 6 +12 * 4 +7 * 17 +5 * 3 +21 * 0 +20 * 6 +25 * 0 = 386 т-км.
Вычислим потенциалы по правилу, описанным выше, и проверим составлен план на оптимальность.
Для свободных клеток произведем расчеты:
Для Х13 сумма потенциалов U1 + V3 = 0 + (-7) = -7, что £ 15
Для Х14 сумма потенциалов U1 + V4 = 0 + (-10) = -10, что £ 19
Для Х15 сумма потенциалов U1 + V5 = 0 + (-13) = -13, что £ 0
Для Х21 сумма потенциалов U2 + V1 = 13 + 6 = 19,> 13
Для Х23 сумма потенциалов U2 + V3 = 13 + (-7) = 6, что£ 28
Для Х31 сумма потенциалов U3 + V1 = 13 + 6 = 19,> 5
Для х32 сумма потенциалов U3 + V2 = 13 + 4 = 17, £ 20
для Х34 сумма потенциалов U3 + V4 = 13 + (-10) = 3, что £ 10
Данный план перевозок не является оптимальным, так как в клетках Х21, Х31, не выполняется условие оптимальности Ui + Vj £ Cij.
Выбирается клетка Х31, начиная с нее строится фигура пересчета.
Следующая транспортная таблица имеет вид:
При таком плане перевозок общее количество тонно-километров будет составлять:
FMin = 7 * 6 +19 * 4 +5 * 3 +28 * 0 +7 * 5 +20 * 6 +18 * 0 = 288 т-км.
Вычислим потенциалы и для свободных клеток произведем расчеты по проверке плана на оптимальность:
Для Х13 сумма потенциалов U1 + V3 = 0 + 7 = 7, £ 15
Для Х14 сумма потенциалов U1 + V4 = 0 + 4 = 4, £ 19
Для Х15 сумма потенциалов U1 + V5 = 0 + 1 = -1,> 0
Для Х21 сумма потенциалов U2 + V1 = -1 + 6 = 5, £ 13
Для Х22 сумма потенциалов U2 + V2 = -1 + 4 = 3, £ 17
Для Х23 сумма потенциалов U2 + V3 = -1 + 7 = 6, £ 28
Для х32 сумма потенциалов U3 + V2 = -1 + 4 = 3, £ 20
для Х34 сумма потенциалов U3 + V4 = -1 + 4 = 3, £ 10
Данный план перевозок не является оптимальным, так как в ячейке Х15 не соблюдается требование оптимальности Ui + Vj £ Cij. Построим фигуру перерасчета и рассчитаем новую таблицу.
Рисуем фигуру перерасчета и рассчитаем новую таблицу.
Поставщик |
Потребители |
Запасы |
Потенциалы, Ui |
||||
В1 |
В2 |
В3 |
В4 |
Вфиктивний |
|||
A1 |
6 |
4 |
15 |
19 |
0 |
26 |
0 |
19 |
7 |
||||||
A2 |
13 |
17 |
28 |
3 |
0 |
33 |
0 |
5 |
28 |
||||||
A3 |
5 |
20 |
6 |
10 |
0 |
45 |
0 |
14 |
20 |
11 |
|||||
Потребность |
14 |
19 |
20 |
5 |
46 |
104 |
|
Потенциалы, VJ |
5 |
4 |
6 |
3 |
0 |
При таком плане перевозок общее количество тонно-километров будет составлять:
FMin = 7 * 6 +19 * 4 +5 * 3 +28 * 0 +7 * 5 +20 * 6 +18 * 0 = 281 т.-км.
Вычислим потенциалы и для свободных клеток произведем расчеты по проверке плана на оптимальность:
Для Х11 сумма потенциалов U1 + V1 = 0 + 5 = 5, £ 6
Для Х13 сумма потенциалов U1 + V3 = 0 + 6 = 6, £ 15
Для Х14 сумма потенциалов U1 + V4 = 0 + 3 = 3, £ 19
Для Х21 сумма потенциалов U2 + V1 = 0 + 5 = 5, £ 13
Для Х22 сумма потенциалов U2 + V2 = 0 + 4 = 4, £ 17
Для Х23 сумма потенциалов U2 + V3 = 0 + 6 = 6, £ 28
Для х32 сумма потенциалов U3 + V2 = 0 + 4 = 4, £ 20
для Х34 сумма потенциалов U3 + V4 = 0 + 3 = 3, £ 10
Данный план перевозок является оптимальным, так как во всех клетках таблицы выполняется условие оптимальности.
При оптимальном плане перевозок общее количество тонно-километров будет составлять 281 т.-км.
Так, перевозка груза следует организовать таким образом:
-из пункта А1 необходимо перевезти 19тон в пункт В2 и 7тон в пункт Вфикт;
-из пункта А2 необходимо перевезти 5тон в пункт В4 и 28тон в пункт Вфикт;
-из пункта А3 необходимо перевезти 14тон в пункт 1, 20тон в пункт В3 и 11тон в пункт Вфикт.
Задача 4.
Экономико-математическая модель оптимизации рациона кормления животных.
Условие задачи.
Составить суточный кормовой рацион для коровы живой массой 500 кг и надою 16л за сутки на стойловый период.
В рационе должно содержаться не менее:
Кормовых единиц |
12,6 |
Обменной энергии, МДж |
148 |
Сухого вещества, кг |
15,8 |
Переваримого протеина, г |
1260 |
Сырой клетчатки, г |
4110 |
Крахмала, г |
1705 |
Сахаров, г |
1135 |
Кальция, г |
89 |
Фосфора, г |
63 |
Магния, г |
25 |
Калия, г |
96 |
Серы, г |
31 |
Железа, мг |
1010 |
Каротина, мг |
565 |
В рационе должно быть не менее (в натуральном выражении):
-концентрированных кормов — 1,5 кг;
-сочных кормов — 14 кг;
-грубых кормов — 10 кг.
Для обеспечения сбалансированности рациона следует учесть соотношение между отдельными кормами:
-количество ячменя должна быть в 3 раза больше количества других концентрированных кормов;
-количество силоса должна быть в 2 раза больше количества других сочных кормов;
-количество сена должна быть в 3 раза больше количества соломы
-количество сена соотносится с количеством сенажа как 2:1.
Составить рацион, который будет иметь минимальную стоимость.
Корма для разработки экономико-математической модели выбрать согласно варианту, числовые данные взять из таблицы.
Разработать экономико-математическую модель, переменными в которой будут корма в натуральном выражении, кг (Х1, Х 2, Х 3, …).
В хозяйстве имеются следующие корма, из которых необходимо составить рацион: свекла кормовая, морковь, сенаж разнотравные, силос кукурузный, жом свекольный, сено лучне в фазе цветения, солома пшеничная, зерно ячменя, зерно овса, зерно гороха, жмых подсолнечный.
Содержание питательных веществ в 1 кг корма
Показатель |
Сахарная свекла |
Морковь |
Сенаж Разнотравных |
Силос кукурузный |
Жом свежий |
Сено лучне в фазе цветения |
Солома Пшеничная |
Зерно |
||
Овес |
Ячмень |
Горох |
||||||||
Кормовые единицы |
0,24 |
0,14 |
0,29 |
0,20 |
0,12 |
0,46 |
0,20 |
1,00 |
1,15 |
1,18 |
Обменная энергия, МДж |
2,84 |
2,20 |
3,44 |
2,30 |
1,13 |
6,59 |
4,76 |
9,02 |
10,5 |
11,1 |
Сухое вещество, г |
230 |
120 |
450 |
250 |
112 |
828 |
846 |
850 |
850 |
850 |
Переваренный протеин, г |
7 |
8 |
23 |
14 |
6 |
49 |
5 |
79 |
85 |
192 |
Сырая клетчатка, г |
14 |
11 |
157 |
75 |
33 |
254 |
364 |
97 |
49 |
54 |
Крахмал, г |
6 |
7 |
15 |
8 |
— |
— |
— |
320 |
485 |
455 |
Сахара, г |
120 |
35 |
23 |
6 |
2,5 |
20 |
3 |
25 |
2 |
55 |
Кальций, г |
0,5 |
0,9 |
4,9 |
1,4 |
1,5 |
7,2 |
2,8 |
1,5 |
2 |
2,0 |
Фосфор, г |
0,5 |
0,6 |
1,3 |
0,4 |
0,14 |
2,1 |
0,8 |
3,4 |
3,9 |
4,3 |
Магний, г |
0,4 |
0,3 |
1,3 |
0,5 |
0,5 |
1,7 |
0,8 |
1,2 |
1,0 |
1,2 |
Калий, г |
2,6 |
5,1 |
11,7 |
2,9 |
0,8 |
17 |
7,6 |
5,4 |
5,0 |
10,7 |
Сера, г |
0,3 |
0,2 |
0,9 |
0,4 |
0,4 |
1,7 |
0,8 |
1,3 |
1,3 |
1,6 |
Железо, мг |
31 |
10 |
208 |
61 |
24 |
287 |
360 |
41 |
50 |
60 |
Каротин, мг |
0,3 |
54 |
25 |
20 |
— |
15 |
4 |
1,3 |
0,3 |
0,2 |
Цена 1 кг корма, грн. |
0,3 |
0,5 |
0,16 |
0,06 |
0,04 |
0,18 |
0,05 |
0,22 |
0,26 |
0,32 |
Решения.
Переменными задачи являются количество кормов по видам в рационе:
Х1 — количество сахарной свеклы;
Х2 — количество моркови
Х3 — количество сенажа;
Х4 — количество силоса;
Х5 — количество жома;
Х6 — количество сена;
Х7 — количество соломы
Х8 — количество зерна овса;
Х9 — количество зерна ячменя;
Х10 — количество зерна гороха.
На эти переменные наложено 20 ограничений, которые можно разделить на три группы:
1) ограничение (с 1-го по 14-е), которые обеспечивают необходимую минимальное количество соответствующей питательного вещества в Рационе;
Так первое ограничение касается содержания кормовых единиц в рационе:
0,24X1 +0,14X2 +0,29X3 +0,2X4 +0,12X5 +0,46X6 +0,2X7 +1X8 +1,15X9 +1,18X10> = 12,6; где
Переменные Х 1, Х 2, …, Х 10 — количество кормов в рационе по видам (коэффициенты при этих переменных — это содержание кормовых единиц в 1 кг соответствующего корма);
12,6 — биологическая норма содержания кормовых единиц в рационе.
Аналогичный структурный вид имеют ограничения по содержания других питательных веществ в рационе (обменной энергии, сухого вещества, переваримого протеина, …)
2) ограничение (с 15-го по 18-е), которые характеризуют соотношение между отдельными запятыми;
15-е ограничение задает соотношение количества ячменя в других концентрированных и имеет такой математический вид:
1X9-3X8-3X10 = 0; где
X9 — количество зерна ячменя в рационе;
X8,X10 — количество зерна овса и гороха в рационе;
1 и 3 — коэффициенты пропорциональности.
3) ограничения (с 19-го по 21-е), которые задают нижнюю границу вхождения в рацион одного корма или группы кормов.
19-е — ограничение обеспечивает минимальное количество концентрированных кормов в рационе:
1X9 +1X8 +1X10> = 1,5; где
X9,X8, Х 10 — количество овса, ячменя и гороха в рационе.
В качестве критерия оптимальности выступает минимальная стоимость рациона:
FMin = 0,3X1 +0,5 Х 2 +0,16X3 +0,06X4 +0,04X5 +0,18X6 +0,05X7 +0,22X8 +0,26X9 +0,32X10
Экономико-математическая модель оптимизации кормового рациона
(В табличном виде).
Показатель |
Сахарная свекла |
Морковь |
Сенаж Разнотравных |
Силос кукурузный |
Жом свекольный свежий |
Сено лучне в фазе цветения |
Солома Пшеничная |
Зерно Овса |
Зерно ячменя |
Зерно гороха |
Тип и размер ограничений |
|
Переменные |
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
Х7 |
Х8 |
Х9 |
Х10 |
||
1. |
Кормовые единицы |
0,24 |
0,14 |
0,29 |
0,20 |
0,12 |
0,46 |
0,20 |
1,00 |
1,15 |
1,18 |
> = 12,6 |
2. |
Обменная энергия, МДж |
2,84 |
2,20 |
3,44 |
2,30 |
1,13 |
6,59 |
4,76 |
9,02 |
10,5 |
11,1 |
> = 148 |
3. |
Сухое вещество, г |
230 |
120 |
450 |
250 |
112 |
828 |
846 |
850 |
850 |
850 |
> = 15800 |
4. |
Переваренный протеин, г |
7 |
8 |
23 |
14 |
6 |
49 |
5 |
79 |
85 |
192 |
> = 1260 |
5. |
Сырая клетчатка, г |
14 |
11 |
157 |
75 |
33 |
254 |
364 |
97 |
49 |
54 |
> = 4110 |
6. |
Крахмал, г |
6 |
7 |
15 |
8 |
320 |
485 |
455 |
> = 1705 |
|||
7. |
Сахара, г |
120 |
35 |
23 |
6 |
2,5 |
20 |
3 |
25 |
2 |
55 |
> = 1135 |
8. |
Кальций, г |
0,5 |
0,9 |
4,9 |
1,4 |
1,5 |
7,2 |
2,8 |
1,5 |
2 |
2,0 |
> = 89 |
9. |
Фосфор, г |
0,5 |
0,6 |
1,3 |
0,4 |
0,14 |
2,1 |
0,8 |
3,4 |
3,9 |
4,3 |
> = 63 |
10. |
Магний, г |
0,4 |
0,3 |
1,3 |
0,5 |
0,5 |
1,7 |
0,8 |
1,2 |
1,0 |
1,2 |
> = 25 |
11. |
Калий, г |
2,6 |
5,1 |
11,7 |
2,9 |
0,8 |
17 |
7,6 |
5,4 |
5,0 |
10,7 |
> = 96 |
12. |
Сера, г |
0,3 |
0,2 |
0,9 |
0,4 |
0,4 |
1,7 |
0,8 |
1,3 |
1,3 |
1,6 |
> = 31 |
13. |
Железо, мг |
31 |
10 |
208 |
61 |
24 |
287 |
360 |
41 |
50 |
60 |
> = 1010 |
14. |
Каротин, мг |
0,3 |
54 |
25 |
20 |
15 |
4 |
1,3 |
0,3 |
0,2 |
> = 565 |
|
15. |
Соотношение количества ячменя в других концентрированных |
-3 |
1 |
-3 |
= 0 |
|||||||
16. |
Соотношение количества силоса до других сочных |
-2 |
-2 |
1 |
-2 |
= 0 |
||||||
17. |
Соотношение количества сена к соломе |
1 |
-3 |
= 0 |
||||||||
18. |
Соотношение количества сена в сенажа |
-2 |
1 |
= 0 |
||||||||
19. |
Нижняя граница концентрированных кормов в рационе |
1 |
1 |
1 |
> = 1,5 |
|||||||
20. |
Нижняя граница грубых кормов в рационе |
1 |
1 |
1 |
> = 10 |
|||||||
21. |
Нижняя граница сочных кормов в рационе |
1 |
1 |
1 |
1 |
> = 14 |
||||||
22. |
Целевая функция (стоимость рациона), грн. |
0,3 |
0,5 |
0,16 |
0,06 |
0,04 |
0,18 |
0,05 |
0,22 |
0,26 |
0,32 |
Min |
Задача 5.
Экономико-математическая модель оптимизации структуры посевных площадей.