Презентация Симплексный метод линейного программирования

Презентация Симплексный метод линейного программирования


Предлагаем ознакомиться с содержанием и скачать для редактирования или печати презентацию «Симплексный метод линейного программирования», содержащую 26 слайдов и доступную в формате ppt. Размер файла доклада составляет 105.32 KB

Просмотреть и скачать

Слайды и текст этого доклада

Симплексный метод линейного программирования
Рис.1 Симплексный метод линейного программирования
План: Общая постановка задачи линейного программирования (ЗЛП). Примеры ЗЛП. Алгоритм симплексного м
Рис.2 План: Общая постановка задачи линейного программирования (ЗЛП). Примеры ЗЛП. Алгоритм симплексного метода линейного программирования
В практике землеустройства наиболее распространены экономико-математические модели, реализуемые с ис
Рис.3 В практике землеустройства наиболее распространены экономико-математические модели, реализуемые с использованием методов линейного программирования. В моделях этого класса ЦФ и ограничения задачи представлены в виде системы линейных уравнений и неравенств.
Линейное программирование – направление математики, изучающее методы решения экстремальных задач, ко
Рис.4 Линейное программирование – направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием оптимальности. Линейное программирование – направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием оптимальности. В 1939г. Канторович Л. В. впервые сформулировал ЗЛП. 1975г. – Нобелевская премия
Примеры ЗЛП Задача об оптимальном использовании ресурсов при производственном планировании; Задача о
Рис.5 Примеры ЗЛП Задача об оптимальном использовании ресурсов при производственном планировании; Задача о смесях (планирование состава продукции); Задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах; Транспортные задачи.
Землеустроительные задачи, решаемые методами линейного программирования, должны удовлетворять требов
Рис.6 Землеустроительные задачи, решаемые методами линейного программирования, должны удовлетворять требованиям: быть многовариантыми; иметь точно определённую ЦФ, для которой ищется экстремальное значение; иметь определённые ограничивающие условия, формирующие область допустимых решений задачи.
Задача линейного программирования
Рис.7 Задача линейного программирования
Для решения задач линейного программирования разработан ряд алгоритмов: Симплексный метод Распредели
Рис.8 Для решения задач линейного программирования разработан ряд алгоритмов: Симплексный метод Распределительный метод
Алгоритмы базируются на последовательном улучшении первоначального плана и за определённое число цик
Рис.9 Алгоритмы базируются на последовательном улучшении первоначального плана и за определённое число циклически повторяющихся вычислений (итераций) позволяют получить оптимальное решение.
Преимущество симплексного метода: Преимущество симплексного метода: Не требует приведения различных
Рис.10 Преимущество симплексного метода: Преимущество симплексного метода: Не требует приведения различных величин к единому измерителю, т. е. производственные ресурсы и коэффициенты затрат используются при решении задачи в обычных, свойственных для них единицах измерения: в гектарах, ч-днях, центнерах, рублях и т. д. Симплекс-метод был предложен в 1949г. Дж. Данцигом.
Распределительный метод предназначен для решения транспортной задачи (распределение определённого ко
Рис.11 Распределительный метод предназначен для решения транспортной задачи (распределение определённого количества однородного ресурса между потребителями). Все переменные в задачах, решаемых распределительным методом должны иметь одну и ту же единицу измерения.
Составные части модели линейного программирования Совокупность основных переменных (площади посевов,
Рис.12 Составные части модели линейного программирования Совокупность основных переменных (площади посевов, объёмы производства продукции, затраты ресурсов и т. д. ); Система линейных ограничений, определяющая ОДЗ переменных; Целевая функция, определяющая критерий оптимальности задачи.
В качестве критерия оптимальности – требование максимизации или минимизации ЦФ при заданных ограниче
Рис.13 В качестве критерия оптимальности – требование максимизации или минимизации ЦФ при заданных ограничениях. Целевая функция – показатель, обобщённо характеризующий один из аспектов деятельности хозяйства – чистый доход, валовая продукция в целом или по отдельной отрасли, затраты и т. д.
2. Алгоритм симплексного метода линейного программирования Задача Возделываются культуры: горох, овё
Рис.14 2. Алгоритм симплексного метода линейного программирования Задача Возделываются культуры: горох, овёс, кормовая свекла. Площадь пашни – 400 га, трудовые ресурсы – 4200 ч-дн. , материально-денежные средства – 100000 д. е. Посевная площадь кормовой свеклы должна быть не более 50 га. Требуется определить оптимальное сочетание посевов культур, обеспечивающее максимум валовой продукции.
Затраты труда и средств на 1 га и выход продукции с 1 га
Рис.15 Затраты труда и средств на 1 га и выход продукции с 1 га
Обозначим: Х1 - площадь посева гороха, га; Х2 - площадь посева овса, га; Х3 - площадь посева кормово
Рис.16 Обозначим: Х1 - площадь посева гороха, га; Х2 - площадь посева овса, га; Х3 - площадь посева кормовой свеклы, га.
ЭММ ЗЛП
Рис.17 ЭММ ЗЛП
Введём переменные: Х4, Х5, Х6, Х7 - дополнительные переменные, обозначающие недоиспользованные ресур
Рис.18 Введём переменные: Х4, Х5, Х6, Х7 - дополнительные переменные, обозначающие недоиспользованные ресурсы (пашня, трудовые ресурсы, денежно-материальные средства)
ЭММ ЗЛП в канонической форме
Рис.19 ЭММ ЗЛП в канонической форме
Опорный план
Рис.20 Опорный план
Алгоритм симплексного метода Проверяем план на оптимальность Если задача решается на максимум, то в
Рис.21 Алгоритм симплексного метода Проверяем план на оптимальность Если задача решается на максимум, то в целевой строке все элементы должны быть ≥ 0. Если задача решается на минимум, то в целевой строке все элементы должны быть ≤ 0. Если план не оптимальный, то строим следующий план по алгоритму:
Алгоритм симплексного метода Находим ключевой столбец (в целевой строке наибольшее по абсолютной вел
Рис.22 Алгоритм симплексного метода Находим ключевой столбец (в целевой строке наибольшее по абсолютной величине) Находим ключевую строку Ресурсы соответствующие элементы ключ. столбца Наименьшее частное указывает на ключевую строку На пересечении ключ. столбца и ключ. строки находится ключевой элемент
В новом плане в базисе меняем ключ. строку на ключ. столбец В новом плане в базисе меняем ключ. стро
Рис.23 В новом плане в базисе меняем ключ. строку на ключ. столбец В новом плане в базисе меняем ключ. строку на ключ. столбец Заполняем элементы ключ. строки: Предыдущий элемент Новый элемент = ---------------------------------- ключевой элемент 6. В ключ. столбце оставшиеся элементы = 0
7. Если в ключевой строке имеются нули, то соответствующие столбцы перейдут без изменения 8. Оставши
Рис.24 7. Если в ключевой строке имеются нули, то соответствующие столбцы перейдут без изменения 8. Оставшиеся элементы вычисляем по «правилу прямоугольника» соотв. эл. кл. строки * соотв. эл. кл. столбца Предыд. - --------------------------------------------------------- элемент ключевой элемент
II –ая итерация
Рис.25 II –ая итерация
III –ая итерация
Рис.26 III –ая итерация


Скачать презентацию