ЛИНЕЙНЫЕ УРАВНЕНИЯ И НЕРАВЕНСТВА I
§ 23 Системы линейных неравенств
Системой линейных неравенств называется любая совокупность двух или более линейных неравенств, содержащих одну и ту же неизвестную величину.
Примерами таких систем могут служить системы:
Решить систему неравенств - это значит найти все значения неизвестной величины, при которых выполняется каждое неравенство системы.
Решим приведенные выше системы.
Расположим одну под другой две числовые прямые (рис. 31); на верхней отметим те значения х , при которых выполняется первое неравенство (х > 1), а на нижней-те значения х , при которых выполняется второе неравенство (х > 4).
Сравнивая результаты на числовых прямых, замечаем, что оба неравенства одновременно будут удовлетворяться при х > 4. Ответ, х > 4.
Первое неравенство дает -3х < -б, или х > 2, а второе - х > -8, или х < 8. Далее поступаем так же, как и в первом примере. На одной числовой прямой отмечаем все те значения х , при которых выполняется первое неравенство системы, а на второй числовой прямой, расположенной под первой, все те значения х , при которых выполняется второе неравенство системы (рис. 32).
Сравнение этих двух результатов показывает, что оба неравенства одновременно будут выполняться при всех значениях х , заключенных от 2 до 8. Множество таких значений х записывается в виде двойного неравенства 2 < х < 8.
Пример 3. Решить систему неравенств
Первое неравенство системы дает 5х < 10, или х < 2, второе х > 4. Таким образом, любое число, удовлетворяющее обоим неравенствам одновременно, должно быть не больше 2 и больше 4 (рис. 33).
Но таких чисел не существует. Поэтому данная система неравенств не выполняется ни при каких значениях х . Подобные системы неравенств называются несовместными.
Упражнения
Решить данные системы неравенств (№ 179 -184):
Решить неравенства (№ 185, 186):
185. (2х + 3) (2 - 2х ) > 0. 186. (2 - π ) (2х - 15) (х + 4) > 0.
Найти допустимые значения букв, входящих в данные равенства (№ 187, 188):
Решить неравенства (№ 189, 190):
189. 1 < 2х - 5 < 2. 190. -2 < 1 - ах < 5.
191. Какой должна быть температура 10 л воды, чтобы при смешении ее с 6 л воды при температуре 15° получить воду с температурой не менее 30° и не более 40°?
192. Одна сторона треугольника равна 4 см, а сумма двух других 10 см. Найти эти стороны, если они выражаются целыми числами.
193. Известно, что система двух линейных неравенств не удовлетворяется ни при каких значениях неизвестной величины. Можно ли сказать, что отдельные неравенства этой системы невыполняются ни при каких значениях неизвестной величины?
Свяжем с каждой точкой (x 1 ,x 2 ,…x n) n-мерного пространства R n n-мерный вектор x =(x 1 ,x 2 ,…x n) с началом в начале координат и концом в точке (x 1 ,x 2 ,…x n). Множество векторов х =(х 1 ,х 2 ,...х n) в R n , компоненты которых удовлетворяют m линейным неравенствам:
A 11 х 1 +a 12 х 2 +...+a 1 n x n ≤ b 1
a 21 х 1 +a 22 х 2 +...+a 2 n x n ≤ b 2
. . . . . . . . . . . . (2)
a m 1 х 1 +a m 2 х 2 +...+a m n x n ≤ b m
называется множеством решений системы линейных неравенств.
В определении все неравенства записаны со знаком ≤. Умножая на
(-1) любое из неравенств, можно изменить его знак на противоположный. Множество решений определено для систем линейных неравенств как со знаком ³ так и ≤.
Вопросы моделирования
Предмет теории моделирования
Моделирование - это замещение одного объекта (оригинала) другим (моделью) и фиксация и изучение свойств модели. Замещение производится с целью упрощения, удешевления, ускорения изучения свойств оригинала.
В общем случае объектом-оригиналом может быть естественная или искусственная, реальная или воображаемая система. Она имеет множество параметров и характеризуется определенными свойствами. Количественной мерой свойств системы служит множество характеристик , система проявляет свои свойства под влиянием внешних воздействий .
Множество параметров и их значений отражает ее внутреннее содержание- структуру и принципы функционирования. Характеристики -это в основном ее внешний признаки, которые важны при взаимодействии с другими .
Моделирование целесообразно, когда у модели отсутствуют те признаки оригинала, которые препятствуют его исследованию.
Теория моделирования - взаимосвязанная совокупность положений, определений, методов и средств создания моделей. Сами модели являются предметом теории моделирования.
Теория моделирования является основной составляющей общей теории систем - системологии, где в качестве главного принципа постулируются осуществимые модели: система представима конечным множеством моделей, каждая из которых отражает определенную грань ее сущности.
Роль и место моделирования в исследовании систем.
Познание любой системы () сводится по существу к созданию ее модели. Перед изготовлением каждого устройства или сооружения разрабатывается его модель- проект. Любое произведение искусства является моделью, фиксирующее действительность.
Достижения математики привели к распространению математических моделей различных объектов и процессов. Помечено, что динамика функционирования разных по физической природе систем однотипными зависимостями, что позволяет моделировать их на ПК.
Классификация моделей
Физические модели. В основу классификации положена степень абстрагирования модели от оригинала. Предварительно все модели можно подразделить на 2 группы - физические и абстрактные (математические).
Ф.М. обычно называют систему, эквивалентную или подобную оригиналу, но возможно имеющую другую физическую природу. Виды Ф.М.:
Натуральные;
Квазинатуральные;
Масштабные;
Аналоговые;
Натуральные модели - это реальные исследуемые системы (макеты, опытные образцы). Имеют полную адекватность (соответствия) с системой оригинала, но дороги.
Квазинатуральные модели - совокупность натуральных и математических моделей. Этот вид используется тогда, когда модель части системы не может быть математической из-за сложности ее описания (модель человека оператора) или когда часть системы должна быть исследована во взаимодействии с другими частями, но их еще не существует или их включение очень дорого (вычислительные полигоны, АСУ).
Масштабная модель - это система той же физической природы, что и оригинал, но отличается от него масштабами. Методологической основой масштабного моделирования является теория подобия. При проектировании ВС масштабные модели могут использоваться для анализа вариантов компоновочных решений.
Аналоговыми моделями называются системы, имеющие физическую природу, отличающуюся от оригинала, но сходные с оригиналом процессы функционирования. Для создания аналоговой модели требуется наличие математического описания изучаемой системы. В качестве аналоговых моделей используются механические, гидравлические, пневматические и электрических системы. Аналоговое моделирование используют при исследовании средства ВТ на уровне логических элементов и электрических цепей, а так же на системном уровне, когда функционирование системы описывается например, дифференциальными или алгебраическими уравнениями.
Математические модели. Математические модели представляют собой формализованное представление системы с помощью абстрактного языка, с помощью математических соотношений, отражающих процесс функционирования системы. Для составления математической модели можно использовать любые математические средства - алгебраическое, дифференциальное, интегральное исчисления, теорию множеств, теорию алгоритмов и т.д. По существу вся математика создана для составления и исследования моделей объектов и процессов.
К средствам абстрактного описания систем относятся также языки химических формул, схем, чертежей, карт, диаграмм и т.п. Выбор вида модели определяется особенностями изучаемой системы и целями моделирования, т.к. исследование модели позволяет получить ответы на определенную группу вопросов. Для получения другой информации другой информации может потребоваться модель другого вида. Математические модели можно классифицировать на детерминированные и вероятностные, аналитические, численные и имитационные.
Аналитической моделью называется такое формализованное описание системы, которое позволяет решить уравнение в явном виде, используя известный математический аппарат.
Численная модель характеризуется зависимостью такого вида, который допускает только частные решения для конкретных начальных условий и количественных параметров моделей.
Имитационная модель - это совокупность описания системы и внешних воздействий, алгоритмов функционирования системы или правил изменения состояния системы под влиянием внешних и внутренних возмущений. Эти алгоритмы и правила не дают возможности использования имеющихся математических методов аналитического и численного решения, но позволяют имитировать процесс функционирования системы и производить вычисления интересующих характеристик. Имитационные модели могут быть созданы для гораздо более широкого класса объектов и процессов, чем аналитические и численные. Поскольку для реализации имитационных моделей служат ВС, средствами формализованного описания им служат универсальные и специальные алгоритмические языки. Им в наибольшей степени подходят для исследования ВС на системном уровне.
Рассмотрим ряд задач, в которых необходимо найти область решения системы линейных неравенств.
Пример 1 :
X 1 + 3х 2 ≤ 6
х 1 - х 2 ≤ 2
Искомое множество решений соответствует заштрихованной области. Вершинами множества решений служат три точки (0,2), (0,-2) и (3,1). Ониявляются точками пересечения прямых, ограничивающих множество решений.
В этом примере множество решений - многогранное выпуклое множество.
Пример 2: Изобразить множество решений следующей системы линейных неравенств в R².
X 1 + 2х 2 ≤ 4
3х 1 + 2х 2 ≤ 6
Вершинами искомого множества являются две точки с координатами: (0,2) и (1/2, 9/4). Точка с координатой (0,3) вершиной не является, так как не удовлетворяет первому неравенству. Это множество решений - неограниченно.
РешениеПример 3: Изобразить множество решений следующей системы линейных неравенств в R².
Х 1 - х 2 ³ 1
х 1 + х 2 ≤ 1
Решением первого и второго неравенств являются точки заштрихо-ванного нижнего сектора. Решением третьего неравенства являются точки заштрихованной верхней полуплоскости. Поскольку общих точек у этих двух областей нет, то нет решения и у всей системы неравенств, т.е решением является Æ.
Основная задача линейного программирования.
В общем виде задача линейного программирования (ЗЛП) ставится следующим образом.
Найти вектор х =(х 1 ,х 2 , ... x n) в R n , который максимизирует (или минимизирует) целевую функцию
F(x)=с 1 х 1 +с 2 x 2 +... +с n x n (3)
и удовлетворяет m+n линейным неравенствам:
A 11 х 1 +a 12 x 2 +...+a 1n x n ≤ b 1
a 21 x 1 +a 22 x 2 +...+a 2n x n ≤ b 2
. . . . . . . . . . . . (4)
a m1 x 1 +a m2 x 2 +...+a mn x n ≤ b m
x 1 ³0, x 2 ³0, ... x n ³0
В терминологии программирования линейная функция F(х) называется целевой функцией задачи. Множество решений системы линейных неравенств (4) называют множеством допустимых решений, а любой вектор х из этого множества называется допустимым решением. Оптимальным решением называется вектор х *, при котором целевая функция принимает своё максимальное (или минимальное) значение на допустимом множестве решений.
Графический метод решения задач линейного программирования. Покажем, как решается указанная задача графическим (геометрическим) методом. Для этого ограничимся рассмотрением системы линейных неравенств с двумя неизвестными.
Пусть задана целевая функция F=с 1 х 1 +с 2 х 2 +с 0 . Найдём среди множества точек (х 1 ,х 2) из области допустимых решений совместной системы неравенств (4) (содержащей только переменные x 1 и x 2) такие, которые придают линейной функции F наименьшее (наибольшее) значения. Для каждой i – ой точки плоскости функция F принимает фиксированное значение F=F i . Множество всех таких точек на которых функция F принимает одно и то же значение F i есть прямая с 1 х 1 +c 2 х 2 +c 0 =F i = const, перпендикулярная к некоторому вектору, называемому градиентом F (grad F). Этот вектор выходит из начала координат и имеет координаты grad F =(с 1 ,с 2). По свойству вектора grad F если указанную прямую передвигать параллельно самой себе в положительном направлении вектора grad F, то значение целевой функции F=с 1 х 1 +с 2 х 2 +с 0 на этой прямой будет возрастать, а в противоположном направлении - убывать.
Пусть при движении прямой F=const в положительном направлении вектора grad F эта прямая впервые встретится с многоугольником допустимых решений в его вершине. Тогда в этом положении F 1 прямая F=const называется опорной, и на этой прямой функция F принимает наименьшее значение. При дальнейшем движении в том же направлении (положительном) прямая F=const пройдёт через другую вершину многоугольника допустимых решений и выходя из области решений также станет опорной прямой F 2 . На ней функция F принимает наибольшее значение среди всех значений, принимаемых на многоугольнике допустимых решений. Таким образом, минимизация и максимизация целевой функции F=с 1 х 1 +с 2 х 2 +с 0 на многоугольнике допустимых решений достигается в точках пересечения этого многоугольника с опорными прямыми F=с 1 х 1 +с 2 х 2 +с 0 = const, нормальными к вектору grad F=(с 1 , с 2). Это пересечение опорной прямой с множеством допустимых решений может быть либо в одной точке (вершине многоугольника), либо в бесконечном множестве точек (если это множество сторона многоугольника).
Задание по первой, второй, третьей задаче выбирается по фамилии имени отчеству студента, а по четвертой задаче выбирается по фамилии и отчеству.
Задача №1
Таблица 1
| Первая буква | Фамилия | Имя | Отчество | ||||||||||||
| a 11 | a 12 | a 21 | a 2 2 | a 31 | a 32 | a 41 | a 4 2 | b 1 | b 2 | b 3 | C0 | C1 | C2 | ||
| А | |||||||||||||||
| Б | |||||||||||||||
| В | |||||||||||||||
| Г | |||||||||||||||
| Д | |||||||||||||||
| Е | |||||||||||||||
| Ж | |||||||||||||||
| З | |||||||||||||||
| И | |||||||||||||||
| К | |||||||||||||||
| Л | |||||||||||||||
| М | |||||||||||||||
| Н | |||||||||||||||
| О | |||||||||||||||
| П | |||||||||||||||
| Р | |||||||||||||||
| С | |||||||||||||||
| Т | |||||||||||||||
| У | |||||||||||||||
| Ф | |||||||||||||||
| Х | |||||||||||||||
| Ц | |||||||||||||||
| Ч | |||||||||||||||
| ШЭ | |||||||||||||||
| ЮЯ | |||||||||||||||
Пример 4: Минимизировать линейную форму F=14x 1 +4x 2 при ограничениях:
7х 1 + 2х 2 ³ 14
4 х 1 –7x 2 ≤ 14
Заменив знаки неравенств на знаки точных равенств, получим уравнения границ области допустимых решений. По уравнениям, полученных прямых построим искомую область:
7х 1 +2х 2 =14
4 х 1 – 7x 2 = 14
Областью допустимых решений системы неравенств является многоугольник ABCDE.
рис 5.
Для нахождения точек экстремума построим прямую F=14x 1 +4x 2 =0 и вектор gradF = (14, 4). Будем передвигать прямую F=0 параллельно самой себе в направлении вектора grad F. С многоугольником ABCDE эта прямая впервые встретиться в точках Е(2,0) и А(10/9, 28/9), где целевая функция принимает одно и то же минимальное значение F(E) = F(A) =14·2+4∙0=28-min, (т.к. вектор grad F перпендикулярен прямой АЕ). Таким образом, минимальное значение целевая функция принимает в любой точке отрезка AE.
Из плана 
основной задачи линейного программирования следует, что число его положительных компонент не превышает .
Опорный план называется невырожденным, если он содержит ровно положительных компонент; в противном случае план является вырожденным.
Любые переменных системы линейных уравнений с переменными (при условии ) называются основными, если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные переменных называются не основными.
Базисным решением системы m линейных уравнений с переменными называется всякое ее решение, в котором все не основные переменные имеют нулевые значения.
Теорема 1 . Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.
Теорема 2 . Если задача линейного программирования имеет оптимальное решение, то оно совпадает с угловой точкой множества допустимых решений.
Следствие. Если оптимальное решение не единственное, то таких решений будет множество (например, все точки отрезка, соединяющего соответствующие угловые точки).
Теорема 3 . Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка области допустимых значений, и наоборот.
Понятие о симплекс-методе .
Решение основной задачи линейного программирования геометрическим методом достигает большой наглядности в случае 2-х и 3-х переменных. Для случая же большего числа переменных геометрический метод становится невозможным. Так называемый симплекс-метод принадлежит к числу аналитических методов решения основной задачи линейного программирования. При этом ограничения, используемые при реализации симплекс-метода, обычно задаются системой линейных уравнений
A 11 х 1 +a 12 х 2 +...+a 1n x n = b 1
a 21 х 1 +a 22 х 2 +...+a 2n x n = b 2
. . . . . . . . . . . . (5)
a m 1 х 1 +a m 2 х 2 +...+a mn x n = b m
среди неотрицательных решений которой ищутся такие, которые максими-зировали бы линейную (целевую) функцию
F=с 1 х 1 +с 2 х 2 +…+с n х n +с 0
Симплексный метод основан на теоремах:
Теорема 1. Если ЗЛП имеет оптимальное решение, то целевая функция принимает экстремальное значение в одной из угловых точек выпуклого многоугольника допустимых решений.
Теорема 2. Каждому опорному решению ЗЛП соответствует угловая точка многоугольника допустимых решений и наоборот.
Исходя из этих теорем, при реализации симплекс-метода осуществляется целенаправленный перебор всех вершин так, чтобы в каждой следующей вершине значение целевой функции было бы не меньше (не больше) чем в предыдущей вершине. При этом за конечное число шагов достигается искомое оптимальное решение, или устанавливается, что ЗЛП неразрешима.
Для осуществления указанного алгоритма выберем в системе (5) max набор линейно независимых переменных (тех, для которых определитель составленный из коэффициентов перед этими переменными отличен от 0). Пусть для определенности это будут переменные х 1 , х 2 ,... х r (r ≤ m). Выразим эти переменные через остальные переменные
Х 1 = а" 1, r +1 х г+1 + ... + a" 1 n х n + b 1 "
х 2 = а" 2, r +1 х г+1 + ... + a" 2 n х n + b 2 " (6)
. . . . . . . . . . . . . . . .
х r = a" r , r +1 х г+1 + ... + a" r n x n + b r "
причем будем предполагать, что все b 1 "³0, b 2 "³0, b r "³0. Если исходные ограничительные условия заданы неравенствами, то их можно преобразовать к виду (5) путём введения новых неотрицательных переменных, так называемых балансовых (выравнивающих). Так, например,в неравенствеа 1 х 1 +а 2 х 2 +…+а n х n ≤ b достаточно добавить к левой части неравенства некоторую величину х n +1 ³ 0 равную разности между правой и левой частями неравенства и мы получим равенство a 1 x 1 + а 2 х 2 +…+а n х n + x n +1 = b. Если ограничительные условия заданы смешанным образом, то есть неравенствами и уравнениями, тогда указанным путём их так же можно свести только к уравнениям.
В полученной системе (6) переменные (неизвестные) х 1 ,х 2 ... х г называются базисными, а весь набор {х 1 , х 2 ... х г } - базисом, остальные переменные называются свободными. Система ограничений (6) называется системой, приведённой к единичному базису. Подставляя в целевую функцию F вместо базисных переменных их выражения через свободные из системы (6) получим
F = C 0 + C г+1 х г+1 + … + C n х n
Теперь, полагая все свободные переменные равными нулю, найдём значения базисных переменных:
х 1 =b 1 " , х 2 = b 2 " , ... x r =b r "
Полученное таким образом допустимое решение системы (6)
(b 1 " ,b 2 " , ... b r " , 0, ... 0) называется базисным. Для этого базисного решения значение целевой функции будет равно F Б = C 0.
Решение задачи при помощи симплекс-метода распадается на ряд шагов, заключающихся в том, что от данного базиса Б мы переходим к другому базису Б" с таким расчётом, чтобы значение F Б на новом базисе увеличивалось или, по крайней мере, не уменьшалось, то есть выполнялось F Б " ≥ F Б. При этом если все b 1 ">0, b 2 ">0,…., b r ">0 , то данное решение называется опорным и соответствует какой-нибудь угловой точке области допустимых решений определяемой исходной системой ограничений. Тогда переход от одного базисного (опорного) решения к другому соответствует переходу от одной вершины многоугольника допустимых решений к другой вершине.
ЗАДАЧА№2
Для реализации трех групп товаров коммерческое предприятие располагает тремя видами органических материально-денежных ресурсов в количестве , , единиц. При этом для продажи 1 группы товаров на 1 тыс.руб. товарооборота расход утерся в количестве единиц, ресурса второго вида в количестве единиц, ресурса третьего вида в количестве единиц. Для продажи 2 и 3 групп товара на 1 тыс.руб. товарооборота расходуется соответственно ресурса первого вида в количестве , единиц, ресурсов второго вида в количестве , единиц, ресурсов третьего вида в количестве , единиц. Прибыль от одах трех групп товаров на 1тыс.руб. товарооборота составляет соответственно , , (тыс.руб.).
Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.
| Первая буква | Фамилия | Имя | Отчество | ||||||||||||
| А | |||||||||||||||
| Б | |||||||||||||||
| В | 1 0 | ||||||||||||||
| Г | |||||||||||||||
| Д | |||||||||||||||
| Е | |||||||||||||||
| Ж | |||||||||||||||
| З | |||||||||||||||
| И | |||||||||||||||
| К | |||||||||||||||
| Л | |||||||||||||||
| М | |||||||||||||||
| Н | |||||||||||||||
| О | |||||||||||||||
| П | |||||||||||||||
| Р | |||||||||||||||
| С | |||||||||||||||
| Т | |||||||||||||||
| У | |||||||||||||||
| Ф | |||||||||||||||
| Х | |||||||||||||||
| Ц | |||||||||||||||
| Ч | |||||||||||||||
| Ш Э | |||||||||||||||
| Ю Я |
Пример 5: Максимизировать целевую функцию F=-х 4 +х 5 при ограничениях:
Данная система уравнений совместна, так как ранги матрицы системы
и расширенной матрицы 
совпадают и равны 3. Выражая базисные переменные (стоящие в единичных столбцах) х 1 , х 2 , х 3 , через свободные переменные х 4 и х 5 , приходим к системе
(7)
Помимо системы (7) базисные переменные выразим через свободные переменные и в целевой функции (в нашем примере F = -x 4 + x 5 уже выражена через свободные переменные x 4 и x 5). Полагая теперь х 4 = 0, х 5 =0 находим базисные переменные: х 1 =1, х 2 =2, х 3 =3. Таким образом, первое допустимое базисное решение системы уравнений есть (1, 2, 3, 0, 0) . При найденном допустимом решении целевая функция F имеет значение 0, то есть F 1 =0.
Теперь попытаемся увеличить значение F 1 . Увеличение х 4 уменьшит F 1 , так как перед х 4 в выражении F = -x 4 + x 5 стоит отрицательный коэффициент, а увеличение x 5 даёт увеличение F 1 . Увеличим поэтому x 5 так, чтобы х 1 , х 2 , х 3 , не стали отрицательными, оставив х 4 =0. Из второго уравнения (7) видим, что х 5 можно увеличить до 2 (так, чтобы x 2 оставалось бы 0, при x 4 = 0). Тогда значение переменных будут (5, 0, 1, 0, 2), а значение F 2 = 2. Как видно величина F на втором шаге увеличилась.
Поскольку x 2 и x 4 оказались равными 0, то далее примем за свободные неизвестные х 2 и х 4 , тогда х 5 = 2-х 2 +2х 4
и от системы (7) переходим к эквивалентной ей системе (8)
(8)
Причем и F в этом случае будет равной
F = 2-х 2 +х 4
Для увеличения F будем увеличивать х 4 (так как перед x 2 стоитотрицательный коэффициент) Из второго уравнения системы (8) видно, что при условии неотрицательного х 3 значение х 4 можно довести до х 4 =1/5, тогда имеем (28/5, 0, 0, 1/5, 12/5), F 3 =11/5.
Поскольку в решении получено x 2 = x 3 = 0, то примем x 2 и x 3 за свободные переменные и выразим х 1 , х 4 , х 5 , через х 2 и х 3 .Получим
X 1 = 28/5 - 7/5 x 2 - 3/5 x 3
x 4 = 1/5 + 1/5 x 2 – 1/5 x 3
x 5 = 12/5 – 3/5 x 2 – 2/5 x 3
причем F = 11/5 – 4/5 x 2 – 1/5 x 3
Так как коэффициенты при x 2 и при x 3 в выражении для F отрицательны, то увеличить значение F уже невозможно. Поэтому полагая х 2 = х 3 =0 получаем наибольшее значение F = 11/5 при решении (28/5, 0, 0, 1/5, 12/5)
Ответ: F max = 11/5 при X * = (28/5, 0, 0, 1/5, 12/5)
Симплексные таблицы.
Поскольку решать ЗЛП, используя такие рассуждения, как это делалось в предыдущем примере, явно неудобно для компактной записи решения, а так же для возможности программирования алгоритма решения на ЭВМ используются так называемые симплекс-таблицы. Для этого систему ограничений сведем к единичному базису
х 1 + а 1, r +1 х г+1 + ... + a 1 n х n = b 1
х i + а i,r+1 х г+1 + .... + a i n х n = b i (9)
х r + а r,r+1 х г+1 + ... + a r n х n = b r
а целевую функцию F - к виду:
F = C г+1 x r +1 + ... + C j х j +…+ C n x n + C 0 (10)
Равенство (10) будем называть приведённым (к свободным переменным) выражением для функции F а коэффициенты C j – оценками (индексами) соответствующих свободных переменных х j .
Коэффициенты приведенной выше системы ограничений (9), а так же различные вспомогательные переменные заносятся в симплексную таблицу (Таблица 1)
Таблица 1
| Базисные перемен-ные | Свободные члены | х 1 | ... | х i | ... | x r | х г+1 | ... | x j | ... | х n | |
| х 1 | b 1 | ... | ... | а 1,r+1 | ... | a 1j | ... | a 1n | ||||
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ||
| х i | b i | ... | ... | а i,r+1 | ... | a ij | ... | a in | ||||
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | |
| x r | b r | ... | ... | а r,r+1 | ... | a rj | ... | a rn | ||||
| F= | C 0 | ... | ... | - C г+1 | ... | - C j | ... | - C n |
Первые r столбцов с неизвестными x i - это единичные столбцы при базисных переменных x 1 ,…,x r . Следующие n-r столбцов – это столбцы при свободных переменных x r +1 ,…,x n . Полагая свободные переменные x r +1 = …=
X n = 0, находим базисные переменные x 1 = b 1 ,…, x r = b r . При этом значение целевой функции F = C 0 .
Найденный вектор-план X 1 = и значение целевой функции F = C 0 соответствуют некоторой вершине многоугольника допустимых решений. Переход к другой вершине и, следовательно, к другому вектор-плану и другому значению целевой функции осуществляется с помощью пересчета данной симплексной таблицы.
см. также Решение задачи линейного программирования графически , Каноническая форма задач линейного программирования
Система ограничений такой задачи состоит из неравенств от двух переменных:
и целевая функция имеет вид F
= C
1 x
+ C
2 y
, которую необходимо максимизировать.
Ответим на вопрос: какие пары чисел ( x
; y
) являются решениями системы неравенств, т. е. удовлетворяют каждому из неравенств одновременно? Другими словами, что значит решить систему графически?
Предварительно необходимо понять, что является решением одного линейного неравенства с двумя неизвестными.
Решить линейное неравенство с двумя неизвестными – это значит определить все пары значений неизвестных, при которых неравенство выполняется.
Например, неравенству 3x
– 5 y
≥ 42 удовлетворяют пары (x
, y
) : (100, 2); (3, –10) и т. д. Задача состоит в нахождении всех таких пар.
Рассмотрим два неравенства: ax
+ by
≤ c
, ax
+ by
≥ c
. Прямая ax
+ by
= c
делит плоскость на две полуплоскости так, что координаты точек одной из них удовлетворяют неравенству ax
+ by
>c
, а другой неравенству ax
+ +by
<c
.
Действительно, возьмем точку с координатой x
= x
0 ; тогда точка, лежащая на прямой и имеющая абсциссу x
0 , имеет ординату
Пусть для определенности a
< 0, b
>0,
c
>0. Все точки с абсциссой x
0 , лежащие выше P
(например, точка М
), имеют y M
>y
0 , а все точки, лежащие ниже точки P
, с абсциссой x
0 , имеют y N
<y
0 .
Поскольку x
0 –произвольная точка, то всегда с одной стороны от прямой будут находиться точки,
для которых ax
+ by
> c
, образующие полуплоскость, а с другой стороны – точки, для которых ax
+ by
< c
.
Рисунок 1
Знак неравенства в полуплоскости зависит от чисел a
, b
, c
.
Отсюда вытекает следующий способ графического решения систем линейных неравенств от двух переменных. Для решения системы необходимо:
Эта область может оказаться пустой, тогда система неравенств не имеет решений, несовместна. В противном случае говорят, что система совместна.
Решений может быть конечное число и бесконечное множество. Область может представлять собой замкнутый многоугольник или же быть неограниченной.
Рассмотрим три соответствующих примера.
Пример 1.
Решить графически систему:
x
+ y –
1 ≤ 0;
–2 x –
2y
+ 5 ≤ 0.
Определим полуплоскости, задаваемые неравенствами. Возьмем произвольную точку, пусть (0; 0). Рассмотрим x
+ y–
1 0, подставим точку (0; 0): 0 + 0 – 1 ≤ 0. значит, в той полуплоскости, где лежит точка (0; 0), x
+ y
–
1 ≤ 0, т.е. полуплоскость, лежащая ниже прямой, является решением первого неравенства.
Подставив эту точку (0; 0), во второе, получим: –2 ∙ 0 – 2 ∙ 0 + 5 ≤ 0, т.е. в полуплоскости, где лежит точка (0; 0), –2x
– 2y
+ 5≥ 0, а нас спрашивали, где –2x
– 2y
+ 5 ≤ 0, следовательно, в другой полуплоскости – в той, что выше прямой.
Найдем пересечение этих двух полуплоскостей. Прямые параллельны, поэтому плоскости нигде не пересекаются, значит система данных неравенств решений не имеет, несовместна.
Пример 2.
Найти графически решения системы неравенств:
Рисунок 3
1. Выпишем уравнения, соответствующие неравенствам, и построим прямые.
x
+ 2y
– 2 = 0
| x | 2 | 0 |
| y | 0 | 1 |
| x | 0 | 2 |
| y | 1 | 3 |
Рассмотрим еще один пример, в котором получившаяся область решения системы не ограничена.
Определение 1 . Совокупность точек пространства R n , координаты которых удовлетворяют уравнению а 1 х 1 + а 2 х 2 +…+ a n x n = b , называется (n - 1 )-мерной гиперплоскостью в n -мерном пространстве.
Теорема 1. Гиперплоскость делит все пространство на два полупространства. Полупространство является выпуклым множеством.
Пересечение конечного числа полупространств является выпуклым множеством.
Теорема 2 . Решением линейного неравенства с n неизвестными
а 1 х 1 + а 2 х 2 +…+ a n x n b
является одно из полупространств, на которые все пространство делит гиперплоскость
а 1 х 1 + а 2 х 2 +…+a n x n = b .
Рассмотрим систему из m линейных неравенств с n неизвестными.
Решением каждого неравенства системы является некоторое полупространство. Решением системы будет являться пересечение всех полупространств. Это множество будет замкнутым и выпуклым.
Решение систем линейных неравенств
с двумя переменными
Пусть дана система из m линейных неравенств с двумя переменными.
Решением каждого неравенства будет являться одна из полуплоскостей, на которые всю плоскость разбивает соответствующая прямая. Решением системы будет являться пересечение этих полуплоскостей. Данная задача может быть решена графически на плоскости Х 1 0 Х 2 .
Определение 1. Замкнутое выпуклое ограниченное множество в R n , имеющее конечное число угловых точек , называется выпуклым n -мерным многогранником.
Определение 2 . Замкнутое выпуклое неограниченное множество в R n , имеющее конечное число угловых точек, называется выпуклой многогранной областью.
Определение 3 . Множество А R n называется ограниченным, если найдется n -мерный шар, содержащий это множество.
Определение 4. Выпуклой линейной комбинацией точек называется выражение, гдеt i , .
Теорема (теорема о представлении выпуклого многогранника). Любую точку выпуклого многогранника можно представить в виде выпуклой линейной комбинации его угловых точек.
Пусть дана система из m линейных уравнений и неравенств с n неизвестными.
Определение 1 . Точка R n называется возможным решением системы, если ее координаты удовлетворяют уравнениям и неравенствам системы. Совокупность всех возможных решений называется областью возможных решений (ОВР) системы.
Определение 2. Возможное решение, координаты которого неотрицательны, называется допустимым решением системы. Множество всех допустимых решений называется областью допустимых решений (ОДР) системы.
Теорема 1 . ОДР является замкнутым, выпуклым, ограниченным (или неограниченным) подмножеством вR n .
Теорема 2. Допустимое решение системы является опорным тогда и только тогда, когда эта точка являетсяугловой точкой ОДР.
Теорема 3 (теорема о представлении ОДР). Если ОДР - ограниченное множество, то любое допустимое решение можно представить в виде выпуклой линейной комбинации угловых точек ОДР (в виде выпуклой линейной комбинации опорных решений системы).
Теорема 4 (теорема о существовании опорного решения системы). Если система имеет хотя бы одно допустимое решение (ОДР), то среди допустимых решений существует хотя бы одно опорное решение.
