Полезные материалы:

Примеры - Математическое программирование

Графический и симплекс метод

Для производства двух видов изделий А и В используются три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется в течении 1 часа, оборудование второго типа – 3 часа, оборудование третьего типа – 3 часа.

Для производства единицы изделия В оборудование первого типа используется в течении 2 часа, оборудование второго типа – 3 часа, оборудование третьего типа – 1 час.
На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 32 часа, оборудование второго типа – 60 часов, оборудование третьего типа – 50 часов.

Прибыль от реализации единицы готового изделия А составляет 4 денежные единицы, а изделия В – 2 денежные единицы.

Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации.
1) Составить математическую модель задачи

2) Решить графическим методом

3)Решить симплекс-методом путем преобразования симплекс-таблиц

Решение

Перед нами – классическая задача линейного программирования. Под планом производства понимается ответ на простой вопрос: сколько изделий А и сколько изделий В надо выпустить, чтобы прибыль была максимальна.
Прибыль рассчитывается по формуле: .

Запишем математическую модель задачи:

Чтобы проиллюстрировать применение симплекс-метода решения этой задачи, решим ее графически.
Для этого построим на плоскости  области, описываемые ограничениями-неравенствами, и прямую , которая называется целевой функцией.

         Три записанных выше неравенства ограничивают на плоскости многоугольник (построен красным цветом), ограниченный слева и снизу координатными осями (т.к. искомое количество изделий положительно).

         График целевой функции (построен синим цветом) передвигается в направлении, обозначенном стрелкой (по-научному – в направлении своего градиента), до тех пор, пока не достигнет граничной точки многоугольника – в нашем случае это точка – (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, т.е. возвращаясь к системе неравенств, получаем:

        Ответы, полученные различными методами, совпадают.



Учебники
Предлагаем наиболее хорошие на наш взгляд учебники для самостоятельного изучения математики и экономики Comment

Справочники
Компактные справочные материалы, формулы по различным разделам высшей математики и экономической статистики. Comment

Онлайн калькуляторы
Некоторые задачи можно решить онлайн, введя числовые значения, с подробным решением. Comment