.

     Понятия «жесткое неравенство», «размерность выпуклого многогранного множества», «грань», «ребро» при рассмотрении неоднородной системы линейных неравенств определяются аналогично случаю системы однородных неравенств.

     Неоднородные  системы линейных неравенств не обязательно являются совместными.

     Теорема. Система линейных неравенств АХ ≥ В совместна тогда и только тогда, когда из UA = 0 и U ≥ 0 следует, что UB ≤ 0 (U — неотрицательная строка длиной m).

     Доказательство. Если исходная система неоднородных неравенств совместна и Х — ее решение, то для любой строки U, определенной  в условии теоремы, справедливо UАХ ≥ UВ. Тогда при UA = 0 получаем требуемое UB ≤ 0. Для доказательства обратного надо показать, что для несовместной системы существует строка U такая, что UA = 0 и UB > 0.

     Для неоднородных систем справедливы следующие утверждения.

     1. Система линейных неравенств  АХ ≥ В совместна при любой правой части В тогда и только тогда, когда система уравнений UA = 0 имеет только тривиальное неотрицательное решение.

     2. Система линейных неравенств АХ ≥ В имеет неотрицательное решение Х ≥ 0 тогда и только тогда, когда из неравенств UA ≤ 0 и U ≥ 0 следует UB ≤ 0. [5, с. 123]

 

     2 Cпособы обозрения бесконечного множества решений систем линейных неравенств

     2.1 Метод построения  фундаментального  набора решений  для однородной системы линейных неравенств

     Набор из конечного числа решений  однородной системы

            (1)

называется  фундаментальным набором решений, если любое решение X этой системы может быть задано формулой , где — неотрицательные числа. В этом случае, следовательно, формула , в которой — любые неотрицательные числа, дает обозрение всех решений системы (1). Отсюда ясно, что нахождение фундаментального набора решений есть задача первостепенной важности при исследовании системы данной системы. Конечной целью наших построений и будет как раз являться выработка алгоритма, позволяющего с помощью весьма простых операций находить фундаментальный набор решений для любой системы (1). [1, с. 74]

     Рассмотрим  произвольную систему однородных линейных неравенств. Для первого неравенства системы можно построить фундаментальный набор решений. Присоединив к первому неравенству второе, можно построить фундаментальный набор решений для системы, состоящей из первых двух неравенств. Далее присоединяем третье неравенство и т. д., пока не получим фундаментальный набор решений для всей исходной системы неравенств. Этим доказано существование и одновременно указан способ построения фундаментального набора решений.

     Разумеется, если в данной системе неравенств имеется подсистема, для которой сразу можно указать фундаментальный набор решений, то в качестве исходного пункта следует взять эту подсистему; присоединяя к ней последовательно остальные неравенства, мы после ряда шагов построим искомый фундаментальный набор. Рассмотрим вышесказанное на конкретном примере. Для системы

           (2)

требуется найти все неотрицательные решения, т. е. все решения, удовлетворяющие условиям

             (3)

     Иначе говоря, нужно найти общее решение  системы (2), (3). Нетрудно видеть, что для системы (3) фундаментальным набором будет являться набор из точек

     

(действительно, любое решение системы (3) представимо в виде ). Присоединим к системе (3) первое из неравенств (2) и для полученной таким образом системы построим фундаментальный набор решений. Для удобства вычислений составим такую таблицу:  

Таблица 2.1 — Фундаментальные точки и значения функции L₁(X) в этих точках

 

     Примечание  — Источник: [1, с. 82]

     В каждой строке таблицы указана одна из фундаментальных точек для системы (3), а также значение функции L₁(X) для этой точки. Из таблицы видно, что единственной точкой типа является Х₃, точки типа суть Х₁ Х₂, Х₄, а точек типа в данном случае нет.

     Находим точки типа . Ими будут:

     

     Чтобы не усложнять дальнейших записей, обозначим  эти точки Y₁, Y₂, Y₄ (соответственно), а вместо Х₃ будем писать Y₃.

     Точки Y₃, Y₁, Y₂, Y₄ образуют фундаментальный набор решений для системы, состоящей из (3) и первого из неравенств (2).

     Присоединяем  к этой системе второе из неравенств (2) и составляем следующую таблицу: 

Таблица 2.2 — Фундаментальные точки и значения функции L₂(Y) в этих точках

 

     Примечание  — Источник: [1, с. 83]

     Из  таблицы видно, что роль точек  теперь играют Y₁, Y₂, роль точек играют Y₃, Y₄, а точек типа нет.

     Находим точки типа :

     

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

     

где a, b, c, d, e, f — какие угодно неотрицательные числа.

     Если  положить а = k₁, b = k₂, 5c = k₃, 5d = k₄, 5e = k₅, 5f = k₆, то получим для Х представление

                             (4)

где k₁, k₂, ..., k₆ — произвольные неотрицательные числа. [1, с. 83]

     2.2 Метод построения  фундаментального  набора решений  для неоднородной  системы линейных неравенств

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

           (5)

— произвольная система линейных неравенств с n неизвестными . Рассмотрим наряду с ней однородную систему

           (6)

с n+1 неизвестными . Между решениями систем (5) и (6) имеется определенного рода связь. А именно, если — какое-либо решение системы (6), причем t > 0, то числа

            (7)

будут составлять решение системы (5). [1, с. 84] В самом деле, рассмотрим, например, первое из неравенств (6). Оно выполняется для чисел , т.е. .

Разделив  обе части неравенства на положительное  число t, будем иметь , но это означает, что набор чисел удовлетворяет первому из неравенств (5). Аналогичное рассуждение можно провести для любого из неравенств (6), откуда и следует наше утверждение. Нетрудно видеть, что любое решение системы (5) может быть получено указанным выше способом. Действительно, если — какое-либо решение системы (5), то числа удовлетворяют системе (6), и при этом справедливы равенства (7).

     Итак, чтобы отыскать все решения  системы (5), следует найти все решения системы (6), для которых t > 0, и преобразовать каждое из них по формулам (7). [1, с. 85]

 

     3 Применение методов решения линейной неоднородной системы неравенств в оценке эффективности затрат ресурсов в задаче линейной оптимизации

     3.1 Содержание прямой  и двойственной  задач линейного программирования

Рассмотрим  общую схему построения двойственной задачи. Если задана общая задача линейного программирования:

      ,

где D определяется по формуле

      ,

      ,

то двойственной по отношению к ней называется общая задача линейного программирования

      ,

где D^* определяется по следующей формуле

      ,

      ,

где   – норма затрат -го вида ресурса в производстве единицы -го вида изделия;

       – имеющийся в наличии запас  -го вида ресурса;

       – цена (прибыль) реализации единицы  изделия, причем и — векторы переменных прямой и двойственной задач линейного программирования соответственно.

     Как следует из приведенной схемы, при переходе от прямой задачи линейного программирования к двойственной:

     1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.

     2. Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами.

     3. Матрица ограничений задачи А транспонируется.

     4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче, определяют номера ограничений, имеющих форму неравенств в двойственной задаче.

     5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче, определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче.

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

      ,

     Основные  теоремы:

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