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

Линейное программирование

Оглавление Задача линейного программирования – 3 слайд. Геометрический метод решения ЗЛП – 26 слайд. Задача линейного программирования в стандартной форме – 32 слайд. Симплексный метод решения ЗЛП – 42 слайд. Метод Гаусса – 48 слайд. Симплекс метод – 58 слайд. Метод искусственного базиса – 76 слайд. Двойственность задач линейного программирования – 87 слайд.

Задача линейного программирования (ЛП)  

Этапы построения математической модели Определение переменных задачи. Представление ограничений в виде линейных уравнений или неравенств. Задание линейной целевой функции и смысла оптимизации.

Классические задачи линейного программирования Задача технического контроля (слайд 6); Транспортная задача (слайд 13 ); Задача о диете (слайд 16); Задача об использовании сырья (слайд 19).

Задача технического контроля Примечание: ОТК – Отдел Технического Контроля

Построение модели Определим переменные задачи – число контролеров 1 разряда; – число контролеров 2 разряда. Представим ограничение в виде неравенств

Построение модели В день необходимо изготовить 1800 изделий (за 8 часов работы). Или

3. Задание целевой функции Расходы фирмы имеют две составляющие заработная плата контроллеров; убытки из-за ошибок контроллеров. Таким образом, один контроллер соответствующего разряда обходится фирме: I разряд II разряд Целевая функция затрат на ОТК за 8 часов:

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

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

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

Математическая модель задачи Введем переменные - количество продукта перевозимого из пункта в пункт. Тогда математическая постановка задачи имеет вид:

Задача о диете Или задача о составлении рациона

Имеется n различных продуктов. Стоимость каждого продукта составляет . Имеется n различных продуктов. Стоимость каждого продукта составляет . Ингредиенты продуктов следующие: Калорийность; жиры ; белки ; углеводы . Суточная потребность конкретного человека в калориях, жирах, белках и углеводах составляет , , , единиц соответственно. Требуется удовлетворить суточную потребность в энергии, не превышая потребления жиров, белков, углеводов при минимальных затратах.

Математическая модель задачи Введем переменные - количество потребления j-го продукта. Тогда математическая постановка задачи имеет вид:

Задача об использовании сырья

Изготавливаются два продукта и из трех видов сырья , , . Изготавливаются два продукта и из трех видов сырья , , . Запасы каждого сырья равны , , . На единицу продукции уходит количества сырья – ; – . На единицу продукции уходит количества сырья – ; – . Требуется так запланировать выпуск продуктов и , чтобы доход от реализации продукции был максимален при имеющихся запасах сырья.

Исходные данные задачи Представим исходные данные в виде таблицы

Пусть имеет место задача об использовании сырья некоторого кондитерского предприятия, выпускающего Пусть имеет место задача об использовании сырья некоторого кондитерского предприятия, выпускающего - карамель А; - карамель Б. При этом используется сырье – сахар; – джем; – шоколад.

Исходные данные для кондитерской Тогда после перехода к условным единицам получим таблицу

Математическая модель задачи Введем переменные единиц продукции выпускает предприятие; единиц продукции выпускает предприятие; Тогда математическая постановка задачи имеет вид:

Графическое решение 1. Строим ограничения – неравенства. 2. Строим линию уровня 3. Зададим const = 100. 4. Перенесем линию уровня параллельно в сторону увеличения ЦФ до пересечения с крайней вершиной многогранника ограничений

Геометрический метод решения ЗЛП Решим геометрическим методом задачу технического контроля:

Построив все ограничения-неравенства, получим множество допустимых решений – треугольник ABC. Построив все ограничения-неравенства, получим множество допустимых решений – треугольник ABC. Для построения ЦФ необходимо построить линию уровня для любой константы, например для 600.   Линия уровня попала в область допустимых решений. Теперь если изменять константу, то линия уровня будут перемещаться параллельно. Увеличиваем константу до тех пор, пока линия уровня не достигнет крайней вершины треугольника ABC - А.

Вершина треугольника А имеет координаты. Вершина треугольника А имеет координаты. Таким образом, для оптимальной работы ОТК необходимо использовать 8 контроллеров 1 разряда и 1.6 контроллеров 2 разряда. Значение1.6 означает или неполный рабочий день, или округление до двух контроллеров.

Частные случаи геометрических решений

Пример 1

Пример 2

Задача линейного программирования в стандартной форме

ЗЛП в стандартной форме содержит следующие элементы: ЗЛП в стандартной форме содержит следующие элементы: Ограничения только в виде равенств; Все переменные ограничены; Ресурсы ЦФ

Матрично–векторная запись где А – матрица коэффициентов; - вектор переменных; - вектор ресурсов - вектор оценок задачи линейного программирования.

Приведение ЗЛП к стандартному виду Преобразование неравенств Ограничения – неравенства можно преобразовать в равенства при помощи введения остаточных и избыточных переменных . Остаточные переменные вводятся со знаком «плюс», избыточные со знаком «минус».

Преобразования неравенств Пример 1 Добавим остаточную переменную   Пример 2 Добавим избыточную переменную  

Преобразования неравенств Преобразуем неравенства из задачи об использовании сырья добавив во все три уравнения остаточную переменную.

Приведение ЗЛП к стандартному виду Преобразование неограниченных по знаку переменных Переменные задачи линейного программирования в стандартной форме предполагаются только неотрицательными. Неограниченные переменные необходимо заменить разностью двух положительных переменных. Здесь . Переменные может быть положительным и отрицательным в зависимости от соотношения .

Приведение ЗЛП к стандартному виду Устранение отрицательных ресурсов Уравнения с отрицательными значениями ресурсов необходимо умножить на (-1).

Пример приведения ЗЛП к стандартному виду Дана следующая система: Переменная - неограниченна   Умножим на (-1) уравнение (3). Введем дополнительные переменные: остаточную в уравнение (1) и избыточную переменную в уравнение (2).

Перепишем задачу ЛП с учетом новых переменных и замен: Перепишем задачу ЛП с учетом новых переменных и замен:

Симплекс метод решения ЗЛП

Запишем задачу линейного программирования в стандартной форме в развернутом виде: Запишем задачу линейного программирования в стандартной форме в развернутом виде: Число уравнений системы меньше числа неизвестных (m < n).

Метод Гаусса – Жордана Основная идея метода состоит в сведении m уравнения с n неизвестными к каноническому или ступенчатому виду, путем линейных преобразования над строками (сложение строк и умножение на скаляр). Это позволяет привести СЛАУ к следующему виду:

Базисные и свободные переменные Переменные которые входят в одно уравнение с коэффициентом 1, а в остальные с коэффициентом 0 называют базисными (зависимыми). Переменные называют свободными (независимыми). В канонических системах в любом уравнении присутствует только одна базисная переменная.

Выразим из предыдущей системы базисные переменные: Выразим из предыдущей системы базисные переменные: Из этой системы можно получить решение для базисных переменных, присваивая независимым переменным произвольные значения

Базисное решение  

Метод последовательного исключения переменных (метод Гаусса) Метод Гаусса состоит из двух этапов: Прямой ход Обратный ход Цель прямого хода - приведение матрицы системы A к верхнетреугольному виду.

Прямой ход На каждом шаге преобразования выбирается k-я главная или ведущая строка. Диагональные элементы главной строки называются главными элементами На прямом ходе выполняется следующие действия: Для всех строк, кроме главной, находим множитель   К каждой неглавной добавляем главную строку, умноженную на множитель    

Прямой ход Главную строку делим на главный элемент ; Главную строку вычеркиваем, размерность системы становится меньше на единицу, то есть (n-1). На следующем шаге исключения главной строкой вновь становится верхняя строка, находящаяся под вычеркнутой на предыдущем шаге. Все указанные выше преобразования повторяются столько раз, пока главная строка не становится единственной в системе.

Обратный ход Вектор неизвестных СЛАУ находится в обратном порядке, начиная с последнего. Для этого составляется матрица из вычеркнутых строк, она имеет верхнетреугольный вид. Из последнего уравнения находится неизвестный , затем неизвестные находятся в порядке , , …, .

Пример решения СЛАУ методом Гаусса

Для уменьшения возможности ошибок счета вводятся контрольные суммы (столбец c ), с которыми выполняются следующие преобразования. Для уменьшения возможности ошибок счета вводятся контрольные суммы (столбец c ), с которыми выполняются следующие преобразования. на прямом ходе те же преобразования, что со столбцом свободных членов b. Контроль правильности преобразования строки на очередном шаге проводится суммированием всех коэффициентов в строке и свободного члена. Эти значения должны быть равны. на обратном ходе одновременно с вычислением корней ,вычисляются корни , которые получены если в выделенном в системе уравнении вместо свободного члена использовать значение контрольной суммы . Между корнями должно выполняться такое соответствие .

Метод главных элементов Применяется в случаях, когда главные диагональные элементы системы уравнений в результате преобразований получаются нулевые. В этих условиях схема единственного деления становится неработоспособной, так как на главные элементы в ходе преобразований производится деление.

Основная идея метода главных элементов На каждом шаге выбирают главный элемент матрицы А – максимальный по модулю коэффициент в матрице . Строка p – главная строка. Для всех строк, кроме главной, вычисляются множители:   К каждой неглавной строке добавляют главную, умноженную на сомножитель . В результате q-й столбец – нулевой. Вычеркиваем p-ю строку и q-й столбец. В результате получаем матрицу , размерность которой на единицу меньше предыдущей матрицы А. Процедуру повторяем с первого шага (n-1) раз.

Основная идея метода главных элементов В результате составляем новую систему уравнений из вычеркнутых строк. Полученная матрица не треугольного вида, как в схеме единственного деления Гаусса. Но каждое уравнение содержит разное количество неизвестных: в последнем уравнении – 1 неизвестное; в (n-1)-м –2 неизвестных и т.д.; в первом уравнении – все n неизвестных. Такой вид преобразованной системы позволяет последовательно находить неизвестные, начиная с последнего уравнения.

Пример решения СЛАУ методом Гаусса с выбором главного элемента

Симплекс метод Теорема 1 Множество опорных планов – выпукло Теорема 2 Если ЗЛП разрешима, то экстремум целевой функции достигается на одном из опорных планов (допустимом базисном решении). То есть оптимальное решение соответствует крайней точке выпуклого множества. Число опорных планов конечно и определяется числом

Алгоритм симплекс метода Выбор начального опорного плана. Переход от начального опорного плана к другому опорному плану с лучшим значением целевой функции. (!Смежному). Приведение системы, для смежного опорного плана к каноническому виду Продолжение поиска опорного плана улучшающего целевую функцию до достижения оптимального плана..

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

Составим симплекс – таблицу для задачи использования ресурсов. Составим симплекс – таблицу для задачи использования ресурсов. Для этого запишем - задачу в каноническом виде и заменим - цель поиска максимум на минимум.

Начальный опорный план

I. Нахождение начального опорного плана Переменные – входят только в одно уравнения, значит они базисные. Переменные - свободные. Свободные переменные могут принимать любые значения, но для удобства их принимают равным 0. Таким образом опорный план Целевая функция

II. Нахождение смежного опорного плана Необходимо одну переменную из свободных перевести в базис, так, чтобы целевая функция уменьшалась. Для удобства запишем ЗЛП в стандартной векторно-матричной форме:

Приращение целевой функции : Приращение целевой функции : Где свободным переменным (в нашем случае k=1, k=2) . – суммирование ведется только по базисным переменным. Приращения вычисляются только для свободных переменных:

Лемма 1 Если все приращения симплекс-плана , следовательно, текущий опорный план оптимальный. Следовательно улучшение целевой функции приносит та свободная переменная , приращение которой отрицательно Если есть несколько отрицательных , то для замены можно выбрать любую. Но обычно выбирают переменную с наименьшим

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

Выбранная для данного примера переменная меняется местами с .

III. Приведение системы к каноническому виду Так как переменную ввели в базис, то она должна в третьем уравнении иметь коэффициент равный единице, а во всех остальных нулю. Записав второй столбец , осуществим эквивалентные преобразования с первой строкой системы. К каждой неглавной строке добавляем главную, умноженную на коэффициент Где главный (ведущий) элемент. k- номер столбца ведущего элемента. p – строка ведущего элемента.

Шаг 1

Шаг 2

Шаг 3

Шаг 4

Полная симплекс таблица

Замечание Если на шаге I выбрать - разрешающим столбцом, то стратегия поиска такова:   Оптимум достигнут за 2 шага.

Метод искусственного базиса Пусть задача линейного программирования приведена к стандартному виду: Пусть все, но часть или все базисные переменные отрицательны, . Следовательно, опорного плана нет.

Дополним уравнения – ограничения искусственными переменными (предполагаем, что все ). Дополним уравнения – ограничения искусственными переменными (предполагаем, что все ). Введем m переменных (по количеству уравнений) , которые в новой системе будут базисными, а отрицательные уйдут в свободные. В результате получим следующую эквивалентную задачу:

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

Пример Перепишем ЗЛП в стандартной форме. Для этого введем дополнительные переменные , , и запишем задачу в канонической форме.

Так как часть базисных переменных отрицательны (), следовательно опорного плана нет. Так как часть базисных переменных отрицательны (), следовательно опорного плана нет. Для получения начального опорного плана введем переменные в двух первых уравнениях-ограничениях и сформулируем вспомогательную задачу: Таким образом, начальным базисом является:

Симплекс таблица с искусственным базисом

Симплекс таблица с искусственным базисом

Симплекс таблица с искусственным базисом

Для первых трех шагов приращения вычисляются только по искусственным переменным, которые входят в искусственную целевую функцию c коэффициентом . Для первых трех шагов приращения вычисляются только по искусственным переменным, которые входят в искусственную целевую функцию c коэффициентом . На третьем шаге искусственные переменные исключены, так как все положительны. Эквивалентная задача решена. Далее приращения вычисляются на основе исходной целевой функции.

Этапы метода искусственного базиса Формирование и решение вспомогательной задачи ЛП с введением искусственных переменных. Искусственные переменные в начальном опорном плане являются базисными. Искусственная целевая функция включает только искусственные переменные. При получении смежных опорных планов искусственные переменные из базисных переводим в свободные. В результате получен оптимальный опорный план для вспомогательной задачи .

Этапы метода искусственного базиса Оптимальный опорный план вспомогательной задачи ЛП является начальным опорным планом основной задачи ЛП. Задача решается для исходной целевой функции обычным симплекс – методом

Введение искусственных переменных требуется в двух случаях: Введение искусственных переменных требуется в двух случаях: Ряд базисных переменных в канонической форме отрицательны; если трудно свести к канонической форме, то просто в любое уравнение-ограничение добавляем искусственную переменную.

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

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

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

Теорема 1 Если существует оптимальный план одной задачи, то и существует оптимальный план другой, при этом справедливо неравенство Неравенство переходит в равенство если и оптимальны.

Теорема 2 Если – оптимальные планы то компоненты планов связаны соотношениями:

Сравнение прямой и двойственной задачи

Матрица ограничений В исходной задаче

Число ограничений и переменных В исходной задаче

Правые части ограничений – это коэффициенты целевой функции двойственной задачи

Знаки ограничений и цель задачи меняются на противоположные В исходной задаче

Соответствие двойственных задач ЛП

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

Симплекс таблица двойственной задачи

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

Подставив оптимальные значения вектора , получим оптимальные значения вектора Подставив оптимальные значения вектора , получим оптимальные значения вектора Получен тот же оптимальный план что и при решении прямой задачи (см. слайд 25 «Задача об использовании сырья»)

Экономическая трактовка двойственности Если прямую задачу: рассматривать, как задачу об использовании сырья (ресурсов), то параметры задачи имеют следующий экономический смысл.

Экономический смысл переменных В прямой задаче: – количество единиц j-го продукта; – стоимость единицы j-го продукта; – ресурс(запас) i-го сырья; В двойственной: – стоимость единицы i-го сырья;

Тогда стоимость всех ресурсов Тогда стоимость всех ресурсов А стоимость всех затраченных ресурсов, идущих на выпуск единицы j-ой продукции не меньше окончательной стоимости этого продукта

Если коэффициенты ограничений понимается как ресурсы, то с точки зрения предприятия эти ресурсы имеют определенную ценность. Если коэффициенты ограничений понимается как ресурсы, то с точки зрения предприятия эти ресурсы имеют определенную ценность. Любой вид ресурса обладает некоторой «теневой ценой», определяющей ценность данного ресурса для получения предприятием дохода, равного разности (прибыль – затраты). А под оптимальным планом понимается отношение Определение оптимальных «теневых цен» – основная цель двойственной задачи.