Автор работы: Пользователь скрыл имя, 08 Июня 2012 в 22:31, курсовая работа
Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за "вклад в разработку теории и оптимального использования ресурсов в экономике".
Введение_____________________________________________2
2. Линейное программирование _____________________________3
3. Методы решения задач_________________________________4
4. Искусственный базис____________________________________4
5. Алгоритм метода искусственного базиса__________________6
6. Блок - схема___________________________________________7
7. Задача_______________________________________________8
8. Список литературы_________________________
искусственные,
базисные переменные.
| X1 | X2 | X3 | X4 | X5 | |||||||||||||
| Z | 0 | -2 | -1 | -6 | 12 | 9 | 0 | 0 | 0 | ||||||||
| 13 | 1 | 1 | 7 | -3 | -7 | 1 | 0 | 0 | |||||||||
| 20 | 1 | 2 | 13 | 2 | -14 | 0 | 1 | 0 | |||||||||
| 19 | 1 | 3 | 20* | 6 | -23 | 0 | 0 | 1 | |||||||||
| M | -52 | -3 | -6 | -40 | -5 | 44 | 0 | 0 | 0 | ||||||||
X1 = ( 0 , 0 , 0 , 0 , 0 , 13 , 20 , 19 )
min
Элементы строки r3 разделим на 20.
| X1 | X2 | X3 | X4 | X5 | |||||||||||||
| Z | 0 | -2 | -1 | -6 | 12 | 9 | 0 | 0 | 0 | ||||||||
| 13 | 1 | 1 | 7 | -3 | -7 | 1 | 0 | 0 | |||||||||
| 20 | 1 | 2 | 13 | 2 | -14 | 0 | 1 | 0 | |||||||||
| 1* | 0 | 0 | |||||||||||||||
| M | -52 | -3 | -6 | -40 | -5 | 44 | 0 | 0 | 0 | ||||||||
Убираем искусственную переменную r3, заменяем ее на базисную переменную X3.
Пересчитываем
таблицу.
| X1 | X2 | X3 | X4 | X5 | |||||||||||
| Z | 0 | 0 | 0 | ||||||||||||
| 0 | * | 1 | 0 | ||||||||||||
| 0 | 0 | 1 | |||||||||||||
| 1 | 0 | 0 | |||||||||||||
| M | -14 | -1 | 0 | 0 | 7 | -2 | 0 | 0 | |||||||
X2 = ( 0 , 0 , 19/20 , 0 , 0 , 127/20 , 153/20 )
min
Элементы строки
r1 разделим на .
| X1 | X2 | X3 | X4 | X5 | |||||||||||
| Z | 0 | 0 | 0 | ||||||||||||
| 0 | 1* | 0 | |||||||||||||
| 0 | 0 | 1 | |||||||||||||
| 1 | 0 | 0 | |||||||||||||
| M | -14 | -1 | 0 | 0 | 7 | -2 | 0 | 0 | |||||||
Убираем искусственную переменную r1, заменяем ее на базисную переменную X5.
Пересчитываем
таблицу.
| X1 | X2 | X3 | X4 | X5 | |||||||||
| Z | -7 | -3 | 0 | 0 | 24 | 0 | 0 | ||||||
| 0 | 1 | 0 | |||||||||||
| 0 | * | 0 | 1 | ||||||||||
| 1 | 0 | 0 | |||||||||||
| M | 0 | 0 | 0 | ||||||||||
X3 = ( 0 , 0 , 166/21 , 0 , 127/21 , 40/21 )
min
Элементы строки
r2 разделим на .
| X1 | X2 | X3 | X4 | X5 | |||||||||
| Z | -7 | -3 | 0 | 0 | 24 | 0 | 0 | ||||||
| 0 | 1 | 0 | |||||||||||
| 0 | 1* | 0 | |||||||||||
| 1 | 0 | 0 | |||||||||||
| M | 0 | 0 | 0 | ||||||||||
Убираем искусственную переменную r2, заменяем ее на базисную переменную X4.
Все искусственные переменные исключены, пересчитываем таблицу симплексным методом
| X1 | X2 | X3 | X4 | X5 | |||||||
| Z | 0 | 0 | 0 | ||||||||
| 0 | 0 | 1 | |||||||||
| 0 | 1 | 0 | |||||||||
| * | 1 | 0 | 0 | ||||||||
| M | 0 | 0 | 0 | 0 | 0 | 0 | |||||
X4 = ( 0 , 0 , 662/57, 40/57 , 539/57 )
min
Разделим элементы строки X3 на 17/57
| X1 | X2 | X3 | X4 | X5 | |||||||
| Z | 0 | 0 | 0 | ||||||||
| 0 | 0 | 1 | |||||||||
| 0 | 1 | 0 | |||||||||
| 1* | 0 | 0 | |||||||||
Пересчитываем таблицу.
| X1 | X2 | X3 | X4 | X5 | |||||||
| Z | 0 | 0 | 3 | 0 | 0 | ||||||
| 0 | 0 | 1 | |||||||||
| 0 | 1 | 0 | |||||||||
| 1* | 0 | 0 | |||||||||
X = ( 662/17 , 0 ,0, 70/17, 33/17) Z = 11
условие удовлетворено. Наибольшее значение Z=11.
Решений множество потому, что небазисная переменная х2 в строке Z равна 0.