Решение задач с ограничениями в виде уравнений

Видео:АЛГЕБРА 7 класс : Решение задач с помощью уравнений | ВидеоурокСкачать

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

В большинстве учебников при подготовке к ЕГЭ по математике рассматриваются задачи C1, состоящие из тригонометрических уравнений. Учителя рассказывают о многочисленных приемах работы с тригонометрией, но совершенно упускают из виду, что существует множество задач C1 совсем другого типа. Например, вместо «классического» тригонометрического уравнения может стоять показательное и логарифмическое. На первый взгляд, такие уравнения решаются даже легче, однако основные проблемы начинаются дальше — в процессе отборе корней.

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

Видео:Решение задач с помощью уравнений. Видеоурок 29. Математика 6 классСкачать

Правила работы со степенями

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

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

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

Решаем задачу

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

25 x− 3 2 −12⋅ 5 x−2 +7=0,x∈ ( 2; 8 3 )

Давайте внимательно посмотрим на наше показательное уравнение: у нас есть 5 в каком-то степенном значении и 25, кроме того, 25= 5 2 25=<^>. Теперь мы можем переписать наше исходное уравнение следующим образом:

( 5 2 ) x− 3 2 −12⋅ 5 x−2 +7=0

Вот здесь мы вспоминаем формулу возведения степени в степень:

5 2⋅ ( x− 3 2 ) −12⋅ 5 x−2 +7=0

5 2x−3 −12⋅ 5 x−2 +7=0

5 2x−4+1 −12⋅ 5 x−2 +7=0

5 2x−4 ⋅ 5 1 −12⋅ 5 x−2 +7=0

5 2 (x−2) ⋅5−12⋅ 5 x−2 +7=0

Обратите внимание: на каждом шаге преобразовании мы работали исключительно с первым элементом, который изначально звучал как 25 x− 3 2 <^<x-frac>>. В итоге мы получил конструкцию вида 5 2(x−2) ⋅5 <^>cdot 5. Возникает сразу два вопроса: в первую очередь, зачем нам нужно было это делать?

Потому что теперь мы можем сделать следующую замену:

5 x−2 =t −12⋅ 5 x−2 +7=0

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

Но есть одна проблема: как добавить 1 и вычесть ее на одном из шагов? Все очень просто. У нас уже есть готовая конструкция 5 x−2 <^>. Следовательно, при возведении ее в квадрат, мы должны перемножить степенные показатели:

5 x−2 = 5 (x−2)2 = 5 2x−4

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

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

Очевидно, поскольку перед t 2 <^> стоит 5, это уравнение не является приведенным, поэтому решать мы его будем через дискриминант. Итак, дискриминант равен:

D=144-4cdot 5cdot 7=4

Корень равен 2. Находим t t:

Итак, мы получили корни квадратного уравнения: 7 5 frac и 1. Теперь возвращаемся к нашему исходному выражению и вспоминаем, что t= 5 x−2 t=<^>:

5 x−2 =1 5 x−2 = 5 0 x−2=0 x=2

Подставляем второй корень:

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

5 x−2 = 5 log 5 7 5

Почему мы выбрали основание именно 5? Потому что у нас слева стоит 5 x−2 <^>, т. е. основание у нас задается самим уравнением. Теперь мы можем избавиться от 5:

Вот наши два ответа: 2 и log535.

Мы решили первую часть задачи и нашли корни. Теперь из этих корней нам нужно отобрать те, которые принадлежат интервалу [left( 2;frac right)].

Для этого давайте для начала перепишем значения, входящие в сам интервал. Дело в том, что 8 3 frac — это дробь, поэтому из нее нужно выделить целую часть. Интервал будет выглядеть следующим образом:

x˜in left( 2;2frac right)

Из двух корней, 2 и log535, нам нужно выбрать такие числа, которые принадлежат нашему интервалу. В первую очередь, давайте сразу заметим, что x=2 x=2 не принадлежит нашему интервалу:

xnotin left( 2;2frac right)

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

Остается лишь один корень log535. Разумеется, поскольку это один единственный ответ нашего показательного выражения, то у нас есть все основания полагать, что он лежит на данном интервале, однако если мы не обоснуем это утверждение, то проверяющие снимут из нас 1 балл. Другими словами, нам нужно доказать, что число log535 лежит на нашем интервале. Но проблема в том, что мы не знаем, чему равен log535. И как поступать в таком случае? Сейчас внимание! Я расскажу вам четкий пошаговый алгоритм, который часто требуется применять в задачах С1, С3 и С5 из ЕГЭ по математике, т. е. всех алгебраических задачах части С.

Видео:РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ УРАВНЕНИЙ. §3 алгебра 7 классСкачать

Пошаговый алгоритм решения задач

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

Мы просто перебираем 5 натурального степенного значения. Получим:

log 5 5 1 = log 5 5

log 5 5 2 = log 5 25

log 5 5 3 = log 5 125

Разумеется, можно было бы выписать больше, но нам важно понять, между какими числами видами 5, 25 и 125, лежит наше исходное 35. Очевидно, оно лежит между 25 и 125. Следовательно, log535 будет лежать между

<_>125. Также мы можем посчитать показательное выражение:

Отсюда заключаем, что

˜2 ( 2;2 2 3 ) left( 2;2frac right), т. е. то, что логарифм лежит на промежутке от 2 до 3, нам не помогает. Поэтому переходим к следующему шагу и начинаем рассматривать половинки, значения вида 1,5; 2,5; 3,5. Давайте посмотрим: возьмем среднее арифметическое чисел 2 и 3 и возводим 5 в степень этого среднего арифметического:

log 5 5 2+3 2 = log 5 5 2,5 = log 5 5 2 ⋅ 5 1 2 = log 5 25 5 √

А теперь нам нужно понять, что больше

25sqrt или 35. Давайте сравним их:

7bigcup 5sqrtuparrow 2

49bigcup 25cdot 5

49 log 5 35 log 5 25 5 √

<_>35 ˜ 2 log 5 35 5 10

˜2 2 log 5 35 2 5 10 2 3

=<_>35 после отбора с учетом ограничений.

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

<_>35 будет лежать между

<_>125, и мы получили такое неравенство

2 5 1,5 <^> или 5 2,5 <^>, у нас, естественно, получаются корни, которые потом придется сравнивать при помощи галочки неизвестности. Однако не стоит переживать, это сравнение не вызывает каких-либо сложностей, и после небольшой тренировки сравнивать корни таким образом сможет даже неподготовленный ученик. В результате мы получили уточненное ограничение, которое уже точно даст нам понять, принадлежит ли наш корень данному интервалу или не принадлежит.

Обратите внимание, более глубокого разделения, т. е. уже на четверти, а не на половинки в реальной части С ЕГЭ по математике я не видел ни разу, т. е. шага выписывания половинок уже будет достаточно. Более сложное задание на настоящем ЕГЭ по математике вам точно не попадется. Вот и все, получив уточненное ограничение, вы уже сможете обоснованно утверждать, что данный корень принадлежит указанному интервалу. И, следовательно, является ответом ко второй части задачи. Вы получите два балла из двух возможных на ЕГЭ по математике. Так что обязательно изучите этот прием. Он будет очень полезен не только в задачах С1 в ЕГЭ по математике, но также и в задачах С3 и С5.

Видео:Графический метод решения задачи линейного программирования (ЗЛП)Скачать

Ключевые моменты

На примере этой задачи C1из ЕГЭ по математике хочу прояснить сразу два принципиально важных моментов:

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

Если при решении показательного уравнения возник «некрасивый логарифм» (в нашем случае это

<_>35), для получения его примерного значения сначала считайте натуральные степенные показатели:

<_>52; log 5 5 3 <_><^> . Если же этих ограничений окажется недостаточно, начинайте перебирать числа, стоящие посередине между соседними натуральными:

Видео:Решение задачи линейного программирования при помощи надстройки Поиск решенияСкачать

Линейное программирование — основные понятия с примерами решения

Содержание:

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

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

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

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

Построение математической модели экономической задачи включает следующие этапы:

1. выбор переменных задачи;
2. составление системы ограничений;
3. выбор целевой функции.

Переменными задачи называются величины

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

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

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

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

Данная запись означает следующее: найти экстремум целевой функции задачи и соответствующие ему переменные X = (). при условии, что эти переменные удовлетворяют системе ограничений и условиям неотрицательности.

Допустимым решением (планом) задачи линейного программирования называется любойX = (). удовлетворяющий системе ограничений и условиям неотрицательности. Множество допустимых решений (планов) задачи образует область допустимых решений.

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

Видео:Математика 6 класс (Урок№51 - Решение задач с помощью уравнений. Часть 1.)Скачать

Задача линейного программирования

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

Используя знак суммирования эту задачу можно записать следующим образом:

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

В данном случае введены векторы:

Здесь С — X — скалярное произведение векторов С и X.

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

Здесь А — матрица коэффициентов системы уравнений, X -матрица-столбец переменных задачи; — матрица-столбец правых частей системы ограничений.

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

Приведение общей задачи линейного программирования к канонической форме

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

прибавляется величина такая, что переводит неравенство в равенство , где:

Неотрицательная переменная называется дополнительной переменной.

Основания для возможности такого преобразования дает следующая теорема.

Теорема. Каждому решению неравенства соответствует единственное решение уравнения: и неравенства и, наоборот, каждому решению уравнения: и неравенства соответствует единственное решение неравенства:

Доказательство. Пусть — решение неравенства. Тогда:

Если в уравнение вместо переменных подставить значения , получится:

Таким образом, решение удовлетворяет уравнению: и неравенству .

Доказана первая часть теоремы.

Пусть удовлетворяет уравнению и неравенству , т.е. . Отбрасывая в левой части равенства неотрицательную величину , получим:

т.е. удовлетворяет неравенству: что и требовалось доказать.

Если в левую часть неравенств системы ограничений вида

добавить переменную , то получится система ограничений — уравнений В случае, если система неравенств-ограничений имеет вид , то из левой части неравенств-ограничений нужно вычесть соответствующую неотрицательную дополнительную переменную

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

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

В реальных практических задачах дополнительные неизвестные имеют определенный смысл. Например, если левая часть ограничений задачи отражает расход ресурсов на производство продукции в объемах , а правые части — наличие производственных ресурсов, то числовые значения дополнительных неизвестных и означают объем неиспользованных ресурсов i-го вида.

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

Множества допустимых решений

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

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

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

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

Граничные точки множества образуют его границу. Множество называется замкнутым, если оно содержит все свои граничные точки.

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

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

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

Так, угловые точки треугольника — его вершины, круга — точки окружности, ее ограничивающие, а прямая, полуплоскость, плоскость, полупространство, пространство не имеют угловых точек.

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

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

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

Уравнение целевой функции при фиксированных значениях самой функции является уравнением прямой линии (плоскости, гиперплоскости и т.д.). Прямая, уравнение которой получено из целевой функции при равенстве ее постоянной величине, называется линией уровня.

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

Теорема. Значения целевой функции в точках линии уровня увеличиваются, если линию уровня перемещать параллельно начальному положению в направлении нормали и убывают при перемещении в противоположном направлении.

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

Опорное решение задачи линейного программирования, его взаимосвязь с угловыми точками

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

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

Базисным решением системы называется частное решение, в котором неосновные переменные имеют нулевые значения. Любая система уравнений имеет конечное число базисных решений, равное , где n — число неизвестных, r- ранг системы векторов условий. Базисные решения, координаты которых удовлетворяют условию неотрицательности, являются опорными.

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

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

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

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

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

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

Пример:

Графический метод решения задачи линейной оптимизации рассмотрим на примере задачи производственного планирования при n = 2.

Предприятие изготавливает изделия двух видов А и В. Для производства изделий оно располагает сырьевыми ресурсами трех видов С, D и Е в объемах 600, 480 и 240 единиц соответственно. Нормы расхода ресурсов на единицу продукции каждого вида известны и представлены в табл. 14.1

Прибыль от реализации изделия А составляет 40 млн. руб., а изделия В — 50 млн.руб. Требуется найти объемы производства изделий А и В, обеспечивающие максимальную прибыль.

Построим математическую модель задачи, для чего обозначим — объемы производства изделий А и В соответственно.

Тогда прибыль предприятия от реализации изделий А и изделий В составит:

Ограничения по ресурсам будут иметь вид:

Естественно, объемы производства должны быть неотрицательными

Решение сформулированной задами найдем, используя геометрическую интерпретацию. Определим сначала многоугольник решений, для чего систему ограничений неравенств запишем в виде уравнений и пронумеруем их:

Каждое из записанных уравнений представляет собой прямую на плоскости, причем 4-я и 5-я прямые являются координатными осями.

Чтобы построить первую прямую, найдем точки ее пересечения с осями координат: а при .

Далее нас интересует, по какую сторону от прямой будет находиться полуплоскость, соответствующая первому неравенству. Чтобы определить искомую полуплоскость, возьмем точку O(0,0) подставив ее координаты в неравенство, видим, что оно удовлетворяется. Так как точка O(0,0) лежит левее первой прямой, то и полуплоскость будет находиться левее прямой

. На рис 14 , расположение полуплоскости относительно первой прямой отмечено стрелками.

Аналогично построены 2-я и 3-я прямые и найдены полуплоскости, соответствующие 2-му и 3-му неравенству. Точки, удовлетворяющие ограничениям , находятся в первом квадранте. Множество точек, удовлетворяющих всем ограничениям одновременно, является ОДР системы ограничений. Такой областью на графике (рис. 14.1) является многоугольник ОАВС.

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

Чтобы найти эту точку, приравняем функцию к нулю и построим соответствующую ей прямую. Вектор-градиент прямой функции

имеет координаты

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

Решив эту систему, получаем, что

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

Алгоритм решения задачи линейного программирования графическим методом таков:

1. Строится область допустимых решений;
2. Строится вектор нормали к линии уровня с точкой приложении в начале координат;
3. Перпендикулярно вектору нормали проводится одна из линий уровня, проходящая через начало координат;
4. Линия уровня перемещается до положения опорной прямой. На этой прямой и будут находиться максимум или минимум функции.

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

На рис. 14.3 показан случай, когда прямая функции параллельна отрезку АВ, принадлежащему ОДР. Максимум функции Z достигается в точке А и в точке В, а, следовательно, и в любой точке отрезка АВ, т.к. эти точки могут быть выражены в виде линейной комбинации угловых точек А и В.

На рисунке 14.4 изображен случай, когда система ограничений образует неограниченное сверху множество. Функция Z в данном случае стремится к бесконечности, так как прямую функции можно передвигать в направлении вектора градиента как угодно далеко, а на рисунке 14.5 представлен случай несовместной системы ограничений.

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

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

Симплекс-метод основан на следующих свойствах задачи линейного программирования:

• Не существует локального экстремума, отличного от глобального. Другими словами, если экстремум есть, то он единственный.
• Множество всех планов задачи линейного программирования выпукло.
• Целевая функция ЗЛП достигает своего максимального (минимального) значения в угловой точке многогранника решений (в его вершине). Если целевая функция принимает свое оптимальное значение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек.
• Каждой угловой точке многогранника решений отвечает опорный план ЗЛП.

Рассмотрим две разновидности симплексного метода: симплекс-метод с естественным базисом и симплекс-метод с искусственным базисом (или М-метод).

Симплекс-метод с естественным базисом

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

Для определенности предположим, что первые m векторов матрицы системы составляют единичную матрицу. Тогда очевиден первоначальный опорный план:

Проверка на оптимальность опорного плана проходит с помощью критерия оптимальности, переход к другому опорному плану — с помощью преобразований Жордана-Гаусса и с использованием критерия оптимальности.

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

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

Теорема 1. Если для некоторого вектора, не входящего в базис, выполняется условие:

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

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

Теорема 2. Если для всех векторов выполняется условие то полученный план является оптимальным.

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

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

Строка называется направляющей, столбец и элемент — направляющими (последний называют также разрешающим элементом).

Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по формулам:

а элементы любой другой i-й строки пересчитываются по формулам:

Значения базисных переменных нового опорного плана (показатели графы «план») рассчитываются по формулам:

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

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

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

Симплексный метод с искусственным базисом (М-метод)

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

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

В полученной задаче первоначальный опорный план очевиден. При применении к этой задаче симплекс-метода оценки А, теперь будут зависеть от числа М. Для сравнения оценок нужно помнить, что М — достаточно большое положительное число, поэтому из базиса будут выводиться в первую очередь искусственные переменные.

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

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

Теория двойственности

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

Любую задачу линейного программирования можно записать в виде:

Первоначальная задача называется исходной или прямой.

Модель двойственной задачи имеет вид:

Переменные двойственной задачи называют объективно обусловленными оценками или двойственными оценками.

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

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

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

При копировании любых материалов с сайта evkova.org обязательна активная ссылка на сайт www.evkova.org

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

Сайт пишется, поддерживается и управляется коллективом преподавателей

Whatsapp и логотип whatsapp являются товарными знаками корпорации WhatsApp LLC.

Cайт носит информационный характер и ни при каких условиях не является публичной офертой, которая определяется положениями статьи 437 Гражданского кодекса РФ. Анна Евкова не оказывает никаких услуг.

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

Решение задач с ограничениями в виде уравнений

5. Многомерная оптимизация

Оптимизация – это целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Количественная оценка оптимизируемого качества называется критерием оптимальности или целевой функцией. Её можно записать в виде:

где x ₁ , x ₂ , … , x_n – некоторые параметры объекта оптимизации.

Существуют два типа задач оптимизации – безусловные и условные.

Безусловная задача оптимизации состоит в отыскании максимума или минимума действительной функции (5.1) от n действительных переменных и определении соответствующих значений аргументов.

Условные задачи оптимизации , или задачи с ограничениями, — это такие, при формулировке которых на значения аргументов налагаются ограничения в виде равенств или неравенств.

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

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

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

Пусть из двух видов сырья изготавливается продукция двух видов.

Обозначим: x ₁ , x ₂ – число единиц продукции первого и второго вида, соответственно; c ₁ , c ₂ – цена единицы продукции первого и второго вида, соответственно. Тогда общая стоимость всей продукции будет :

В результате производства желательно, чтобы общая стоимость продукции была максимальной. R ( x ₁ , x ₂ ) – целевая функция в данной задаче.

b ₁ , b ₂ – количество сырья первого и второго видов, имеющееся в наличии; a _ij – число единиц i -го вида сырья, необходимое для производства единицы j -го вида продукции.

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

Относительно переменных x ₁ , x ₂ можно ещё сказать, что они неотрицательны и не бесконечны .:

Среди множества решений системы неравенств (5.3) и (5.4) требуется найти такое решение ( x ₁ , x ₂ ), для которого функция R достигает наибольшего значения.

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

Графический метод решения задачи линейного программирования.

Пусть требуется найти x ₁ и x ₂ , удовлетворяющие системе неравенств:

и условиям неотрицательности :

для которых функция

Построим в системе прямоугольных координат x ₁ Ox ₂ область допустимых решений задачи (рис.11). Для этого, заменяя каждое из неравенств (5.5) равенством, строим соответствующую ему граничную прямую:

Эта прямая делит всю плоскость на две полуплоскости. Для координат x ₁ , x ₂ любой точки А одной полуплоскости выполняется неравенство:

а для координат любой точки В другой полуплоскости – противоположное неравенство:

Координаты любой точки граничной прямой удовлетворяют уравнению:

Для определения того, по какую сторону от граничной прямой располагается полуплоскость, соответствующая заданному неравенству, достаточно «испытать» одну какую-либо точку (проще всего точку О (0;0)). Если при подстановке её координат в левую часть неравенства оно удовлетворяется, то полуплоскость обращена в сторону к испытуемой точке, если же неравенство не удовлетворяется, то соответствующая полуплоскость обращена в противоположную сторону. Направление полуплоскости показывается на чертеже штриховкой. Неравенствам:

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

На рисунке строим граничные прямые и полуплоскости, соответствующие всем неравенствам.

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

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

Рис. 12. Область допустимых решений пустая, что соответствует несовместности системы неравенств; решения нет

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

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

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

Графическое изображение целевой функции

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

перпендикулярный к линиям уровня, показывает направление возрастания R .

Задача отыскания оптимального решения системы неравенств (5.5), для которого целевая функция R (5.7) достигает максимума, гео­метрически сводится к определе­нию в области допустимых реше­ний точки, через которую пройдет линия уровня, соответствую­щая наибольшему значении пара­метра R

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

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

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

Пусть требуется найти значения x ₁ и x ₂ , удовлетворяющие системе неравенств:

и условиям неотрицательности :

для которых функция:

Заменим каждое из неравенств равенством и построим граничные прямые:

Определим полуплоскости, соответствующие данным неравенствам, путём «испытания» точки (0;0). С учетом неотрицательности x ₁ и x ₂ получим область допустимых решений данной задачи в виде выпуклого многоугольника ОАВДЕ.

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

показывающий направление возрастания R .

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

Задания. Найти положение точки экстремума и экстремальное значение целевой функции

🎦 Видео

Урок по теме РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ СИСТЕМЫ УРАВНЕНИЙ 7 КЛАСССкачать

СИМПЛЕКС МЕТОД: ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯСкачать

Урок 14 Решение задач с помощью уравнений (5 класс)Скачать

Решение задач с помощью уравнений.Скачать

Cимплексный метод решения задачи линейного программирования (ЗЛП)Скачать

Алгоритм решения задач с помощью систем уравнений. Практическая часть. 9 класс.Скачать

Как решать уравнения с модулем или Математический торт с кремом (часть 1) | МатематикаСкачать

Алгебра 7 класс (Урок№44 - Решение задач с помощью линейных уравнений.)Скачать

Дробно-рациональные уравнения. 8 класс.Скачать

Решение задач с помощью уравнений. 6 классСкачать

Графический метод решения задач линейного программирования | Высшая математика TutorOnlineСкачать

Алгоритм решения задач с помощью систем уравнений. Практическая часть. 9 класс.Скачать