🗊Презентация Линейное программирование

Лекция 1

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

Пример задачи ЛП

Пример задачи линейного программирования Небольшая фирма производит два вида продукции, которая поступает в оптовую продажу. В производственном цикле используются два исходных продукта – А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 т соответственно. Расходы А и В на 1 т двух видов продукции представлены в таблице. Изучение рынка сбыта показало, что суточный спрос на продукцию вида 2 никогда не превышает спроса на продукцию вида 1 более чем на 1 т. Кроме того, установлено – спрос на продукцию вида 2 никогда не превышает 2 т в сутки. Оптовые цены 1 тонны продукции 1 -3 тыс. у.е., продукции 2 – 2 тыс. у.е. Какое количество продукции вида 1 и 2 должна производить фирма, чтобы доход от реализации продукции был максимальным.

Графический метод решения ЗЛП

Стандартная форма линейных оптимизационных моделей

Стандартная форма линейных оптимизационных моделей

Пример приведения ЗЛП к стандартной форме

Симплекс – метод

Вычислительная процедура симплекс-метода линейного программирования

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

Оптимальное решение

Особые случаи решения ЗЛП и применения симплекс метода

Особые случаи решения ЗЛП и применения симплекс метода