49625 (Задача линейного программирования), страница 2
Описание файла
Документ из архива "Задача линейного программирования", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "49625"
Текст 2 страницы из документа "49625"
Второй столбец – базисные переменные.
Третий столбец – свободные члены.
Самая верхняя строка – коэффициенты при целевой функции.
Вторая верхняя строка – сами переменные, входящие в целевую функцию и в систему ограничений.
Основное поле симплекс метода – система коэффициентов из уравнения.
Последняя строка – служит для того, чтобы ответить на вопрос: “оптимален план или нет ”.
Индексная строка позволяет нам судить об оптимальности плана.
-
Проверяют опорное решение, на оптимальность, вычисляя коэффициенты индексной строки по форме:
При решении задачи возможны два случая:
- При решении задачи на максимум:
а) все оценки 
следует, что решение оптимальное
б) хотя бы одна оценка 
и при соответствующей переменной нет положительных коэффициентов, то задача не имеет оптимального решения m, k, целевая функция неограниченна в О.Д.Р.
в) хотя бы одна оценка и при соответствующей переменной есть положительный коэффициент то данное решение можно улучшить, построив новое опорное решение на котором целевая функция будет больше.
- При решении задачи на минимум:
а) все оценки 
следует, что решение оптимальное
б) хотя бы одна оценка 
и при соответствующей переменной нет положительных коэффициентов, то задача не имеет оптимального решения m, k, целевая функция неограниченна в О.Д.Р.
в) хотя бы одна оценка и при соответствующей переменной есть положительный коэффициент то данное решение можно улучшить, построив новое опорное решение.
-
Новое опорное решение находится с помощью ключевого столбца, ключевой строки и ключевого элемента.
Ключевой столбец указывает на переменную, которую надо вывести из числа базисных для улучшения решения.
Ключевая строка указывает на переменную, которую надо вывести из числа базисных для улучшения решения.
Ключевой элемент нужен для элементов нового опорного решения (для новой симплексной таблицы).
Их нахождения зависит от цели задачи.
- При решении задачи на максимум:
а) ключевой столбец – это столбец с отрицательной наименьшей оценкой 
в индексной строке.
б) ключевая строка – это строка с наименьшим отношением свободных членов к положительным коэффициентам ключевого столбца:
min 
= 
в) ключевой элемент – это число расположенное на пересечении ключевых столбца и строки(не может быть равен нулю).
- При решении задач на минимум:
а) ключевой столбец – это столбец с положительной наименьшей оценкой в индексной строке.
б) ключевая строка – это строка с наибольшим отношением свободных членов к положительным коэффициентам ключевого столбца:
mах = 
в) ключевой элемент – это число расположено на пересечении ключевых столбца и строки.
-
Заполняют первую симплексную таблицу следующим образом:
а) ключевую строку делят на ключевой элемент и записывают на том же месте в новой таблице.
б) заполняют базисные столбцы.
в) остальные элементы пересчитывают по правилу “прямоугольника”:
НЭ = СТЭ – 
где НЭ – новый элемент
СТЭ – элемент старого плана
РЭ – разрешающей элемент
А и Б – элементы старого плана
-
Возвращаются ко второму этапу алгоритма – проверка плана на оптимальность.
§ 4 Построение начального опорного решения методом Гаусса
Приводим задачу к каноническому виду.
Z(X) = 
)
Z(X) = 
)
4 2 10 1 0 420
6 2 8 0 0 120 * (-1)
4 2 18 0 -1 250
28 24 20 0 0 0
4 2 10 1 0 420
-6 -2 -8 0 0 -120 + + 
4 2 18 0 -1 250
28 24 20 0 0 0
-2 0 2 1 0 420
6 2 8 0 0 120 *12
-2 0 10 0 -1 130
28 24 20 0 0 0
-2 0 2 1 0 300
72 24 96 0 0 1440 -
-2 0 10 0 -1 130
28 24 20 0 0 0
-2 0 2 1 0 300
72 24 96 0 0 1440 
-2 0 10 0 -1 130
-44 0 -76 0 0 -1440
-2 0 2 1 0 300 *5
3 1 4 0 0 60
-2 0 10 0 -1 130 * (-1)
-44 0 -76 0 0 -1440
-10 0 10 5 0 1500
3 1 4 0 0 60
2 0 -10 0 1 -130 +
-44 0 -76 0 0 -1440
-10 0 10 5 0 1500 
3 1 4 0 0 60
12 0 0 5 1 1370
-44 0 -76 0 0 -1440
-2 0 2 1 0 300 -
3 1 4 0 0 60
2,4 0 0 1 1 274
-44 0 -76 0 0 -1440
-4,4 0 2 0 -1 26 *2
3 1 4 0 0 60
2,4 0 0 1 1 274
-44 0 -76 0 0 -1440
-8,8 0 4 0 -2 52
3 1 4 0 0 60 -
2,4 0 0 1 1 274
-44 0 -76 0 0 -1440
-8,8 0 4 0 -2 52 *19
11,8 1 0 0 2 8
2,4 0 0 1 1 274
-44 0 -76 0 0 -1440
-167,2 0 76 0 -38 988
11,8 1 0 0 2 8
2,4 0 0 1 1 274
-44 0 -76 0 0 -1440 +
-167,2 0 76 0 -38 988 
11,8 1 0 0 2 8
2,4 0 0 1 1 274
-123,2 0 0 0 -38 -452
-2,2 0 1 0 -0,5 13
11,8 1 0 0 2 8
2,4 0 0 1 1 274
-123,2 0 0 0 -38 -452
§ 5 Решение задачи
Составляем симплексную таблицу
Симплексная таблица 1
|
| -452 | -123,2 | 0 | 0 | 0 | -38 | |||||||||
|
| 0 | 13 | -2,2 | 1 | 0 | 0 | -0,5 | ||||||||
|
| 0 | 8 | 11,8 | 1 | 0 | 0 | 2 | ||||||||
|
| 0 | 274 | 2,4 | 0 | 0 | 1 | 1 | ||||||||
|
| 452 | 123,2 | 0 | 0 | 0 | 38 | |||||||||
т. к все > 0 решение оптимальное
Ответ: max Z(X) = 452 при X = (0; 8; 13)
§ 6 Вывод
Максимальная прибыль в размере 425 тыс. руб. может быть достигнута, если производить 8 станков ІΙ вида, 13 станков ІΙІ вида и не производить станки Ι вида.
При этом расходуется 146 ед. сырья, 120 ед. трудовых ресурсов и 250 ед. накладных расходов.
Заключение
Данная курсовая работа посвящена вопросу о решении задачи линейного программирования методом последовательного улучшения плана, иначе симплекс – метод. Состоит из введения, двух глав, заключения и списка литературы.
В первой главе рассказывается о линейном программировании в частности, и о том, что такое общая постановка задачи линейного программирования, как составить математическую модель, а также рассказано о канонической форме задач линейного программирования.
Вторая глава работы посвящена практической части решения задачи. Строится математическая модель, решается задача симплексным методом, а также методом Гаусса.
