Автор работы: Пользователь скрыл имя, 27 Июня 2012 в 10:42, курсовая работа
Целью данной курсовой работы является : освоить навыки использования линейного программирования для решения задач оптимизации. Для этого были поставлены следующие задачи :
1)Изучить теоретические сведения, необходимые для решения задач оптимизации методом линейного программирования.
2)Изучить методы решения задач линейного программирования.
3)Решить поставленные задачи, используя рассмотренные методы линейного программирования.
Введение
I.Теоретический раздел
1.1 Понятие о линейном программировании. Формулировка задачи линейного программирования
1.2 Виды задач линейного программирования
1.3 Методы решения задач линейного программирования
II. Практический раздел
2.1 Решение транспортной задачи
2.2 Решение производственной задачи
Заключение
Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
| 1 | 2 | 3 | 4 | 5 | Запасы |
1 | 7 | 4 | 15[50] | 9 | 14[70] | 120 |
2 | 11 | 2[65] | 7[25] | 2[60] | 10 | 150 |
3 | 4[85] | 5 | 12[15] | 8 | 17 | 100 |
Потребности | 85 | 65 | 90 | 60 | 70 |
|
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
| v1=7 | v2=10 | v3=15 | v4=10 | v5=14 |
u1=0 | 7 | 4 | 15[50] | 9 | 14[70] |
u2=-8 | 11 | 2[65] | 7[25] | 2[60] | 10 |
u3=-3 | 4[85] | 5 | 12[15] | 8 | 17 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (1;2): 4
Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| 1 | 2 | 3 | 4 | 5 | Запасы |
1 | 7 | 4[+] | 15[50][-] | 9 | 14[70] | 120 |
2 | 11 | 2[65][-] | 7[25][+] | 2[60] | 10 | 150 |
3 | 4[85] | 5 | 12[15] | 8 | 17 | 100 |
Потребности | 85 | 65 | 90 | 60 | 70 |
|
Цикл приведен в таблице (1,2; 1,3; 2,3; 2,2; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1 | 2 | 3 | 4 | 5 | Запасы |
1 | 7 | 4[50] | 15 | 9 | 14[70] | 120 |
2 | 11 | 2[15] | 7[75] | 2[60] | 10 | 150 |
3 | 4[85] | 5 | 12[15] | 8 | 17 | 100 |
Потребности | 85 | 65 | 90 | 60 | 70 |
|
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
| v1=1 | v2=4 | v3=9 | v4=4 | v5=14 |
u1=0 | 7 | 4[50] | 15 | 9 | 14[70] |
u2=-2 | 11 | 2[15] | 7[75] | 2[60] | 10 |
u3=3 | 4[85] | 5 | 12[15] | 8 | 17 |
Информация о работе Использование линейного программирования для решения задач оптимизации