Тема 2.4. Задача линейного программирования для n переменных

Цель изучения темы:  знать формулировку задачи линейного программирования для N переменных

• задача линейного программирования для N переменных

• симплекс - метод решения

Рассмотрим задачу формирования плана производства.

Некоторое предприятие может выпускать определённый набор продукции. Нормы затрат известны. Требуется построить производственный план, учитывающий ограниченность ресурсов.

Формализация

n - число различных видов продукции.

m - число различных ресурсов.

aij - объём i-того ресурса, который расходуется на производство одной единици j-того вида продукции i=1..m, j=1..n.

Xj - объем (количество единиц) j-того вида продукции в производственном плане предприятия (j от 1 до n).

Необходимо определить нормы выпуска каждого вида продукции, чтобы прибыль от её реализации была максимальной.

Построение экономико-математической модели

Прибыль обозначим F, тогда F=c₁X₁+c₂X₂+...+c_nX_n->=max

Составим ограничения для первого ресурса:

а₁₁ - объем первого ресурса, который расходуется на производство одной единицы первого вида продукции;

а₁₁Х₁ - объём первого ресурса, который требуется на изготовление Х₁ единиц первого вида продукции;

а₁₂Х₂ - объём первого ресурса, который требуется на изготовление Х₂ единиц второго вида продукции;

а_1nХ_n - объём первого ресурса, который требуется на изготовление Х_n единиц n-ого вида продукции;

а₁₁Х₁+a₁₂X₂+...+a_1nX_n - объём первого ресурса, который требуется на изготовление продукции, следовательно, мы имеем следующее ограничение:

а₁₁Х₁+а₁₂+...+а_1nX_n<=b1

Аналогично для остальных ресурсов:

а₂₁Х₁+а₂₂+...+а_2nX_n<=b₂

а₃₁Х₁+а₃₂+...+а_3nX_n<=b₃

...

а_m1Х₁+а_m2+...+a_mnX_n<=b_m

Кроме того, количество выпущенной продукции не может быть отрицательной, следовательно, Х₁>= 0, X₂>=0, ...,X_n>=0.

Таким образом, получаем следующую экономико-математическую модель задачи линейного программирования:

Рисунок 2.4.1.

Задачу линейного программирования для N (любое целое число) переменных можно представить в следующем виде:

Рисунок 2.4.2.

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

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

Двумерные задачи линейного программирования решаются графически. Для случая N=3 можно рассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.

В общем виде, когда в задаче участвуют N-неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в n-мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах. Решить данные задачи графически, когда количество переменных более 3 весьма затруднительно. Существует универсальный способ решения задач линейного программирования, называемый симплекс-методом .

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

Так как симплекс-метод довольно труден мы не будем его рассматривать более подробно.