Образовательная программа: Вычислительная техника и программное обеспечение 8D06104
жүктеу/скачать 221,11 Kb.
|
- Бұл бет үшін навигация:
- Подготовил
- 1. Математическая модель линейного программирования Линейное программирование
|
Лекция 6. Математическая модель линейного программирования. Часть1. Дисциплина: Методы оптимизации в инженерии, 5 кредитов Образовательная программа: Вычислительная техника и программное обеспечение 8D06104 Подготовил: д.ф.-м.н., профессор Искаков Казизат Такуадинович План лекции Математическая модель линейного программирования. Графический метод решения задачи линейного программирования. Симплексный метод решения задач линейного программирования. 1. Математическая модель линейного программирования Линейное программирование позволяет найти экстремальные (наибольшие и наименьшие) значения линейной функции, на неизвестные которой наложены линейные ограничения. Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений. Решение задачи линейного программирования заключается в выборе наилучшего (оптимального) варианта из множества возможных по какому-либо признаку – критерию оптимальности. Признаки оптимизационной модели: 1) наличие признака оптимальности (специального показателя выгодности или критерия оптимальности), который называется целевой функцией. Типичные критерии оптимальности: максимум дохода, прибыли, валовой продукт, производительность, эффективность. В таких случаях выгодно, чтобы показатель оптимальности был для выбранного варианта решения максимальным. Другая группа критериев – это минимум издержек, себестоимости, капиталовложений, трудоемкости, то есть в этих случаях критерий должен быть минимальным; 2) наличие системы ограничений, то есть условий, которые описывают множество возможных вариантов (решений), из которых выбирается оптимальный. Множество возможных решений всегда ограничено (ресурсами сырья, наличием рабочей силы, количеством и качеством оборудования и т.п.). Поэтому каждое из рассматриваемых решений должно быть допустимым, т.е. удовлетворять имеющимся ограничениям. Общая задача линейного программирования формулируется следующим образом. Дана система m линейных уравнений и неравенств с n переменными (система ограничений): ( 6.1) или система ограничений в краткой записи: (6.2) Также задана линейная целевая функция где i – номер ограничения; m – количество ограничений; j – номер переменной; n – количество переменных; xj – размер переменной j; aij – коэффициенты при переменных xj; bi – объемы правых частей ограничений; cj – целевой функции F. Необходимо найти такое решение (множество значений переменных) 𝑋=(𝑥1,𝑥2,…,𝑥𝑛) системы ограничений, при котором линейная функция F принимает максимальное (или минимальное) значение: В общем случае задача может иметь бесконечное множество решений. Решение , которое удовлетворяет ограничениям, называют планом. Если все компоненты xj ≥ 0 ( ), то решение (план) называют допустимым решением (опорным планом). Множество опорных планов образует область допустимых решений. Решение , которое удовлетворяет всем ограничениям, условию неотрицательности всех переменных (xj ≥ 0) и при этом дает max (min) целевой функции F, называется оптимальным решением (оптимальным планом). жүктеу/скачать 221,11 Kb. Достарыңызбен бөлісу:
|