Общая задача линейного программирования

Дана система m линейных уравнений и неравенств с n переменными

 

,

………………………….

,                                                                      (1)

,

,

…………………………..,

где .

и линейная функция

,                                               (2)

где .

необходимо найти такое решение системы  где

                                            (3)

при котором линейная функция f (1) принимает оптимальное значение.

Система (1) называется системой ограничений, а функция f – линейной функцией.

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

4.1. Основные определения

Любые m переменных системы m линейных уравнений с n переменными  называются основными или базисными, если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные  переменных называются неосновными.

Теорема 1. если для системы m линейных уравнений с n переменными  ранг матрицы коэффициентов при переменных равен m, т.е. существует хотя бы одна группа основных переменных, то эта система является неопределенной, причем каждому произвольному набору значений неосновных переменных соответствует одно решение системы.

Базисным решением системы m линейных уравнений с n переменными называется решение, в котором все  неосновных переменных равны нулю.

Угловая точка – точка множества, которая не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.

Теорема 2. если задача линейного программирования имеет оптимальное решение, то линейная функция принимает максимальное значение в одной из угловых точек многогранника решений. Если линейная функция принимает максимальное значение более, чем в одной угловой точке, то она принимает его в любой точке, являющейся выпуклой комбинацией этих точек.

Оптимум линейной функции задачи линейного программирования следует искать среди конечного числа ее допустимых базисных решений.

Пример решения задачи линейного программирования

Задача 1. (об использовании ресурсов).

Для изготовления двух видов продукции р₁ и р₂ используют четыре вида ресурсов s₁, s₂, s₃, s₄. запасы ресурсов, затрачиваемых на производство единицы продукции, приведены в таблице 1.

Таблица 1

Вид ресурса	№запас ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
		р1	р2
s1	18	1	3
s2	16	2	1
s3	5	-	1
s4	21	3	-

 

Прибыль, получаемая от единицы продукции р₁ и р₂ – соответственно 2 и 3 руб. Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

Геометрический метод решения. Составим экономико-математическую модель задачи. Обозначим  - число единиц продукции соответственно  и , запланированных к производству. Для их изготовления потребуется  единиц ресурса ,  единиц ресурса s₂,  единиц ресурса  и  единиц ресурса . Так как потребление ресурсов s₁, s₂, s₃, s₄ не должно превышать их запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

 

,

,                                                                                                  (4)

,

.

по смыслу задачи переменные

х₁³0, х₂³0                                                                                        (5)

суммарная прибыль f составит  руб. от реализации продукции  и  руб. - от реализации продукции р₂, т.е.

                                                                                     (6)

итак, экономико-математическая модель задачи: найти такой план выпуска продукции , удовлетворяющий системе (4) и условию (5), при котором функция (6) принимает максимальное значение:

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

(i)

(ii)

     (iii)

(iv)

  (v,vi)                                                                                     

Изобразим многоугольник решений на рис. 1

Рис. 1.

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

 

откуда , т.е. С (6;4).

Максимум (максимальное значение) линейной функции равен .

Итак,  при оптимальном решении , т.е. максимальная прибыль в 24 руб. может быть достигнyта при производстве 6 единиц продукции р₁ и 4 единиц продукции р₂.