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

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

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

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

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

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

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

Таблица №1

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

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

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

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

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

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

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

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

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

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

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

а₁₁x₁+а₁₂+...+а_1nx_n<=b₁

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

а₂₁x1+а₂₂+...+а_2nx_n<=b₂

а₃₁x1+а₃₂+...+а_3nx_n<=b₃

...

а_m1x₁+а_m2+...+a_mnx_n<=b_m

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

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

(2.1)

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

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

С помощью графического метода может быть решена задача линейного программирования, система ограничений которой содержит n неизвестных и m линейно независимых уравнений, если N и M связаны соотношением N – M = 2.

Действительно, пусть поставлена задача линейного программирования.

Найти максимальное значение линейной функции

Z = c₁х₁+c₂х₂+... +c_Nx_N

при ограничениях

a₁₁x₁ + a₂₂x₂ + ... + a_1NХ_N = b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2NХ_N = b₂

. . . . . . . . . . . . . . .

a_М1x₁ + a_М2x₂ + ... + a_МNХ_N = b_М

x_j ≥ 0 (j = 1, 2, ..., N)

где все уравнения линейно независимы и выполняется соотношение N - M = 2.

Используя метод Жордана-Гаусса, производим M исключений, в результате которых базисными неизвестными оказались, например, M первых неизвестных х₁, х₂, ..., х_M, а свободными — два последних: х_М+1, и х_N, т. е. система ограничений приняла вид:

x₁ + a_1,М+1x_М+1 + a_1NХ_N = b₁

x₂ + a_2,М+1x_М+1 + a_2NХ_N = b₂

. . . . . . . . . . . .

x_М + a_{М, М+1}x₂ + a_МNХ_N = b_М

x_j ≥ 0 (j = 1, 2, ..., N)

С помощью уравнений преобразованной системы выражаем линейную функцию только через свободные неизвестные и, учитывая, что все базисные неизвестные — неотрицательные: х_j ≥ 0 (j = 1, 2, ..., M), отбрасываем их, переходя к системе ограничений, выраженных в виде неравенств.