Симплекс метод. Задача Для производства двух видов изделийАиВ используются три типа технологического оборудования. Для производства единицы изделия а оборудование первого типа используется в течении 1 часа, оборудование второго типа 3 часа, оборудование третьего типа 3 часа.
![]()
|
Задача Для производства двух видов изделий А и В используются три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется в течении 1 часа, оборудование второго типа – 3 часа, оборудование третьего типа – 3 часа. Для производства единицы изделия В оборудование первого типа используется в течении 2 часа, оборудование второго типа – 3 часа, оборудование третьего типа – 1 час. На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 32 часа, оборудование второго типа – 60 часов, оборудование третьего типа – 50 часов. Прибыль от реализации единицы готового изделия А составляет 4 денежные единицы, а изделия В – 2 денежные единицы. Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации. Решить задачу симплекс-методом путем преобразования симплекс-таблиц. Дать геометрическое истолкование задачи, используя для этого ее формулировку с ограничениями – неравенствами. Решение. Перед нами – классическая задача линейного программирования. Под планом производства понимается ответ на простой вопрос: сколько изделий А и сколько изделий В надо выпустить, чтобы прибыль была максимальна. Прибыль рассчитывается по формуле: ![]() Запишем математическую модель задачи: ![]() Чтобы проиллюстрировать применение симплекс-метода решения этой задачи, решим ее графически. Для этого построим на плоскости ![]() ![]() Три записанных выше неравенства ограничивают на плоскости многоугольник (построен красным цветом), ограниченный слева и снизу координатными осями (т.к. искомое количество изделий положительно). График целевой функции (построен синим цветом) передвигается в направлении, обозначенном стрелкой (по-научному – в направлении своего градиента), до тех пор, пока не достигнет граничной точки многоугольника – в нашем случае это точка – (15 ; 5). В этой точке целевая функция будет достигать максимума. ![]() ![]() А теперь решим эту задачу симплекс-методом. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам, введя дополнительные переменные ![]() ![]() ![]()
Симплекс-таблица составляется так: В графе Базис записываются вектора переменных, принимаемые за базисные. На первом этапе это – A3, A4, A5. Базисными будут переменные, каждая из которых входит только в одно уравнение системы, и нет такого уравнения, в которое не входила бы хотя бы одна из базисных переменных. В следующий столбец ![]() Под столбцом свободных членов записывается начальная оценка ![]() Остальные оценки записываются под столбцами соответствующих векторов ![]() ![]() ![]() ![]() Следует отметить, что оценки для базисных векторов всегда равны нулю. Преобразование симплекс-таблицы ведется следующим образом: Шаг 1: Проверяется критерий оптимальности, суть которого состоит в том, что все оценки ![]() Шаг 2: Для отрицательных оценок вычисляются величины: ![]() ![]() ![]() ![]() Из этих элементов выбирается тот, для которого вычисленное произведение минимально, в нашем случае ![]() Шаг 3: Третья строка таблицы делится на 3 и вычитается из первой и второй строк. В сущности, применяется метод исключения неизвестных, известный как метод Жордана – Гаусса. Таким образом, новыми базисными переменными становятся A3, A4, A1. Возвращаемся к шагу 1 и повторяем весь процесс. Под столбцом свободных членов записывается начальная оценка ![]() Остальные оценки записываются под столбцами соответствующих векторов ![]() ![]() ![]() ![]() Следует отметить, что оценки для базисных векторов всегда равны нулю. Опять проверяется критерий оптимальности. Отрицательная оценка только одна – в столбце А2. Вычисляем: ![]() Разрешающим элементом будет второй элемент второго столбца – 2/3. Новыми базисными переменными становятся A3, A2, A1 Делим вторую строку на 2 и вычитаем из третьей. Умножаем вторую строку на 5/2 и вычитаем из первой. ![]() ![]() ![]() ![]() ![]() ![]() На этот раз отрицательных оценок нет, т.е. критерий оптимальности выполнен. Таким образом, получается искомое значение целевой функции F(15; 5; 7; 0; 0) = 70, т.е. возвращаясь к системе неравенств, получаем: ![]() Ответы, полученные различными методами, совпадают. |