49625 (Задача линейного программирования), страница 2

2016-07-30СтудИзба

Описание файла

Документ из архива "Задача линейного программирования", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.

Онлайн просмотр документа "49625"

Текст 2 страницы из документа "49625"

Второй столбец – базисные переменные.

Третий столбец – свободные члены.

Самая верхняя строка – коэффициенты при целевой функции.

Вторая верхняя строка – сами переменные, входящие в целевую функцию и в систему ограничений.

Основное поле симплекс метода – система коэффициентов из уравнения.

Последняя строка – служит для того, чтобы ответить на вопрос: “оптимален план или нет ”.

Индексная строка позволяет нам судить об оптимальности плана.

  1. Проверяют опорное решение, на оптимальность, вычисляя коэффициенты индексной строки по форме:

При решении задачи возможны два случая:

- При решении задачи на максимум:

а) все оценки следует, что решение оптимальное

б) хотя бы одна оценка и при соответствующей переменной нет положительных коэффициентов, то задача не имеет оптимального решения m, k, целевая функция неограниченна в О.Д.Р.

в) хотя бы одна оценка и при соответствующей переменной есть положительный коэффициент то данное решение можно улучшить, построив новое опорное решение на котором целевая функция будет больше.

- При решении задачи на минимум:

а) все оценки следует, что решение оптимальное

б) хотя бы одна оценка и при соответствующей переменной нет положительных коэффициентов, то задача не имеет оптимального решения m, k, целевая функция неограниченна в О.Д.Р.

в) хотя бы одна оценка и при соответствующей переменной есть положительный коэффициент то данное решение можно улучшить, построив новое опорное решение.

  1. Новое опорное решение находится с помощью ключевого столбца, ключевой строки и ключевого элемента.

Ключевой столбец указывает на переменную, которую надо вывести из числа базисных для улучшения решения.

Ключевая строка указывает на переменную, которую надо вывести из числа базисных для улучшения решения.

Ключевой элемент нужен для элементов нового опорного решения (для новой симплексной таблицы).

Их нахождения зависит от цели задачи.

- При решении задачи на максимум:

а) ключевой столбец – это столбец с отрицательной наименьшей оценкой в индексной строке.

б) ключевая строка – это строка с наименьшим отношением свободных членов к положительным коэффициентам ключевого столбца:

min =

в) ключевой элемент – это число расположенное на пересечении ключевых столбца и строки(не может быть равен нулю).

- При решении задач на минимум:

а) ключевой столбец – это столбец с положительной наименьшей оценкой в индексной строке.

б) ключевая строка – это строка с наибольшим отношением свободных членов к положительным коэффициентам ключевого столбца:

mах =

в) ключевой элемент – это число расположено на пересечении ключевых столбца и строки.

  1. Заполняют первую симплексную таблицу следующим образом:

а) ключевую строку делят на ключевой элемент и записывают на том же месте в новой таблице.

б) заполняют базисные столбцы.

в) остальные элементы пересчитывают по правилу “прямоугольника”:

НЭ = СТЭ –

где НЭ – новый элемент

СТЭ – элемент старого плана

РЭ – разрешающей элемент

А и Б – элементы старого плана

  1. Возвращаются ко второму этапу алгоритма – проверка плана на оптимальность.

§ 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 ед. накладных расходов.



Заключение

Данная курсовая работа посвящена вопросу о решении задачи линейного программирования методом последовательного улучшения плана, иначе симплекс – метод. Состоит из введения, двух глав, заключения и списка литературы.

В первой главе рассказывается о линейном программировании в частности, и о том, что такое общая постановка задачи линейного программирования, как составить математическую модель, а также рассказано о канонической форме задач линейного программирования.

Вторая глава работы посвящена практической части решения задачи. Строится математическая модель, решается задача симплексным методом, а также методом Гаусса.

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Нет! Мы не выполняем работы на заказ, однако Вы можете попросить что-то выложить в наших социальных сетях.
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
4123
Авторов
на СтудИзбе
667
Средний доход
с одного платного файла
Обучение Подробнее