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

Решение ЗЛП графическим методом.Теорема 1 «О представлении точек выпуклого ограниченного множества» Любая точка выпуклого ограниченного множества может быть представлена в виде выпуклой комбинации его угловых точек.Теорема 2. Точку допустимого множества D канонической ЗЛП можно считать его угловой точкой, когда оная является опорным решением системы ограничений данной ЗЛП.Теорема 3. Если в задаче минимизации z ограничена снизу на множестве D, а целевое множество D ≠ Ø, то ЗЛП имеет решение на множестве D.Теоремы 1, 2, 3 подводят к Теореме 4, дающей основное свойство ЗЛП.Теорема 4. Если ЗЛП имеет решение, то оптимальное значение целевой функции достигается по крайней мере в одной из угловых точек множества D.На Теореме 4 основан графический метод решения ЗЛП. Графический метод пригоден в случае: n – m = 2.В нашем случае n = 5, m = 3. Подставляем: 5 – 3 = 2.Равенство соблюдается, следовательно, данную ЗЛП возможно решить графическим методом.При решении ЗЛП первым способом будем рассматривать систему ограничений для базиса : Уменьшаем размерность системы ограничений, выражая базисные переменные через свободные: Получили новую систему ограничений:x10-2x2-20x105x220 x101x2-10.Найдем координаты точки Е: Прямая z(x) = const пересекает в последний раз область D в точке А(0;0). В этой точке функция достигает максимального значения...Вычисленные значения соответствуют найденным ранее значениям минимума и максимума функции, решение графическим способом выполнено верно.При решении ЗЛП вторым способом будем рассматривать систему ограничений для базиса : Уменьшаем размерность системы ограничений, выражая базисные переменные через свободные: Получили новую систему ограничений:x20-1x510x203x530 x108/7x2-40.Найдем координаты точки D: Найдем координаты точки В:..Вычисленные значения соответствуют найденным ранее значениям минимума и максимума функции, решение графическим способом выполнено верно.4. Решение ЗЛП двухфазным симплекс-методом.Для выполнения симплекс метода, необходимо знать следующие теоремы:Теорема 1. Критерий оптимальности основного опорного плана. Если все содержащиеся в индексной строке Δk ≤ 0, то основной опорный план ЗЛП – оптимальный план; а Δ0 – оптимальное решение целевой функции 𝑓(𝑥̅опт).Теорема 2. Если в индексной строке есть Δk > 0, а в столбце над ней не содержится ни одного положительного элемента, то данная ЗЛП не имеет решения; целевая функция 𝑓 является неограниченной на данном множестве.Теорема 3. Если в индексной строке симплексной таблицы есть Δk > 0, а в столбце над ней есть хотя бы один положительный элемент, то возможно такое симплексное преобразование, что, при переходе к новому опорному плану, значение целевой функции 𝑓 не увеличится.Алгоритм симплекс-метода:Составляем первую симплексную таблицу.Проверка основного опорного решения на оптимальность – Теорема 1.Проверка задачи на ограниченность – Теорема 2.Симплексноепреобразование(улучшение основного опорного решения) по Теореме 3.Симплекс-метод применяется к ЗЛП с простейшей системой ограничений.Метод искусственного базиса выясняет наличие планов любой канонической задачи. В случае ее допустимости – заменяет ее систему ограничений на эквивалентную простейшую систему ограничений. Далее возможно решение эквивалентно простейшей системы ограничений обычным симплекс-методом.Алгоритм метода искусственного базиса (двухфазный симплекс-метод):Построение вспомогательной ЗЛП:Если ЗЛП не каноническая, то приводим ЗЛП к канонической форме, вводя дополнительные переменные.Преобразуем систему ограничений так, чтобы выполнялись условия положительности свободных членов.Если необходимо, то вводим искусственные переменные, чтобы привести систему ограничений к эквивалентной с единичным базисом.Составляем вспомогательную задачу, для которой задача минимизации новой функции S равна сумме искусственных переменных.Решение вспомогательной ЗЛП обычным симплекс-методом. Для начала найдем минимальное значение функции S. При этом возможны следующие случаи:Если Smin ≠ 0 и в индексной строке нет положительных оценок, то исходная ЗЛП не имеет решения.Если Smin ≠ 0 и среди базисных переменных нет искусственных переменных, то таблица, в которой вычеркнуты столбцы с искусственными переменными, определяет простейшую систему ограничений для решения исходной ЗЛП.Если Smin= 0 и среди базисных переменных есть искусственные, то тогда нужно выполнить жорданово исключение, выбирая по одному ведущему элементу в строках с искусственными переменными. Затем выводим искусственные переменные из базиса, при этом индексные строки и столбцы не изменяются.Заменяем систему ограничений исходной задачи на эквивалентную простейшую, после решаем исходную ЗЛП обычным симплекс-методом