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

Навигация по странице.

Что такое система неравенств?

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

Определение.

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

Приведем пример системы неравенств. Возьмем два произвольных , например, 2·x−3>0 и 5−x≥4·x−11 , запишем их одно под другим
2·x−3>0 ,
5−x≥4·x−11
и объединим знаком системы – фигурной скобкой, в результате получим систему неравенств такого вида:

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

Основные виды систем неравенств

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

• по числу неравенств в системе;
• по числу переменных, участвующих в записи;
• по виду самих неравенств.

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

Отдельно скажем, что нет смысла говорить о системе одного неравенства, в этом случае по сути речь идет о самом неравенстве, а не о системе.

Если смотреть на число переменных, то имеют место системы неравенств с одной, двумя, тремя и т.д. переменными (или, как еще говорят, неизвестными). Посмотрите на последнюю систему неравенств, записанную двумя абзацами выше. Это система с тремя переменными x , y и z . Обратите внимание, что ее два первых неравенства содержат не все три переменные, а лишь по одной из них. В контексте этой системы их стоит понимать как неравенства с тремя переменными вида x+0·y+0·z≥−2 и 0·x+y+0·z≤5 соответственно. Заметим, что в школе основное внимание уделяется неравенствам с одной переменной.

Осталось обговорить, какие виды неравенств участвуют в записи систем. В школе в основном рассматривают системы двух неравенств (реже – трех, еще реже - четырех и более) с одной или двумя переменными, причем сами неравенства обычно являются целыми неравенствами первой или второй степени (реже – более высоких степеней или дробно рациональными). Но не удивляйтесь, если в материалах по подготовке к ОГЭ столкнетесь с системами неравенств, содержащими иррациональные, логарифмические, показательные и другие неравенства. В качестве примера приведем систему неравенств , она взята из .

Что называется решением системы неравенств?

Введем еще одно определение, связанное с системами неравенств, - определение решения системы неравенств :

Определение.

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

Поясним на примере. Возьмем систему двух неравенств с одной переменной . Возьмем значение переменной x , равное 8 , оно является решением нашей системы неравенств по определению, так как его подстановка в неравенства системы дает два верных числовых неравенства 8>7 и 2−3·8≤0 . Напротив, единица не является решением системы, так как при ее подстановке вместо переменной x первое неравенство обратится в неверное числовое неравенство 1>7 .

Аналогично можно ввести определение решения системы неравенств с двумя, тремя и большим числом переменных:

Определение.

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

К примеру, пара значений x=1 , y=2 или в другой записи (1, 2) является решением системы неравенств с двумя переменными , так как 1+2<7 и 1−2<0 - верные числовые неравенства. А пара (3,5, 3) не является решением этой системы, так как второе неравенство при этих значениях переменных дает неверное числовое неравенство 3,5−3<0 .

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

В некоторых источниках вводятся определения частного и общего решения системы неравенств, как, например, в учебниках Мордковича . Под частным решением системы неравенств понимают ее одно отдельно взятое решение. В свою очередь общее решение системы неравенств - это все ее частные решения. Однако в этих терминах есть смысл лишь тогда, когда требуется особо подчеркнуть, о каком решении идет речь, но обычно это и так понятно из контекста, поэтому намного чаще говорят просто «решение системы неравенств».

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

Список литературы.

1. Алгебра: учеб. для 8 кл. общеобразоват. учреждений / [Ю. Н. Макарычев, Н. Г. Миндюк, К. И. Нешков, С. Б. Суворова]; под ред. С. А. Теляковского. - 16-е изд. - М. : Просвещение, 2008. - 271 с. : ил. - ISBN 978-5-09-019243-9.
2. Алгебра: 9 класс: учеб. для общеобразоват. учреждений / [Ю. Н. Макарычев, Н. Г. Миндюк, К. И. Нешков, С. Б. Суворова]; под ред. С. А. Теляковского. - 16-е изд. - М. : Просвещение, 2009. - 271 с. : ил. - ISBN 978-5-09-021134-5.
3. Мордкович А. Г. Алгебра. 9 класс. В 2 ч. Ч. 1. Учебник для учащихся общеобразовательных учреждений / А. Г. Мордкович, П. В. Семенов. - 13-е изд., стер. - М.: Мнемозина, 2011. - 222 с.: ил. ISBN 978-5-346-01752-3.
4. Мордкович А. Г. Алгебра и начала математического анализа. 11 класс. В 2 ч. Ч. 1. Учебник для учащихся общеобразовательных учреждений (профильный уровень) / А. Г. Мордкович, П. В. Семенов. - 2-е изд., стер. - М.: Мнемозина, 2008. - 287 с.: ил. ISBN 978-5-346-01027-2.
5. ЕГЭ -2013. Математика: типовые экзаменационные варианты: 30 вариантов / под ред. А. Л. Семенова, И. В. Ященко. – М.: Издательство «Национальное образование», 2012. – 192 с. – (ЕГЭ-2013. ФИПИ – школе).

Определение 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 .

37. Представление выпуклого многогранника

Определение 1. Замкнутое выпуклое ограниченное множество в R n , имеющее конечное число угловых точек , называется выпуклым n -мерным многогранником.

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

Определение 3 . Множество А R n называется ограниченным, если найдется n -мерный шар, содержащий это множество.

Определение 4. Выпуклой линейной комбинацией точек называется выражение, гдеt i , .

Теорема (теорема о представлении выпуклого многогранника). Любую точку выпуклого многогранника можно представить в виде выпуклой линейной комбинации его угловых точек.

38. Область допустимых решений системы уравнений и неравенств.

Пусть дана система из m линейных уравнений и неравенств с n неизвестными.

Определение 1 . Точка R n называется возможным решением системы, если ее координаты удовлетворяют уравнениям и неравенствам системы. Совокупность всех возможных решений называется областью возможных решений (ОВР) системы.

Определение 2. Возможное решение, координаты которого неотрицательны, называется допустимым решением системы. Множество всех допустимых решений называется областью допустимых решений (ОДР) системы.

Теорема 1 . ОДР является замкнутым, выпуклым, ограниченным (или неограниченным) подмножеством вR n .

Теорема 2. Допустимое решение системы является опорным тогда и только тогда, когда эта точка являетсяугловой точкой ОДР.

Теорема 3 (теорема о представлении ОДР). Если ОДР - ограниченное множество, то любое допустимое решение можно представить в виде выпуклой линейной комбинации угловых точек ОДР (в виде выпуклой линейной комбинации опорных решений системы).

Теорема 4 (теорема о существовании опорного решения системы). Если система имеет хотя бы одно допустимое решение (ОДР), то среди допустимых решений существует хотя бы одно опорное решение.

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

Помимо аналитической геометрии, материал актуален для ряда задач математического анализа, экономико-математического моделирования, поэтому рекомендую проштудировать данную лекцию со всей серьёзностью.

Линейные неравенства

Различают два типа линейных неравенств:

1) Строгие неравенства: .

2) Нестрогие неравенства: .

Какой геометрический смысл этих неравенств? Если линейное уравнение задаёт прямую, то линейное неравенство определяет полуплоскость .

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

Начнём с простейших линейных неравенств. Голубая мечта любого двоечника – координатная плоскость, на которой нет ничегошеньки:

Как известно, ось абсцисс задаётся уравнением – «игрек» всегда (при любом значении «икс») равняется нулю

Рассмотрим неравенство . Как его понимать неформально? «Игрек» всегда (при любом значении «икс») положителен. Очевидно, что данное неравенство определяет верхнюю полуплоскость – ведь там и находятся все точки с положительными «игреками».

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

Аналогично: неравенству удовлетворяют все точки нижней полуплоскости, нестрогому неравенству соответствует нижняя полуплоскость + ось .

С осью ординат та же самая прозаичная история:

– неравенство задаёт правую полуплоскость;
– неравенство задаёт правую полуплоскость, включая ось ординат;
– неравенство задаёт левую полуплоскость;
– неравенство задаёт левую полуплоскость, включая ось ординат.

На втором шаге рассмотрим неравенства, в которых отсутствует одна из переменных.

Отсутствует «игрек»:

Или отсутствует «икс»:

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

Пример 1

Решить линейные неравенства:

Что значит решить линейное неравенство?

Решить линейное неравенство – это значит найти полуплоскость , точки которой удовлетворяют данному неравенству (плюс саму прямую, если неравенство нестрогое). Решение , как правило, графическое .

Удобнее сразу выполнить чертёж, а потом всё закомментировать:

а) Решим неравенство

Способ первый

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

Правило : В неравенстве слагаемые переносятся из части в часть со сменой знака, при этом знак САМОГО неравенства не меняется (например, если был знак «меньше», то так и останется «меньше»).

Переносим «пятёрку» в правую часть со сменой знака:

Правило ПОЛОЖИТЕЛЬНОЕ не меняется .

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

Каков смысл неравенства ? «Икс» всегда (при любом значении «игрек») меньше, чем . Очевидно, что этому утверждению удовлетворяют все точки левой полуплоскости. Данную полуплоскость, в принципе, можно заштриховать, но я ограничусь маленькими синими стрелочками, чтобы не превращать чертёж в художественную палитру.

Способ второй

Это универсальный способ. ЧИТАЕМ ОЧЕНЬ ВНИМАТЕЛЬНО!

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

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

Получено неверное неравенство (простыми словами, так быть не может), значит, точка не удовлетворяет неравенству .

Ключевое правило нашей задачи :
не удовлетворяет неравенству, то и ВСЕ точки данной полуплоскости не удовлетворяют данному неравенству.
– Если какая-либо точка полуплоскости (не принадлежащая прямой) удовлетворяет неравенству, то и ВСЕ точки данной полуплоскости удовлетворяют данному неравенству.

Можете протестировать: любая точка справа от прямой не будет удовлетворять неравенству .

Какой вывод из проведённого опыта с точкой ? Деваться некуда, неравенству удовлетворяют все точки другой – левой полуплоскости (тоже можете проверить).

б) Решим неравенство

Способ первый

Преобразуем неравенство:

Правило : Обе части неравенства можно умножить (разделить) на ОТРИЦАТЕЛЬНОЕ число, при этом знак неравенства МЕНЯЕТСЯ на противоположный (например, если был знак «больше либо равно», то станет «меньше либо равно»).

Умножаем обе части неравенства на :

Начертим прямую (красный цвет), причём, начертим сплошной линией, так как неравенство у нас нестрогое , и прямая заведомо принадлежит решению.

Проанализировав полученное неравенство , приходим к выводу, что его решением является нижняя полуплоскость (+ сама прямая).

Подходящую полуплоскость штрихуем либо помечаем стрелочками.

Способ второй

Начертим прямую . Выберем произвольную точку плоскости (не принадлежащую прямой), например, и подставим её координаты в наше неравенство :

Получено верное неравенство , значит, точка удовлетворяет неравенству , и вообще – ВСЕ точки нижней полуплоскости удовлетворяют данному неравенству.

Здесь подопытной точкой мы «попали» в нужную полуплоскость.

Решение задачи обозначено красной прямой и красными стрелочками.

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

Пример 2

Решить линейные неравенства:

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

Думаю, после всех проделанных в примерах действий вам придётся на них жениться не составит труда решить простейшее неравенство вроде и т.п.

Переходим к рассмотрению третьего, общего случая, когда в неравенстве присутствуют обе переменные:

Как вариант, свободный член «цэ» может быть нулевым.

Пример 3

Найти полуплоскости, соответствующие следующим неравенствам:

Решение : Здесь используется универсальный метод решения с подстановкой точки.

а) Построим уравнение прямой , при этом линию следует провести пунктиром, так как неравенство строгое и сама прямая не войдёт в решение.

Выбираем подопытную точку плоскости, которая не принадлежит данной прямой, например, , и подставим её координаты в наше неравенство:

Получено неверное неравенство , значит, точка и ВСЕ точки данной полуплоскости не удовлетворяют неравенству . Решением неравенства будет другая полуплоскость, любуемся синими молниями:

б) Решим неравенство . Сначала построим прямую. Это сделать несложно, перед нами каноничная прямая пропорциональность . Линию проводим сплошняком, так как неравенство нестрогое.

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

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

Пример 4

Найти полуплоскости, соответствующие неравенствам:

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

Разберём обратную задачу:

Пример 5

а) Дана прямая . Определить полуплоскость, в которой находится точка , при этом сама прямая должна входить в решение.

б) Дана прямая . Определить полуплоскость, в которой находится точка . Сама прямая не входит в решение.

Решение : здесь нет необходимости в чертеже, и решение будет аналитическим. Ничего трудного:

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

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

Ответ :

Творческий пример для самостоятельного изучения:

Пример 6

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

Небольшая подсказка: сначала нужно составить неравенство, определяющее полуплоскость, в которой находится начало координат. Аналитическое решение и ответ в конце урока.

Системы линейных неравенств

Система линейных неравенств – это, как вы понимаете, система, составленная из нескольких неравенств. Лол, ну и определение выдал =) Ёжик – это ёжик, ножик – это ножик. А ведь правда – получилось просто и доступно! Нет, если серьёзно, не хочется приводить каких-то примеров в общем виде, поэтому сразу перейдём к насущным вопросам:

Что значит решить систему линейных неравенств?

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

В качестве простейших примеров рассмотрим системы неравенств, определяющих координатные четверти прямоугольной системы координат («рисунок двоечников» находится в самом начале урока):

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

Аналогично:
– система неравенств задаёт вторую координатную четверть (левая верхняя);
– система неравенств задаёт третью координатную четверть (левая нижняя);
– система неравенств задаёт четвёртую координатную четверть (правая нижняя).

Система линейных неравенств может не иметь решений , то есть, быть несовместной . Снова простейший пример: . Совершенно очевидно, что «икс» не может одновременно быть больше трёх и меньше двух.

Решением системы неравенств может являться прямая, например: . Лебедь, рак, без щуки, тянут воз в две разные стороны. Да воз и ныне там – решением данной системы является прямая .

Но самый распространённый случай, когда решением системы является некоторая область плоскости . Область решений может быть не ограниченной (например, координатные четверти) либо ограниченной . Ограниченная область решений называется многоугольником решений системы .

Пример 7

Решить систему линейных неравенств

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

Решение : то, что неравенств многовато, пугать не должно. Сколько может быть неравенств в системе? Да сколько угодно. Главное, придерживаться рационального алгоритма построения области решений:

1) Сначала разбираемся с простейшими неравенствами. Неравенства определяют первую координатную четверть, включая границу из координатных осей. Уже значительно легче, так как область поиска значительно сузилась. На чертеже сразу отмечаем стрелочками соответствующие полуплоскости (красные и синие стрелки)

2) Второе по простоте неравенство – здесь отсутствует «игрек». Во-первых, строим саму прямую , а, во-вторых, после преобразования неравенства к виду , сразу становится понятно, что все «иксы» меньше, чем 6. Отмечаем зелёными стрелками соответствующую полуплоскость. Ну что же, область поиска стала ещё меньше – такой не ограниченный сверху прямоугольник.

3) На последнем шаге решаем неравенства «с полной амуницией»: . Алгоритм решения мы подробно рассмотрели в предыдущем параграфе. Вкратце: сначала строим прямую, потом с помощью подопытной точки находим нужную нам полуплоскость.

Встаньте, дети, встаньте в круг:


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

Любая точка данного многоугольника удовлетворяет КАЖДОМУ неравенству системы (для интереса можете проверить).

Ответ : решением системы является многоугольник .

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

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

Пример 8

Решить систему

Решение и ответ в конце урока. У вас, скорее всего, будут другие буквенные обозначения вершин полученной области. Это не принципиально, главное, правильно найти вершины и правильно построить область.

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

Пример 9

Решить систему и найти координаты вершин полученной области

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

Графический метод.. 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 – базисные неизвестные. Их надо выразить через свободные неизвестные и произвести их замену в целевой функции.

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

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

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

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

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

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