Графический метод решения задач линейного программирования с 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), отбрасываем их, переходя к системе ограничений, выраженных в виде неравенств.