Общая постановка задачи линейного программирования. Критерии оптимальности как количественная оценка оптимизируемого качества объекта. Графический метод решения задачи программирования. Сущность симплекс-метода, порядок расчета. Теорема двойственности.
Аннотация к работе
Факультет компьютерных технологий, экономики и дизайна Решение оптимизационных экономических задач методами линейного программированияОптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях. На основании выбранного критерия оптимальности составляется целевая функция, представляющая собой зависимость критерия оптимальности от параметров, влияющих на ее значение. Вид критерия оптимальности или целевой функции определяется конкретной задачей оптимизации. Методы оптимизации могут быть скалярными (оптимизация проводится по одному критерию), векторными (оптимизация проводится по многим критериям), поисковыми (включают методы регулярного и методы случайного поиска), аналитическими (методы дифференциального исчисления, методы вариационного исчисления и др.), вычислительными (основаны на математическом программировании, которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим, эвристическим и т.д.), теоретико-вероятностными, теоретико-игровыми и др.Линейное программирование - направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием оптимальности. задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке"); Линейное программирование - наиболее применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ; Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.Пусть некоторая производственная единица (цех, завод, объединение и т. д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции (товаров), известных под номерами, обозначаемыми индексом j . Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т. д.). Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т. д. Известны также технологические коэффициенты , которые указывают, сколько единиц i-го ресурса требуется для производства единицы продукции j-го вида. Так как - расход i-го ресурса на производство единиц j-й продукции, то, просуммировав расход i-го ресурса на выпуск всех n видов продукции, получим общий расход этого ресурса, который не должен превосходить единиц: Чтобы искомый план был реализован, наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объемы выпуска продукции: .При откорме каждое животное должно получить не менее А=28 ед.питательного вещества S1, не менее В=5 ед. вещества S2 и не менее С=9 вещества S3 . Содержание количества единиц питательных веществ в 1 килограмме каждого вида корма и стоимость одного килограмма корма дана в таблицах 1 и 2. Питательные вещества Количество единиц питательных веществ в 1 кг. корма корм 1 корм 2 Необходимо найти минимальное значение целевой функции Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).Для изготовления 4-ех видов продукции P1, P2, P3, P4 используют два вида сырья: S1 и S2 . Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а так же величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2. Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). A = a(ij) этой системы уравнений имеет вид: Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.Пример(3) а) Составить задачу двойственную к примеру 2. б) найти ее решение любым методом. в) найти решение задачи 2, используя теорему двойственности. Составим двойственную задачу к прямой задаче. Необходимо найти минимальное значение целевой функции Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
План
Содержание
Введение
1. Общая постановка задачи линейного программирования
2. Примеры экономических задач, приводящихся к задачам ЛП
3. Графический метод решения задачи ЛП
4. Симплекс-метод решения задач ЛП
5. Теорема двойственности
6. Транспортная задача
7. Решение задач ЛП с использованием программы «Microsoft Excel»
Заключение
Литература линейный программирование графический двойственность