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

Лекция 3. Симплекс-метод решения задач линейного программирования 1. Построение математической модели 2. Алгоритм симплекс-метода 3. Пример решения ЗЛП симплекс-методом 4. Решение ЗЛП в среде MS EXCEL 1. Построение математической модели Линейное программирование предусматривает построение математической модели рассматриваемой задачи. Задачи линейного программирования решаются графическим методом, симплексным методом, а также можно решить задачи с помощью инструментов MS Excel. Построение математической модели – наиболее сложная часть линейного программирования. Рассмотрим пример построения математической модели линейного программирования Предприятие выпускает два вида продукции: Изделие 1 и Изделие 2. На изготовление единицы Изделия 1 требуется затратить а11 кг сырья первого типа, a21 кг сырья второго типа, a31 кг сырья третьего типа. На изготовление единицы Изделия 2 требуется затратить а12 кг сырья первого типа, a22 кг сырья второго типа, a32 кг сырья третьего типа. Производство обеспечено сырьем каждого типа в количестве b1 кг, b2 кг, b3 кг соответственно. Рыночная цена единицы Изделия 1 составляет c1 тыс. руб., а единицы Изделия 2 – c2 тыс.руб. Исходные данные для решения задачи: Показатели Затраты Количество сырья на первое Изделие на второе Изделие Сырьё первого типа 2 7 560 Сырьё второго типа 3 3 300 Сырьё третьего типа 5 1 332 Цена единицы Изделия 55 35 а11 = 2 а12 = 7 b1 = 560 c1 = 55 а21 = 3 а22 = 3 b2 = 300 c2 = 35 а31 = 5 а32 = 1 b3 = 332 Требуется: 1) построить экономико – математическую модель задачи; 2) составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи графического метода решения задачи линейного программирования. 3) составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи табличного симплекс – метода решения задачи линейного программирования. 4) составить план производства изделий, обеспечивающий максимальную выручку от их реализации. Для решения задачи ЛП составим Математическую модель задачи. Обозначение переменных задачи В задаче требуется определить оптимальное число изделий каждого вида, обеспечивающее максимальную прибыль от их реализации, а значит, переменными задачи являются количество каждого вида изделий: x1 – количество изделий вида 1; x2 – количество изделий вида 2. Целевая функция задачи Критерием эффективности служит параметр прибыли, который должен стремиться к максимуму. Чтобы рассчитать величину прибыли от реализации изделий, необходимо знать: • выпускаемое количество изделий каждого вида, т.е. x1 и x2 ; • прибыль от их реализации – согласно условию, соответственно 55 и 35 тыс. руб. Таким образом, прибыль от реализации выпускаемых изделий вида 1 равна 55*x1 тыс.руб., а от реализации изделий вида 2 – 35*x2 тыс.руб. Поэтому запишем ЦФ в виде суммы прибыли от продажи каждого из видов изделий: Z (x) = 55 x1 + 35 x2 → max Ограничения Возможное оптимальное количество изделий каждого вида x1 и x2 ограничивается следующими условиями: • Заданными ресурсами - b1, b2 и b3, которые используются на выпуск каждого вида изделия, не могут превышать общего запаса ресурсов; • количество каждого вида изделия не может быть отрицательным. Запишем эти ограничения в математической форме: по расходу ресурса 1: 2 x1 + 7 x2 ≤ 560, по расходу ресурса 2: 3 x1 + 3 x2 ≤ 300, по расходу ресурса 3: 5 x1 + x2 ≤ 332 не отрицательность количества выпускаемых изделий задаётся так: х1 ≥ 0 х2 ≥ 0 Таким образом, математическая модель этой задачи имеет вид Z (x) = 55 x1 + 35 x2 → max 2 * х1 + 7 * х2 ≤ 560 3 * х1 + 3 * х2 ≤ 300 5 * х1 + х2 ≤ 332 х1 ≥ 0 х2 ≥ 0 2. Алгоритм симплекс-метода Симплексный метод – это метод последовательного улучшения плана. Этим методом можно решать задачи линейного программирования с любым количеством переменных и ограничений. Этот метод включает в себя три основные этапа: 1) Построение начального опорного плана. 2) Правило перехода к лучшему (точнее, нехудшему) решению. 3) Критерий проверки найденного решения на оптимальность. При симплексном методе выполняются вычислительные процедуры (итерации) одного и того же типа в определенной последовательности до тех пор, пока не будет получен оптимальный план задачи или станет ясно, что его не существует. 1) Построение начального опорного плана Данную задачу линейного программирования необходимо сначала привести к каноническому виду; при этом правые части ограничений должны быть неотрицательными (если они отрицательные, то необходимо умножить соответствующу строку на - 1). Признаком возможности построения начального опорного плана служит наличие в каждом ограничении-равенстве с неотрицательной правой частью базисной переменной. Для этого в каждом ограничении слева добавим положительную переменную х3 , х4 , х5 соответственно запишем канонический вид задачи: Z (x) = 55 x1 + 35 x2 + 0 х3 + 0 х4 + 0 х5→ max 2 * х1 + 7 * х2 + х3 = 560 3 * х1 + 3 * х2 + х4 = 300 5 * х1 + х2 + х5 = 332 х1 ≥ 0 х2 ≥ 0 Базисной называют дополнительную переменную, которая входит только в одно уравнение (а в другие не входит), и при этом имеет коэффициент, равный единице. Каждая дополнительная переменная имеет определённое экономическое содержание х3, х4, х5 - размеры недоиспользуемых соответствующих ресурсов b1, b2 и b3. Переменные х3, х4, х5 базисные. Приравниваем их к правым частям ограничений: х3 = 560, х4 = 300 , х5 = 332 Все остальные переменные – свободные, приравниваем их к нулю: х1 = 0, х2 = 0. Запишем теперь начальный опорный план Xопор = (х1, х2, х3, х4, х5) =(0, 0, 560, 300, 332) 2) Составление симплексных таблиц. Критерий оптимальности. Симплексный метод удобно применять, используя построение симплексных таблиц. Первая симплексная таблица, соответствующая начальному плану, имеет вид: Рисунок 1 (Таблица 1). Симплекс-Таблица В первой строке записана прибыль от продажи изделий. Столбец А - «Базис» – это базисные переменные. Столбец B - Cbi – это коэффициенты при базисных переменных в целевой функции. Столбец D - «Ресурсы» – правые части ограничений (ресурсы); В столбцах D, E, F, G, H записаны коэффициенты при переменных в ограничениях; В строке 6 (при х1, х2, значения со знаком минус) – коэффициенты при переменных в целевой функции. Алгоритм решения задачи симплекс-методом состоит из нескольких этапов. 1. В целевой строке выбираем наибольшую по модулю отрицательную оценку- это разрешающий столбец. 2. Далее находим оценочные отношения, путём деления значения столбца ограничений (ресурсов) - С на разрешающий столбец D, которые записываем в последний столбец таблицы, а затем из них (отношений) выбираем наименьшее число – получим разрешающую строку. 3. На пересечении разрешающей строки и разрешающего столбца расположен разрешающий элемент. 4. Разрешающую строку (Третью) строку делим на разрешающий элемент равный 5 и значения записываем в новой таблице в соответствующей строке. При этом в базис (столбик А) записываем соответствующую переменную – по разрешающему столбцу (в нашем случае х1). 5. Все остальные элементы таблицы пересчитываем по методу Гаусса (прямоугольника). Составляем вторую секцию таблицы. 6. Далее повторяем пункты 1-5 пока не получим оптимальный план. 7. Опорный план будет оптимальным тогда и только тогда, когда все оценки целевой строке будут ≥ 0 для задачи на max и ≤ 0 для задачи на min Далее переходим к решению задачи. Так как решаемая задача на нахождение максимального значения, то в индексной строке выбираем наибольшую по модулю отрицательную оценку – это столбец с переменной х1 (таблица 1). Выделяем его. Потом находим оценочные отношения, путём деления значения столбца С на столбец D, которые записываем в предпоследний столбец таблицы, из которых выбираем наименьшее из них – это 66,4 – третья строка. Выделяем её. На пересечении разрешающей строки и разрешающего столбца расположен разрешающий элемент (5). Третью строку делим на 5 и значения записываем в новой таблице. Из базиса выводим переменную х5, при этом в базис вводим переменную х1. Все невыделенные элементы пересчитываем по методу Гаусса. Составляем вторую секцию таблицы. В результате перейдём к таблице 2. Так как в индексной строке присутствует отрицательная оценка, план не является оптимальным. Требуется улучшение плана. Выделяем столбец с переменной х2. Далее находим оценочные отношения делением столбца С на столбец Е, среди которых наименьшее 42 - вторая строка. Выделяем её. Элементы строки 2 делим на 2,4. Из базиса выводим переменную х4 при этом в базис вводим переменную х2. Получим таблицу 3. Так как в индексной строке все оценки положительные или равны нулю, план оптимален: Z (x) = 55 x1 + 35 x2 Z (58, 42) = 55 x1 + 35 x2 = 55*58 +35 * 42 =4660 Можно проверить и решить графическим методом. 4. Решение ЗЛП в среде MS EXCEL Для решения рассмотренной задачи в среде Excel заполним ячейки исходными данными (в виде таблицы) и формулами математической модели. Excel позволяет получить оптимальное решение без ограничения размерности системы неравенств и целевой функции. Таблица в режиме чисел Таблица в режиме формул Здесь: В9:С9 – результат (оптимальное количество изделий каждого вида); В6:С6 – коэффициенты целевой функции; В10 – значение целевой функции; В3:С5 – коэффициенты ограничений; D12:D14 – правая часть ограничений; B12:B14 – вычисляемые (фактические) значения левой части ограничений. Решим задачу с помощью команды меню Сервис / Поиск решения. Итак, делаем активной ячейку B10. Выполняем команду Сервис / Поиск решения. На экране появляется диалоговое окно Поиск решения. В поле Установить целевую ячейку будет показана ссылка на активную ячейку, то есть на B10. Причём эта ссылка абсолютная (мы видим $B$10). В секции Равной: устанавливаем переключатель максимальному значению. Можно задать не только максимальное/минимальное значения, но и любую произвольную величину, введя её в специальное поле значению в секции Равной:. Ограничения устанавливаются с помощью кнопки Добавить, которая вызывает диалоговое окно их ввода Добавление ограничения В поле ввода Ссылка на ячейку: указывается адрес ячейки, содержащей формулу левой части ограничения. Затем выбирается из списка знак соотношения. В поле Ограничение: указывается адрес ячейки, содержащей правую часть ограничения. Щёлкаем на кнопку Добавить и повторяем для следующего ограничения. После ввода всех ограничений следует щёлкнуть кнопку ОК. Так как все переменные несут условие не отрицательности, то их положительность задаём через кнопку Параметры в окне диалога Поиск решения. После щелчка на ней, на экране окно Параметры поиска решения Устанавливаем флажки Линейная модель и Неотрицательные значения, соглашаясь с остальными установками по умолчанию. Щёлкаем на кнопке ОК. После этого произойдёт переключение в окно Поиск решения, в котором необходимо щёлкнуть кнопку Выполнить для решения поставленной задачи. Excel предъявит окно Результаты поиска решения с сообщением о том, что решение найдено, или о том, что не может найти подходящего решения. Если вычисления оказались успешными, Excel предъявит следующее окно итогов. Их можно сохранить или отказаться (Восстановить исходные значения). Кроме того, можно получить один из трёх видов отчётов (Результаты, Устойчивость, Пределы), позволяющие лучше осознать полученные результаты, в том числе, оценить их достоверность. После найденного решения, в ячейках В9:С9 появится оптимальное количество изделий каждого вида. Покажем это. При сохранении отчёта выбрали вид отчёта – Отчёт по результатам. Из отчёта видно, что ресурс 1 не используется полностью на 150 кг, а ресурсы 2 и 3 используются полностью. Получили оптимальный план, при котором изделий первого вида необходимо выпустить в количестве 58 шт., а изделий второго вида в количестве 42 шт. При этом прибыль от их реализации максимальная и составит 4660 тыс.руб.