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