Файл: Решение Необходимо найти минимальное значение целевой функции f 2x 1 4x 2 min, при системе ограничений.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 108
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Искомый элемент равен c23=3. Для этого элемента запасы равны 10, потребности 25. Поскольку минимальным является 10, то вычитаем его.
x23 = min(10,25) = 10.
| 4 | 3 | 4 | x | 0 | 11 |
| x | x | 3 | 2 | x | 10 - 10 = 0 |
| 9 | x | 3 | x | 0 | 48 |
| 36 | 0 | 25 - 10 = 15 | 0 | 8 | |
Искомый элемент равен c33=3. Для этого элемента запасы равны 48, потребности 15. Поскольку минимальным является 15, то вычитаем его.
x33 = min(48,15) = 15.
| 4 | 3 | x | x | 0 | 11 |
| x | x | 3 | 2 | x | 0 |
| 9 | x | 3 | x | 0 | 48 - 15 = 33 |
| 36 | 0 | 15 - 15 = 0 | 0 | 8 | |
Искомый элемент равен c11=4. Для этого элемента запасы равны 11, потребности 36. Поскольку минимальным является 11, то вычитаем его.
x11 = min(11,36) = 11.
| 4 | 3 | x | x | x | 11 - 11 = 0 |
| x | x | 3 | 2 | x | 0 |
| 9 | x | 3 | x | 0 | 33 |
| 36 - 11 = 25 | 0 | 0 | 0 | 8 | |
Искомый элемент равен c31=9. Для этого элемента запасы равны 33, потребности 25. Поскольку минимальным является 25, то вычитаем его.
x31 = min(33,25) = 25.
| 4 | 3 | x | x | x | 0 |
| x | x | 3 | 2 | x | 0 |
| 9 | x | 3 | x | 0 | 33 - 25 = 8 |
| 25 - 25 = 0 | 0 | 0 | 0 | 8 | |
Искомый элемент равен c35=0. Для этого элемента запасы равны 8, потребности 8. Поскольку минимальным является 8, то вычитаем его.
x35 = min(8,8) = 8.
| 4 | 3 | x | x | x | 0 |
| x | x | 3 | 2 | x | 0 |
| 9 | x | 3 | x | 0 | 8 - 8 = 0 |
| 0 | 0 | 0 | 0 | 8 - 8 = 0 | |
| | B1 | B2 | B3 | B4 | B5 | Запасы |
| A1 | 4[11] | 3[44] | 4 | 5 | 0 | 55 |
| A2 | 8 | 5 | 3[10] | 2[50] | 0 | 60 |
| A3 | 9[25] | 8 | 3[15] | 5 | 0[8] | 48 |
| Потребности | 36 | 44 | 25 | 50 | 8 | |
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 4*11 + 3*44 + 3*10 + 2*50 + 9*25 + 3*15 + 0*8 = 576
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 4; 0 + v1 = 4; v1 = 4
u3 + v1 = 9; 4 + u3 = 9; u3 = 5
u3 + v3 = 3; 5 + v3 = 3; v3 = -2
u2 + v3 = 3; -2 + u2 = 3; u2 = 5
u2 + v4 = 2; 5 + v4 = 2; v4 = -3
u3 + v5 = 0; 5 + v5 = 0; v5 = -5
u1 + v2 = 3; 0 + v2 = 3; v2 = 3
| | v1=4 | v2=3 | v3=-2 | v4=-3 | v5=-5 |
| u1=0 | 4[11] | 3[44] | 4 | 5 | 0 |
| u2=5 | 8 | 5 | 3[10] | 2[50] | 0 |
| u3=5 | 9[25] | 8 | 3[15] | 5 | 0[8] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;1): 5 + 4 > 8; ∆21 = 5 + 4 - 8 = 1 > 0
(2;2): 5 + 3 > 5; ∆22 = 5 + 3 - 5 = 3 > 0
max(1,3) = 3
Выбираем максимальную оценку свободной клетки (2;2): 5
Для этого в перспективную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| | 1 | 2 | 3 | 4 | 5 | Запасы |
| 1 | 4[11][+] | 3[44][-] | 4 | 5 | 0 | 55 |
| 2 | 8 | 5[+] | 3[10][-] | 2[50] | 0 | 60 |
| 3 | 9[25][-] | 8 | 3[15][+] | 5 | 0[8] | 48 |
| Потребности | 36 | 44 | 25 | 50 | 8 | |
Цикл приведен в таблице (2,2 → 2,3 → 3,3 → 3,1 → 1,1 → 1,2).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| | B1 | B2 | B3 | B4 | B5 | Запасы |
| A1 | 4[21] | 3[34] | 4 | 5 | 0 | 55 |
| A2 | 8 | 5[10] | 3 | 2[50] | 0 | 60 |
| A3 | 9[15] | 8 | 3[25] | 5 | 0[8] | 48 |
| Потребности | 36 | 44 | 25 | 50 | 8 | |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1
= 0.
u1 + v1 = 4; 0 + v1 = 4; v1 = 4
u3 + v1 = 9; 4 + u3 = 9; u3 = 5
u3 + v3 = 3; 5 + v3 = 3; v3 = -2
u3 + v5 = 0; 5 + v5 = 0; v5 = -5
u1 + v2 = 3; 0 + v2 = 3; v2 = 3
u2 + v2 = 5; 3 + u2 = 5; u2 = 2
u2 + v4 = 2; 2 + v4 = 2; v4 = 0
| | v1=4 | v2=3 | v3=-2 | v4=0 | v5=-5 |
| u1=0 | 4[21] | 3[34] | 4 | 5 | 0 |
| u2=2 | 8 | 5[10] | 3 | 2[50] | 0 |
| u3=5 | 9[15] | 8 | 3[25] | 5 | 0[8] |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Минимальные затраты составят: F(x) = 4*21 + 3*34 + 5*10 + 2*50 + 9*15 + 3*25 + 0*8 = 546
Анализ оптимального плана.
Из 1-го склада необходимо груз направить к 1-у потребителю (21 ед.), к 2-у потребителю (34 ед.)
Из 2-го склада необходимо груз направить к 2-у потребителю (10 ед.), к 4-у потребителю (50 ед.)
Из 3-го склада необходимо груз направить к 1-у потребителю (15 ед.), к 3-у потребителю (25 ед.)
На 3-ом складе остался невостребованным груз в количестве 8 ед.
Оптимальный план является вырожденным, так как базисная переменная x35=0.