Главный Учебник. Главный учебник МММ. Методические материалы по курсу экономикоматематическое моделирование
 Скачать 0.62 Mb.
|
Тема 2. Задачи линейного программирования (ЗЛП)Пример задачи 1. Решить ЗЛП графическим способом.  Требуется найти max L = x1 + 4x2, при ограничениях  Решение задачи: Запишем уравнения граничных прямых и построим их на плоскости x1ox2  EMBED CorelDRAW.Graphic.11  Рис. 1. Решение ЗЛП геометрическим способом Выделив область решения каждого неравенства системы ограничений, получим многоугольник допустимых решений ЗЛП. На рис. 1 видно, что областью допустимых решений является многоугольник ONAC. Построим основную прямую L = 0, то есть x1 + 4x2 = 0, проходящую через начало координат O (0,0) перпендикулярно вектору  . Перемещая прямую L = 0 в направлении вектора , находим максимальную точку A, в которой пересекаются прямые L2 и L3, и координаты которой: x1 = 3, x2 = 1. Минимальной точкой является точка начала координат. Итак, Omin (0,0), Amax (3;1). Тогда Lmin = 0, Lmax = 7 Пример задачи 2. Решить ЗЛП симплексным методом   х1 0; х2 0; х3 0.Решение задачи: Приведем данную ЗЛП к канонической форме. Запишем ограничения – неравенства в форме ограничений - равенств, для чего введем дополнительные переменные х4, х5, х6: 18х1 + 15х2 + 12х3 + х4 = 360, 6х1 + 4х1 + 8х3 + х5 = 192, 5х1 + 3х2 + 3х3 +х6 = 180, Составим симплекс – таблицу (табл. 11). В табл. 11 (итерация 0) имеем базисное решение Б1 (0; 0; 0; 360; 192; 180). Данное решение не оптимально, т.к. при F  max коэффициенты в строке оценок целевой функции должны быть положительны – условие оптимальности задачи.Исключаем переменные, содержащие в строке оценок F отрицательные коэффициенты. Допустим, это будет переменная х3. Для выбора разрешающего элемента (с целью получения неотрицательных решений) используется правило симплекс – преобразования: для всех положительных элементов столбца исключаемой переменной х3 вычисляется отношение свободного члена строки к ним самим, т.е bi/aij. Выбирается наименьшее из отношений, а соответствующий ему коэффициент aij - за разрешающий элемент. Таблица 11
Наименьшее отношение дает коэффициент  , который выбирается за разрешающий элемент.Для пересчета таблицы относительно этого разрешающего элемента используется следующий порядок: 1) Разрешающая строка (вторая) делится на разрешающий элемент a23 . 2) Разрешающий столбец (третий) записывается в виде нулей, кроме разрешающего элемента а23 , т.е. переменная х3 исключается из остальных строк, включая строку оценок целевой функции F. 3) Все остальные строки и столбцы таблицы пересчитываются по правилу прямоугольника. Суть его состоит в том, что пересчитываемый элемент аi,j всегда составляет с разрешающим а23 диагональ прямоугольника и весь расчет производится по диагоналям этого прямоугольника по следующей схеме (если пересчитывается а11 ):  ,По данной схеме рассчитываются все элементы таблицы, включая строку целевой функции и столбец свободных членов. Результаты пересчета представлены в табл. 11 (первая итерация), новое базисное решение Б2 = (0; 0; 24; 72; 0; 108). Целевая функция F = 384. Однако это решение не оптимально, т.к. в строке оценок целевой функции F имеется отрицательный элемент (при переменной х2). Следовательно, на новом шаге итерации необходимо исключить переменную х2, а за разрешающий элемент взять  = 9, т.к. он дает наименьшее отношение bi/aij.Пересчитывается таблица относительно разрешающего элемента a22, результаты пересчета представлены в табл. 11 (итерация 2). Все коэффициенты в строке оценок целевой функции положительны. Следовательно, решение оптимально. Базисное решение (оптимальное) Б3 = (0; 8; 20; 0; 0; 96). Целевая функция F = 400. |