Графический метод.. 3

Симплекс-метод.. 6

Метод искусственного базиса.. 8

Принцип двойственности.. 10

Список использованной литературы... 12

Вступление

Отдельные свойства систем линейных неравенств рассматривались еще в первой половине 19 века в связи с некоторыми задачами аналитической механики. Систематическое же изучение систем линейных неравенств началось в самом конце 19 века, однако о теории линейных неравенств стало возможным говорить лишь в конце двадцатых годов 20 века, когда уже накопилось достаточное количество связанных с ними результатов.

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

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

В данной работе будут изложены основные методы решения линейных неравенств, применительно к конкретным задачам.

Графический метод

Графический метод заключается в построении множества допустимых решений ЗЛП, и нахождении в данном множестве точки, соответствующей max/min целевой функции.

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

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

На первом этапе надо построить область допустимых решений. Для данного примера удобнее всего выбрать X2 за абсциссу, а X1 за ординату и записать неравенства в следующем виде:

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

Для того чтобы найти граничные точки решаем уравнения (1)=(2), (1)=(3) и (2)=(3).

Как видно из иллюстрации многогранник ABCDEобразует область допустимых решений.

Если область допустимых решений не является замкнутой, то либо max(f)=+ ∞, либо min(f)= -∞.

Теперь можно перейти к непосредственному нахождению максимума функции f.

Поочерёдно подставляя координаты вершин многогранника в функцию f и сравнивать значения, находим что

f(C)=f(4;1)=19 – максимум функции.

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

В таком случае удобнее рассмотреть линию уровня вида f=a. При монотонном увеличении числа aот -∞ до +∞ прямые f=aсмещаются по вектору нормали . Если при таком перемещении линии уровня существует некоторая точка X– первая общая точка области допустимых решений (многогранник ABCDE) и линии уровня, то f(X)- минимум fна множестве ABCDE. Если X- последняя точка пересечения линии уровня и множества ABCDE то f(X)- максимум на множестве допустимых решений. Если при а→-∞ прямая f=aпересекает множество допустимых решений, то min(f)= -∞. Если это происходит при а→+∞, то

В нашем примере прямая f=aпересевает область ABCDEв точке С(4;1). Поскольку это последняя точка пересечения, max(f)=f(C)=f(4;1)=19.

Симплекс-метод

Реальные задачи линейного программирования содержат очень большое число ограничений и неизвестных и выполняются на ЭВМ. Симплекс-метод – наиболее общий алгоритм, использующийся для решения таких задач. Суть метода заключается в том, что после некоторого числа специальных симплекс- преобразований ЗЛП, приведенная к специальному виду, разрешается. Для того, чтобы продемонстрировать симплекс-метод в действии решим, с попутными комментариями следующую задачу:

Для того, чтобы приступить к решению ЗЛП симплекс методом, надо привести ЗЛП к специальному виду и заполнить симплекс таблицу.

Система (4) – естественные ограничения и в таблицу не вписываются. Уравнения (1), (2), (3) образуют область допустимых решений. Выражение (5) – целевая функция. Свободные члены в системе ограничений и области допустимых решений должны быть неотрицательны.

В данном примере X3, X4, X5 – базисные неизвестные. Их надо выразить через свободные неизвестные и произвести их замену в целевой функции.

Теперь можно приступить к заполнению симплекс-таблицы:

Б.	X1	X2	X3	X4	X5	C
X3	0	-1	1	1	0	1
X4	0	1	-1	0	1	1
X5	1	1	1	0	0	2
f	0	-6	7	0	0	3

В первом столбце данной таблицы обозначены базисные неизвестные, в последнем – значения свободных неизвестных, в остальных – коэффициенты при неизвестных.

Для того чтобы найти максимум функции fнадо с помощью преобразований методом Гаусса сделать так, чтобы все коэффициенты при неизвестных в последней строке были неотрицательными (для нахождения минимума, сделать так, чтобы все коэффициенты были меньше или равны нулю).

Б	X1	X2	X3	X4	X5	C
X3	-1	1	1	0	0	1
X4	1	-1	0	1	0	1
X5	1	1	0	0	1	2
f	-6	7	0	0	0	3

Для этого выбираем столбец с отрицательным коэффициентом в последней строке (столбец 3) и составляем для положительных элементов данного столбца отношения свободный член/коэффициент (1/1; 2/1) . Из данных отношений выбираем наименьшее и помечаем соответствующую строку .

Нами выбран элемент в ячейке (3;3). Теперь с помощью метода Гаусса обнуляем другие коэффициенты в данном столбце, это приводит к смене базиса и мы на один шаг приближаемся к оптимальному решению.

Б	X1	X2	X3	X4	X5	C
X3	0	0	1	1	0	2
X1	1	-1	0	1	0	1
X5	0	2	0	-1	1	1
f	0	1	0	6	0	9

Как видно из таблицы теперь все коэффициенты в последней строке больше либо равны нулю. Это означает, что нами найдено оптимальное значение. Свободные неизвестные равны нулю, значению базисных неизвестных и максимуму функции f соответствует значения свободных неизвестных.

Рассмотрим на примерах, как решить систему линейных неравенств.

4x + 29 \end{array} \right.\]" title="Rendered by QuickLaTeX.com">

Чтобы решить систему, нужно каждое из составляющих её неравенств. Только решение принято записывать не по отдельности, а вместе, объединяя их фигурной скобкой.

В каждом из неравенств системы неизвестные переносим в одну сторону, известные — в другую с противоположным знаком:

Title="Rendered by QuickLaTeX.com">

После упрощения обе части неравенства надо разделить на число, стоящее перед иксом. Первое неравенство делим на положительное число, поэтому знак неравенства не изменяется. Второе неравенство делим на отрицательное число, поэтому знак неравенства надо изменить на противоположный:

Title="Rendered by QuickLaTeX.com">

Решение неравенств отмечаем на числовых прямых:

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

Ответ: x∈[-2;1).

В первом неравенстве избавимся от дроби. Для этого обе части умножим почленно на наименьший общий знаменатель 2. При умножении на положительное число знак неравенства не изменяется.

Во втором неравенстве раскрываем скобки. Произведение суммы и разности двух выражений равно разности квадратов этих выражений. В правой части — квадрат разности двух выражений.

Title="Rendered by QuickLaTeX.com">

Неизвестные переносим в одну сторону, известные — в другую с противоположным знаком и упрощаем:

Обе части неравенства делим на число, стоящее перед иксом. В первом неравенстве делим на отрицательное число, поэтому знак неравенства изменяется на противоположный. Во втором — делим на положительное число, знак неравенства не изменяется:

Title="Rendered by QuickLaTeX.com">

Оба неравенства со знаком «меньше» (не существенно, что один знак — строго «меньше», другой — нестрогий, «меньше либо равно»). Можем не отмечать оба решения, а воспользоваться правилом « «. Меньшим является 1, следовательно, система сводится к неравенству

Отмечаем его решение на числовой прямой:

Ответ: x∈(-∞;1].

Раскрываем скобки. В первом неравенстве — . Оно равно сумме кубов этих выражений.

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

Переносим неизвестные в одну сторону, известные — в другую с противоположным знаком:

Title="Rendered by QuickLaTeX.com">

Оба знака «больше». Используя правило «больше большего», сводим систему неравенств к одному неравенству. Большее из двух чисел 5, следоветельно,

Title="Rendered by QuickLaTeX.com">

Решение неравенства отмечаем на числовой прямой и записываем ответ:

Ответ: x∈(5;∞).

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

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

Рубрика: |

Соблюдение Вашей конфиденциальности важно для нас. По этой причине, мы разработали Политику Конфиденциальности, которая описывает, как мы используем и храним Вашу информацию. Пожалуйста, ознакомьтесь с нашими правилами соблюдения конфиденциальности и сообщите нам, если у вас возникнут какие-либо вопросы.

Сбор и использование персональной информации

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

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

Ниже приведены некоторые примеры типов персональной информации, которую мы можем собирать, и как мы можем использовать такую информацию.

Какую персональную информацию мы собираем:

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

Как мы используем вашу персональную информацию:

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

Раскрытие информации третьим лицам

Мы не раскрываем полученную от Вас информацию третьим лицам.

Исключения:

• В случае если необходимо - в соответствии с законом, судебным порядком, в судебном разбирательстве, и/или на основании публичных запросов или запросов от государственных органов на территории РФ - раскрыть вашу персональную информацию. Мы также можем раскрывать информацию о вас если мы определим, что такое раскрытие необходимо или уместно в целях безопасности, поддержания правопорядка, или иных общественно важных случаях.
• В случае реорганизации, слияния или продажи мы можем передать собираемую нами персональную информацию соответствующему третьему лицу – правопреемнику.

Защита персональной информации

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

Соблюдение вашей конфиденциальности на уровне компании

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

называется любая совокупность двух или более линейных неравенств, содержащих одну и туже неизвестную величину

Вот образцы подобных систем:

Промежуток пересечения двух лучей и есть наше решение. Следовательно решением данного неравенства выступают все х расположенные между двойкой и восьмеркой.

Ответ: х

Применение такого типа отображения решения системы неравенств иногда именуют методом крыш .

Определение: Пересечением двух множеств А и В называется такое третье множество, которое включает все элементы, входящих и в А и в В . Это смысл пересечения множеств произвольной природы. Нами сейчас детально рассматриваются числовые множества, поэтому при нахождении линейных неравенств такими множествами являются лучи - сонаправленные, противонаправленные и так далее.

Выясним на реальных примерах нахождение линейных систем неравенств, как определить пересечения множеств решений отдельных неравенств, входящих в систему.

Вычислим систему неравенств :

Поместим одну под другой две силовые прямые. На верхней нанесем те значения х, которые выполняют первое неравенство x >7 , а на нижней - которые выступают решением второго неравенства x >10 Соотнесем результаты числовых прямых, выясним, что оба неравенства будут удовлетворятся при x >10.

Ответ: (10;+∞).

Делаем по аналогии с первым образцом. На заданной числовой оси наносим все те значения х при которых существует первое неравенство системы , а на второй числовой оси, размещенной под первой, - все те значения х , при которых выполняется второе неравенство системы. Соотнесем эти два результата и определим, что оба неравенства одновременно будут выполнятся при всех значениях х расположенных между 7 и 10 с учетом знаков получаем 7<х≤10

Ответ: (7; 10].

Подобным образом решаются и нижеследующие системы неравенств.

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

Наглядно данную формулировку иллюстрируют, к примеру, такие системы неравенств :

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

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

Разберем решение нескольких неравенств:

Разместим одну под другой пару числовых прямых; на верхнею нанесем величину x , при которых первое неравенств о (x > 1) становиться верным, а на нижней—величину х , которые являются решением второго неравенства (х > 4).

Сопоставив данные на числовых прямых , отметим, что решением для обоих неравенств будет х > 4. Ответ, х > 4.

Пример 2.

Вычисляя первое неравенство получаем -3х < -6, или x > 2, второе -х > -8, или х < 8. Затем делаем по аналогии с предыдущим примером. На верхнюю числовую прямую наносим все те значения х , при которых реализуется первое неравенство системы , а на нижнюю числовую прямую, все те значения х , при которых реализуется второе неравенство системы.

Сопоставив данные, получаем, что оба неравенства будут реализовываться при всех значениях х , размещенных от 2 до 8. Множеств значений х обозначаем двойным неравенством 2 < х < 8.

Пример 3. Найдем