рівносильно лемі 1.
ЛЕММА 2. Нехай нерівність
(2)
є наслідок системи
і
. (3)
Тоді нерівність (2) є наслідком системи
Доказ. Розглянемо систему
Вектор з чинності (3) є неотрицательная лінійна комбінація векторів,
У силу пропозиції 1.1. звідси випливає, що (2) є наслідком системи (II):
(II) (5)
Треба довести, що будь-яке рішення? системи (4) є рішенням нерівності (2). Можливі два випадки: або. Якщо то ? є рішення системи (1) і, отже, за умовою? є рішенням нерівності (2). Якщо ж, то? є рішення системи (1); отже, зважаючи (4) є рішенням і нерівності (2). Отже, будь-яке рішення системи (4) є рішенням нерівності (2).
1.7 Теорема Мінковського
У теорії лінійних нерівностей однією з основних є наступна теорема.
ТЕОРЕМА. Нехай нерівність
(2)
Є наслідок системи
Тоді.
Доказ. (проводиться індукцією по m) ю Теорема вірна при m=1. Дійсно, нехай За умовою, нерівність є наслідок нерівності. За слідству 1., де? Так як то Тому вектор є рішення нерівності і, за умовою, рішення нерівності (2), тобто Отже,?. Теорема, очевидно, вірна також при.
Припустимо, що теорема вірна, коли система містить нерівностей. Так як (1) (2), то по слідству 1. Серед уявлень вектора b існує уявлення з найбільшим числом невід'ємних коефіцієнтів. Нехай
(3)
одне з таких подань. Нехай s є число невід'ємних коефіцієнтів у (3), Треба довести, що. Припустимо, що
Ми будемо вважати, що коефіцієнти ненегативні. Розглянемо вектор
Тоді
Нехай M - множина всіх рішень системи (1) і?- Будь-який вектор з М, тоді, якщо; отже,
Крім того, за умовою, тому
На підставі (6) і (7) укладаємо для будь-якого? з М, тобто нерівність є наслідок системи (1).
За лемі 2, звідси випливає, що нерівність є наслідок системи
складатися з нерівностей. За індуктивному припущенню,, т.е з можна представити у вигляді
Зважаючи (5) і (8)
У цьому поданні вектора b число невід'ємних коефіцієнтів більше, ніж s. Це суперечить припущенню, що подання (3) вектора b містить найбільше число невід'ємних коефіцієнтів. Ми прийшли до протиріччя, допустивши, що Таким чином, цей випадок неможливий. Отже, т.е (3) є шукане уявлення вектора b у вигляді невід'ємних комбінації векторів.
Глава 2. Симплекс-метод
. 1 Основна задача лінійного програмування
. Формулювання основного завдання. Основна задача лінійного програмування формулюється так:
Дана лінійна форма (цільова функція)
і задана система лінійних нерівностей (обмежень)
(1)
яку перепишемо у вигляді
Знайти максимум (мінімум форми (2.1) при виконанні (2.2).
Іншими словами, серед рішень системи (2.2) (утворюють багатогранник?) треба відшукати таке, для якого форма (2.1) приймає найбільше (найменше) значення.
. Геометрична інтерпретація. Основну задачу лінійного програмування можна легко інтерпретувати геометрично. Кожне нерівність
системи (2.2) визначає в евклідовому n-вимірному просторі півпростір, що складається з точок, розташованих «по один бік» від площини
і на самій цій площині. Точки ж, що належать всім Напівпростір (2.2) (тобто безліч всіх рішень системи (2.2)) як перетин опуклих множин, утворять деякий опуклий багатогранник? (Або багатогранне безліч).
Значення функції
в точці можна розглядати як ухилення точки від площини
розуміючи під ухиленням даної точки від цієї площини число, яке отримаємо, підставляючи в ліву частину рівняння (*) замість координати цієї точки. Так, наприклад, ухилення точки x (1, - 2,5) від площини
...
