![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Понятие о симплексном методе
Симплексный метод (симплекс-метод) является одним из универсальных методов решения линейнойоптимизационной модели. Его называют так же методом последовательного улучшения плана. Рассмотрим линейнуюоптимизационную модель с системой ограничений в канонической форме записи:
Из теоремы: «Линейная функция, определенная на выпуклом n‑ мерном многограннике, достигает наибольшего значения в вершине этого многогранника. Если линейная функция достигает наибольшего значения более чем в одной вершине, то она достигает такого же значения в любой точке, являющейся выпуклой линейной комбинацией этих вершин» следует, что оптимальный план задачи (2.1)-(2.3) является одним из опорных решений системы (2.2). Это опорное решение, применяя симплекс-метод, мы и ищем, переходя от одного опорного решения к другому, при условии, что значение функции (2.1) возрастает (не убывает). Суть метода: предположим, что в системе (2.2) m < n и все m уравнений линейно независимы: r = m < n. Тогда система (2.2) имеет бесконечное множество решений. Разрешаем систему (2.2) относительно базисных неизвестных
и подставляя значения
Отметим, что значения базисных переменных Пусть в (2.4) все Опорный план С геометрической точки зрения, перебор опорных планов Построение начального опорного плана Первым шагом симплексного метода является построение начального опорного плана. Для этого систему ограничений приводят к предпочтительному виду. Система ограничений имеет предпочтительный вид, если: 1) ограничения заданы в виде равенств; 2) правые части (системы ограничений) (2.2) неотрицательны, т. е. 3) если левая часть ограничения равенства содержит переменную, входящую с коэффициентом, равным единице, то в остальные ограничения равенства эта переменная входит с коэффициентом, равным нулю. Например, в системе ограничений:
первое и второе ограничения имеют предпочтительный вид, третье – нет. Если каждое ограничение (2.2) имеет предпочтительный вид, то ее опорное решение (базисное с неотрицательными координатами) строится следующим образом: все переменные, кроме предпочтительных, приравниваются к нулю. Тогда предпочтительные переменные будут равны правым частям. Полученный план будет иметь не более m отличных от нуля координат (число ненулевых координат равно рангу системы ограничений) и полученный план будет опорным. Предпочтительные переменные – это базисные переменные, другие переменные, которые приравниваем нулю – это свободные неизвестные. Как же приводится система ограничений к предпочтительному виду? 1) Если система ограничений имеет вид:
то прибавив к левым частям дополнительные переменные
имеет предпочтительный вид. Начальный опорный план имеет вид:
В целевую функцию дополнительные переменные вводятся с коэффициентами равными нулю: 2) Если система ограничений имеет вид:
то вычитая из левых частей неотрицательные дополнительные переменные 3) Если исходная линейнаяоптимизационная модели имеет вид:
и если ни одно из ограничений не имеет предпочтительного вида, то М ‑ модель запишется в виде:
где знак «–» в (2.10) относится к модели на максимум. Начальный опорный план М ‑ задачи, которая имеет предпочтительный вид, запишется:
Если в оптимальном плане М ‑ модели: Является оптимальным для исходной модели. Если же хотя бы одна из искусственных переменных Так как исходную модель можно представить в предпочтительном виде, то будем считать, что линейнаяоптимизационная модель имеет предпочтительный вид:
Разрешая систему (2.14) относительно базисных переменных
Так как Для решения линейнойоптимизационной модели вручную условия заносят в таблицу, которая называется симплексной. Перед заполнением таблицы систему ограничений приводят к эквивалентному предпочтительному виду. В столбце БП записываются базисные переменные (т.е. предпочтительные) для каждого из ограничений равенств, в столбец Таблица 2.1
или
Признак оптимальности опорного плана Снова рассмотрим линейную оптимизационную модель в предпочтительном виде:
Пусть эта задача решается на максимум. Начальный опорный план Если для всех j Для определения переменной, подлежащей исключению из базиса, составляются отношения свободных членов к положительным элементам разрешающего столбца (такие отношения называются симплексными). Наименьшее симплексное отношение и определяет строку (разрешающую), содержащую исключаемую переменную. Выбор переменной, исключаемой из базиса, но min симплексному отношению гарантирует положительность базисных компонент в новом опорном плане. Значение новой базисной переменной Установим правила, по которым осуществляется преобразование условий модели от одного базиса к другому. В каждом уравнении системы ограничений, где коэффициент
Затем
и подставляем (2.16) во все остальные уравнения системы ограничений. Коэффициент Подставив (2.16) во все остальные уравнения системы ограничений, выражаем через новый набор свободных переменных остальные базисные переменные. Выполнив преобразования, получим:
Обозначив
получим следующую систему равенств:
Приведение системы
к новому базису называется симплексным преобразованием. В результате получим симплексную таблицу 2.2: Таблица 2.2
Полагая в равенствах (2.16) и (2.18) свободные переменные
Сформулируем правила перехода к новому опорному плану: 1) выбираем разрешающий элемент 2) разрешающий элемент заменяем обратной величиной 3) остальные элементы разрешающей строки 4) остальные элементы разрешающего столбца 5) все другие элементы симплексной таблицы вычисляются по правилу прямоугольника, вершинами которого служат разрешающий
Таким образом, симплекс-метод представляет собой процесс направленного решения системы линейных уравнений – ограничений задачи с особым правилом выбора разрешающего элемента, обеспечивающим движение по опорным решениям (правило выбора разрешающей строки) и монотонный рост линейной функции цели (правило выбора разрешающего столбца). Сформулируем теоремы, в которых определяются условия оптимальности планов, бесконечности оптимальных планов, неограниченности целевой функции. Теорема 2.1. Если для некоторого опорного плана, при решении модели на максимум, все элементы в индексной строке последней симплексной таблицы неотрицательны, то такой план оптимальный. Теорема 2.2. Если для некоторого опорного плана, при решении модели на минимум, все элементы в индексной строке последней симплексной таблицы не положительны, то такой план оптимальный. Теорема 2.3. Если в индексной строке последней симплексной таблицы, содержащей оптимальный план, имеется хотя бы один нулевой элемент, соответствующий свободной переменной, то линейная оптимизационная модель имеет бесконечное множество оптимальных планов; если же все элементы положительны (отрицательны), то оптимальный план единственный. Теорема 2.4. Если в индексной строке симплексной таблицы, при решении модели на максимум, имеется отрицательный элемент, а в соответствующем столбце нет ни одного положительного элемента, то целевая функция не ограничена сверху на множестве допустимых планов. Теорема 2.5. Если в индексной строке симплексной таблицы, при решении модели на минимум, имеется положительный элемент, а в соответствующем столбце нет ни одного положительного элемента, то целевая функция не ограничена снизу на множестве допустимых планов. Пример 2.1. Предприятие может изготовлять четыре вида продукции П Таблица 2.3
Необходимо: 1) определить план выпуска продукции, максимизирующий прибыль; 2) решить задачу с требованием комплектации, чтобы количество единиц третьей продукции было в 3 раза больше количества единиц первой; 3) выяснить оптимальный ассортимент при дополнительных ограничениях: первого продукта выпускать не менее 25 единиц, третьего – не более 30, второго и четвертого – в отношении 1: 3. Решение. Построим математическую модель задачи. Пусть
План удовлетворяет ограничениям: а) на трудовые ресурсы:
на полуфабрикаты:
на станочное оборудование:
условия неотрицательности:
б) дополнительное условие комплектации:
в) дополнительные условия:
Приведем вначале систему ограничений к предпочтительному виду, добавив к левым частям дополнительные переменные В расширенной задаче система ограничений
имеет предпочтительный вид. В целевую функцию дополнительные переменные вводятся с коэффициентами равными нулю: Заносим условия расширенной задачи в симплексную таблицу 2.4:
Таблица 2.4
Рассчитаем элементы индексной строки:
Так как Для определения переменной, подлежащей исключению из базиса, составляем отношения свободных членов к положительным элементам разрешающего столбца. В разрешающем столбце все элементы положительные: 100/2 =50; 260/4 = 65; 370/4 = 92, 5. Выбираем наименьшее, которое определяет первую строку в качестве разрешающей. Таким образом, разрешающим элементом будет «2». Строим новую симплексную таблицу 2.5: Таблица 2.5
Составляем отношения свободных членов к положительным элементам разрешающего столбца:
500/0, 75 = 66; 60/3 = 20; 170/70 = 24.
Так как отношение 60/3 = 20 – наименьшее, то третья строка разрешающая. Разрешающий элемент «3». Строим новую симплексную таблицу 2.6:
Таблица 2.6
Так как в
Х * = (0, 0, 35, 20, 0, 0, 30)
расширенной задачи - оптимальный. Задача имеет единственное решение:
так как в Лекция 3 Экономико-математические методы и модели оптимального планирования в промышленности, АПК (продолжение) Вопросы, изучаемые на лекции: 3.1. Понятие двойственности. Построение двойственных моделей оптимального планирования в промышленности, АПК 3.2. Соответствие между переменными пары взаимно двойственных линейных оптимизационных моделей 3.3. Теоремы двойственности Понятие двойственности. Построение двойственных моделей оптимального планирования в промышленности, АПК Каждой линейной оптимизационной модели можно поставить в соответствие другую линейную оптимизационную модель, называемую двойственной по отношению к первой. Так если в первой требуется найти максимум целевой функции Рассмотрим линейную оптимизационную модель в канонической форме записи: найти план
и который удовлетворяет ограничениям:
Двойственная модель формулируется следующим образом: найти план
и который удовлетворяет ограничениям:
В двойственной модели y Пусть линейная оптимизационная модель записана в симметрической форме: требуется найти план
и который удовлетворяет ограничениям:
Двойственная задача формулируется следующим образом: найти план
и который удовлетворяет ограничениям:
В рассмотренных парах двойственных моделей каждая из моделей может быть принята за исходную, тогда вторая будет двойственной. Установим связи между двойственными моделями: 1) упорядочим запись исходной модели: в задаче на максимум ограничения-неравенства должны иметь смысл ≤, в задаче на минимум − ≥. 2) если в прямой модели определяется максимум целевой функции, то в двойственной – минимум, и наоборот; 3) свободные члены ограничений прямой модели служат коэффициентами целевой функции двойственной модели, а коэффициенты целевой функции прямой модели служат свободными членами ограничений двойственной модели; 4) матрицей коэффициентов ограничений двойственной модели служит матрица, полученная транспонированием матрицы коэффициентов ограничений исходной модели; 5) каждому ограничению-неравенству прямой модели соответствует неотрицательная переменная двойственной модели, а каждому ограничению-равенству – переменная произвольного знака. 6) каждой неотрицательной переменной прямой модели соответствует ограничение-неравенство двойственной, а каждой произвольной переменной – ограничение-равенство. Пример 3.1. Пусть предприятие выпускает n видов продукции и использует при этом m различных видов ресурсов, объем которых ограничен величинами Тогда двойственная задача формулируется следующим образом: Пусть предприятие решило реализовать имеющиеся ресурсы, не выпуская готовую продукцию. При этом оно заинтересовано получить выручку не меньшую чем при изготовлении готовой продукции. Предприятие, которое закупает ресурсы, стремится к тому, чтобы общая стоимость ресурсов была минимальной. Поэтому необходимо установить оптимальные цены на ресурсы
|