Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Методы оптимизации
Лекции по дисциплине
База знаний бэкмологии включает расширенные курсы по следующим дисциплинам:
Отдельные дисциплины, которые не входят в базу знаний бэкмологии, но могут понадобиться ее пользователям, предоставляются в виде традиционных электронных изданий в формате DOC и PDF.
Официальный сайт: becmology.ru
Блог: http://becmology.blogspot.com/
Оглавление
|
[1] Введение [1.0.0.1] Общая постановка задачи. [2] Линейное программирование. [2.1] Постановка задачи линейного программирования [2.1.0.1] Определение [2.1.0.2] Так, например, ограничение [2.2] Выпуклые множества и выпуклые функции [2.2.0.1] Определение. [2.2.0.2] Замечание. [2.2.0.3] Определение. [2.2.0.4] Замечание. [2.2.0.5] Примеры. [2.3] Определение экстремума и его виды [2.3.0.1] Определение. [2.3.0.2] Определение. [2.3.0.3] Определение. [2.3.0.4] Замечание. [2.3.0.5] Определение. [2.3.0.6] Определение. [2.3.0.7] Определение. [2.3.0.8] Замечания. [2.3.0.9] Замечание. [2.4] Основные задачи линейного программирования [2.4.0.1] Замечание. [2.4.0.2] Определение. [2.4.0.3] Определение. [2.4.0.4] Замечание. [2.4.0.5] Определение. [2.4.0.6] Замечания. [2.4.0.7] Пример. [2.5] Типовые задачи [2.5.0.1] Транспортная задача. [2.5.0.2] Задача о рациональном питании. [2.5.0.3] Задача об использовании ресурсов. [2.5.0.4] Задача о загрузке транспорта. [2.6] Геометрический подход к решению задач линей ного програм мирования [2.6.0.1] Теорема. [2.6.0.2] Доказательство: [2.6.0.3] Замечание. [2.7] Геометрический поиск решения задачи линейного програм мирования для двухмерного случая [2.7.0.1] Примеры. [2.7.0.2] Таблица . [2.7.0.3] Решение: [2.7.0.4] В силу условий задачи должны выполнятся условия: [2.7.0.5] Решение: [2.7.0.6] Решение: [2.7.0.7] Задание. [2.8] Симплекс метод решения задач линейного программирования [2.8.0.1] Табличный алгоритм симплекс метода [2.8.0.2] Табл. 3.Симплекс таблица для третей итерации. [2.8.0.3] Пример реализации данного алгоритма в MATLAB. [2.8.0.4] Недостатки симплекс метода. [2.9] Двойственные задачи линейного програм мирования [2.9.0.1] Определение [2.9.0.2] Пример [2.9.0.3] Пример [2.9.0.4] Связь между решениями прямой и двойственной задач. [2.9.0.5] Лемма 1. [2.9.0.6] Лемма 2. [2.9.0.7] Теорема (первая теорема двойственности). [2.9.0.8] Теорема (вторая теорема двойственности). [2.9.0.9] Геометрическая интерпретация двойственных задач. [2.9.0.10] Пример. [2.9.0.11] Пример [2.9.0.12] Решение. [2.9.0.13] Теорема. [2.9.0.14] Пример. [2.9.0.15] Решение. [2.9.0.16] Таблица 12 [2.9.0.17] Экономическая интерпретация двойственных задач [2.9.0.18] Пример [2.9.0.19] Таблица [2.9.0.20] Таблица [3] Безусловная оптимизация (многомерные функции) [3.1] Безусловная оптимизация. Основные понятия [3.1.0.1] Определение [3.1.0.2] Общая схема безусловной оптимизации [3.2] Методы первого порядка (градиентные методы). Градиентный метод с постоянным шагом [3.3] Градиентный метод с дроблением шага. [3.4] Метод наискорейшего спуска. [3.4.0.1] Графическая интерпретация: [3.5] Масштабирование [3.6] Метод Ньютона. [3.6.0.1] Понятие о скорости сходимости [3.7] Сравнение достоинств и недостатков градиентного метода и метода Ньютона [3.7.0.1] Сравнительная таблица достоинств и недостатков градиентного метода и метода Ньютона: [3.7.0.2] Число обусловленности локального min. [3.8] Многошаговые ( двухшаговые ) методы. Метод тяжелого шарика [3.9] Метод сопряженных градиентов [3.10] Модификация Полака-Ривьера [3.11] Квазиньютоновские методы [3.12] Метод Давидона- Флетчера- Пауэлла (ДФП) [3.12.0.1] Метод Бройдена-Флетчера –Шенно. [3.13] Методы нулевого порядка (методы прямого поиска). Методы аппроксимации [3.13.0.1] Метод покоординатного спуска [3.13.0.2] Метод симплексов (Нелдера-Мида) [3.13.0.3] Метод Пауэлла (сопряженных направлений) [3.14] Методы прямого поиска в задачах одномерной минимизации. Метод квадратичной интерполяции. [3.15] Метод дихотомии ( половинного деления.). [3.16] Метод «золотого» сечения. [3.17] Метод Фибоначчи [4] Условная минимизация [5] Решение переборных задач [5.1] Метод ветвей и границ [5.2] Задача о коммивояжере. [5.3] Динамическое программирование [5.3.0.1] Абстрактная схема. [6] Практическое занятие №1. Динамическое программирование [6.1] Общие указания к выполнению практической работы. [6.2] Цель работы [6.3] Постановка задачи [6.3.0.1] 8.2. Формулировка задания. [6.3.0.2] Определение. [6.3.0.3] Пример. [6.3.0.4] Переходы можно представить также с помощью таблицы и схематически: [6.3.0.5] Определение. [6.4] Последовательность выполнения. [6.5] Методический пример. [6.6] Контрольная распечатка. [6.7] Замечания. [6.8] Отчет по практической работе. [6.9] Контрольные вопросы [6.10] Варианты заданий. [7] Задания для домашней работы [7.1] Линейное программирование. [8] Список литературы |
Методы оптимизации представляют одну из базовых дисциплин, изучаемых в технических вузах, наиболее близка она студентам, изучающим математику, информатику и программирование.
Общая постановка задачи.
Найти значение переменных x1, x2,…, xn, доставляющих экстремум некоторой функции = ( x1, x2,…, xn) и удовлетворяющих ряду ограничений , .
Функция = (x1, x2,…,xn) называется целевой функцией; ограничения указывают область определения задачи.
Величины m, n, вообще говоря, не связаны. Обычно n 1, m 0. Практически бывают еще специфические ограничения вида: и требование целочисленности.
Сегодня методы оптимизации являются важным звеном математического образования. Умение пользоваться математическими методами оптимизации является обязательным квалификационным требованием к специалистам в области информационных технологий и программного обеспечения.
Задача линейного программирования состоит в следующем: находятся такие переменные x1, x2,…,xn, которые доставляют экстремум линейной функции
(.)
при условиях
(.)
где – известные константы и .
Определение
Функция экстремум которой ищется,
называется целевой функцией.
Словесно задачу линейного программирования можно сформулировать так: требуется найти такие значения n переменных , которые доставляют экстремум (максимум или минимум) линейной формы от n переменных при m ограничениях в виде неравенств или равенств. Нетрудно убедиться, что всегда можно говорить только о равенствах, так как введением дополнительных или слабых переменных неравенства всегда можно свести к строгим равенствам.
Так, например, ограничение
(.)
можно свести к равенству, добавив переменную xn+1:
. (.)
В этом случае условие (1.3) сводится к условию (1.4) и условию неотрицательности xn+1.
Таким образом, задача линейного программирования, путём введения в случае необходимости вспомогательных переменных, сведена к стандартной форме, к так называемой основной задаче линейного программирования (ОЗЛП).
Определение.
Множество S в Rn называется выпуклым множеством, если для любых точек , точки принадлежат S при всех .
Замечание.
Эта формула может быть записана также в следующем виде:
, ,
где .
Геометрически это означает, что если x1 и x2 принадлежат S, то отрезок прямой, соединяющий эти две точки, также принадлежит S. Таким образом, выражение (1) является параметрическим представлением отрезка прямой, соединяющей x1 и x2 (см. рис.).
Рис. .. Пример выпуклого множества на плоскости.
Определение.
Функция , определенная на выпуклом множестве S, называется выпуклой, если выполняется неравенство
,
где , или
,
где , .
Замечание.
С геометрической точки зрения это уравнение устанавливает, что между любыми двумя точками на графике функции график лежит ниже хорды, соединяющей точки и (рис.1.6.2).
Рис. .. Выпуклая функция.
Из рисунка видно, что точка P имеет координаты , .
Примеры.
Множество точек, удовлетворяющих неравенству
является выпуклым, когда матрица Q вещественна, симметрична и положительно полуопределена.
Действительно,
{согласно неравенству Коши-Буняковского-Шварца}
{согласно (1)}
.
При n = 2 это множество представляет собой совокупность точек, лежащих внутри эллипса.
Пусть n = 2, Q – знакоопределенная матрица, то есть пусть .
Тогда множеством точек являются точки, координаты которых x1 и x2 удовлетворяют условию . Это множество – невыпуклое. Так, например, отрезок, соединяющий точки A и B, не содержится в указанном множестве (рис.1.6.3).
Рис. .. Невыпуклое множество на плоскости.
Рассмотрим пространство Rn. В нём расстояние или метрику можно ввести вполне определенным образом. Рассмотрим четыре метрических пространства со следующими метриками:
а) ,
б) ,
в) ,
г) ,
где M – положительно определенная симметричная – матрица.
Рис. .. Точки, равноудаленные от начала координат, соответствующие различно определённым расстояниям.
На рисунке показаны геометрические места точек, равноудаленных от начала координат, соответствующие четырём различно определенным расстояниям для n=2. Множество точек, например, с , где ,– это выпуклые множества. На рисунке 1.6.4. это множества области с началом координат {точкой }, ограниченные соответствующими кривыми.
Как известно из математического анализа, функция скалярной переменной может иметь в заданном интервале более одного локального или относительного экстремума. Аналогично и функция n переменных в заданной области пространства Rn может обладать несколькими экстремумами.
Определение.
Функция называется унимодальной в данной области, если она в этой области имеет единственный экстремум. В противном случае она называется мультимодальной.
Определение.
-окрестностью точки x0N называется такое множество точек xN, для которых (рис. 1.5).
Рис. .. Окрестность N точки x0 и область S определения функции.
Определение.
Пусть (x) определена в подмножестве S пространства Rn. Функция (x) достигает локального [строго локального] минимума в точке x0S, если существует окрестность N(x0) такая, что
для и S отлична от x0.
Замечание.
То, что x0 является локальным минимумом, не исключает возможности существования другой точки x* S вне малой окрестности N(x0), для которой (x*) (x0).
Определение.
Если (x*) (x) (x*) (x) для всех x S, отличных от x*, то x* является глобальным [строгим глобальным] минимумом функции (x) на S.
При этом число (x*) есть минимальное значение функции на S.
Определение.
Функция (x) достигает локального [строго локального] максимума в точке x0S, если существует окрестность N(x0) такая, что
(x) (x0) (x) (x0) для xN(x0) и S отлична от x0.
Определение.
Если (x*) (x) (x*) (x) для всех xS, отличных от x*, то x* является глобальным [строгим глобальным] максимумом функции (x) на S. При этом число (x*) есть максимальное значение функции на S.
Замечания.
Если функция не унимодальна в S, то в общем случае локальный и глобальный экстремумы (минимумы или максимумы) могут различаться. Все известные методы позволяют определять локальный, а не глобальный экстремум. В задачах минимизации часто приходится сталкиваться со многими локальными минимумами. Только при некоторых дополнительных условиях локальный минимум будет совпадать с глобальным.
Замечание.
Заметим, что для произвольной целевой функции = (x1, x2,…,xn) имеет место:
Max = min(–) и min = max(–).
Требуется найти такие значения переменных x1, x2, …, xn, которые минимизируют целевую функцию
(.)
при m < n линейных ограничениях – равенствах
, (.)
и n линейных ограничениях – неравенствах
. (.)
Замечание.
Строгое неравенство сильно усложняет задачу. Например, найти x1 доставляющий z=x1 максимум при x1<1. Решение в этом случае не (1.1).
Рисунок . . Максимум при x1<1 не существует.
Определение.
Допустимым решением или планом задачи линейного программирования, данной в стандартной форме, называется упорядоченное множество чисел (x1, x2, …, xn) (то есть точка n-мерного пространства Rn), удовлетворяющих ограничениям вида (1.6) и (1.7).
Определение.
Оптимальным решением или оптимальным планом называется допустимое решение, минимизирующее целевую функцию, представляющую собой линейную форму вида (1.5).
Замечание.
Чаще всего оптимальное решение, если оно существует, единственно, однако возможны случаи, когда оптимальных решений бесчисленное множество. Для существования допустимого решения необходимо, (но не достаточно), чтобы система (1.6) была совместна.
В дальнейшем при решении задачи линейного программирования считается, что система (1.6) совместна и ранг матрицы системы равен В этом случае r линейно независимых уравнений системы (1.6) определяют некоторые r неизвестных как линейные функции остальных неизвестных, так называемых свободных неизвестных.
Фактически, выражая все переменные через свободные неизвестные, можно перейти к задаче линейного программирования, содержащей переменных и n линейных ограничений – неравенств, выражающих неотрицательность исходных n переменных.
Определение.
Допустимое решение, соответствующее нулевым значениям свободных неизвестных, называется базисным допустимым решением или опорным планом, при этом решение или план называются невырожденными, если несвободные переменные положительны и вырождены, если среди них есть хоть одно нулевое.
Замечания.
Если существует какое-либо допустимое решение для задачи линейного программирования, то существует и базисное допустимое решение. Если, кроме того целевая функция имеет нижнюю границу на множестве решений, то есть существует оптимальное решение, то существует и оптимальное базисное решение.
Множество всех допустимых решений данной задачи линейного программирования есть выпуклое множество в n-мерном пространстве решений. Это значит, что каждая точка прямолинейного отрезка, соединяющего два допустимых решения (x1, x2, …, xn)T и
(x'1, x'2, …, x'n)T : , — есть также допустимое решение.
Другими словами, множество допустимых решений есть выпуклый многоугольник или многогранник в плоскости или гиперплоскости, определяемой уравнениями (1.5) с граничными линиями, плоскостями или гиперплоскостями (1.6).
Пример.
Множество решений на плоскости (x1, x2) для задачи линейного программирования.
Найти x1,x2z=3x1+2x2 минимум, то есть z=3x1+2x2=min при условиях
(рис. 2.2).
Рисунок .. Геометрическое представление множества решений.
Транспортная задача.
В трех месторождениях добывается определенное количество угля. Имеются три пункта потребления угля. Известны расстояния между пунктами добычи и потребления и стоимость перевозок .
Необходимо так определить девять чисел , означающих количество грузов, перевозимых с пункта добычи на пункт потребления, чтобы суммарная стоимость перевозок была минимальна:
(.)
при условиях
, (.)
требующих, чтобы спрос bi удовлетворялся во всех пунктах, и при условиях
, (.)
требующих, чтобы из каждого пункта добычи вывозилось угля не больше количества ai, которое на нем производится.
Как правило, в таких задачах считается, что сумма добытого количества равна сумме потребляемого, то есть
, хотя это ограничение не принципиально.
Задача о рациональном питании.
При правильном питании калорийность пищевых продуктов должна полностью возмещать расход энергии человека, причём потребление отдельных растительных и животных жиров, белков, углеводов и витаминов не должно превышать определенную норму.
Предположим, что имеется n различных продуктов калорийностью , равной числу калорий в единице массы. В единице массы j-го продукта содержится a2j жиров, a3j белков и a4j углеводов. Обозначим через b1, b2, b3, b4 потребление организма в энергии, жирах, белках и углеводах соответственно. Тогда при правильном питании должны выполняться следующие соотношения:
, (.)
где xj 0 – количество потребления j-го продукта.
Если ввести требование экономного расходования средств, то это эквивалентно критерию
. (.)
Если поменять знаки у , то первое уравнение запишется в виде:
. (.)
После этого задача о рациональном питании приобретает стандартный вид задачи линейного программирования.
Задача об использовании ресурсов.
Предприятие имеет определенное количество ресурсов, рабочую силу, сырьё, оборудование и т.д. Для простоты будем считать, что число ресурсов равно трем, и каждого ресурса имеется b1, b2, b3 условных единиц.
Пусть предприятие выпускает два вида товаров. Для производства единицы каждого товара затрачивается aij ресурсов .
Известна стоимость cj единицы каждого товара. Требуется при данных ресурсах выпустить такую комбинацию товаров x1 и x2, чтобы доход предприятия был максимален. При линейной зависимости стоимости продукции от количества продукции задача записывается в виде:
при
, , (.)
и относится к классу задач линейного программирования. Если стоимость товаров не зависит линейно от их количества, то имеет место задача нелинейного программирования.
Задача о загрузке транспорта.
Пусть имеется транспортная единица грузоподъемностью b, которую необходимо загрузить различными предметами xj в разных количествах, причем cj -стоимость, wj -вес отдельного предмета j-го типа. Например, загружаются автомобили, тракторы, самолеты. Требуется определить оптимальную загрузку так, чтобы стоимость перевозимого груза была максимальной. Очевидно, что стоимость всего перевозимого груза задается формулой:
. (.)
Необходимо найти такие целые числа , при которых эта линейная форма приняла бы максимальное значение при условиях
. (.)
В отличие от предыдущих в этой задаче число ограничений i = 1. Эта задача существенно отличается от ранее рассмотренных тем, что в ней искомые значения величины xj — целочисленные. Поэтому она относиться к задачам целочисленного линейного программирования.
В решении задач линейного программирования часто пользуются геометрическими интерпретациями в разных вариантах.
Система неравенств (2.1.2) определяет в пространстве x1, x2, …, xn выпуклую область – выпуклый многогранник или многоугольник U. Для случая n = 2 имеем систему неравенств:
(.)
Каждое из этих соотношений определяет область, лежащую по одну сторону от прямой:
. (.)
Теорема.
Экстремальное значение целевой функции в задачах линейного программирования:
всегда является абсолютным;
достигается в крайней точке определения задачи.
Доказательство:
Допустим, что в многограннике U или на его границе есть точка x0 такая что (x0)(x) в некоторой окрестности N(x0). Предположим также, что в этом же многограннике есть точка типа x0, то есть точка , в которой целевая функция принимает лучшее значение, чем в точке x0. Если это не так, то x*=x0, то есть точка относительного экстремума является и точкой абсолютного экстремума. Итак, предположим противное, то есть существование некоторой точки .Соединим точки x0 и отрезком и рассмотрим значение целевой функции внутри отрезка в точке x (рис. ниже).
Рис. .. Отрезок, соединяющий точки х0 и , принадлежащие многограннику U.
Так как то
.
Очевидно, что при фиксированных значениях x0 и функция (x) является линейной функцией параметра :
.
Если сколь угодно близко x устремить к x0, то всегда будет (x)(x0), но это противоречит определению условного экстремума в точке x0. Следовательно, точка x0 является и точкой абсолютного экстремума.
Докажем теперь, что экстремум всегда достигается в крайней точке определения задачи.
Допустим, что x* не является крайней точкой в многограннике U, то есть можно найти точки x1 и x2 такие, что x* окажется на соединяющем их отрезке. Тогда очевидно, что
или
.
Если (x1)(x2), то тогда получаем противоречие с тем, что x* – абсолютный экстремум, а, следовательно, и (x*)(x1) и (x*)(x2). Противоречия не будет, если (x1)=(x2). Очевидно, что это справедливо, если x1 и x2 принадлежат гиперплоскости вида z=const=z*.
Очевидно, что z* не может быть внутренней точкой U. Значит эта гиперплоскость (прямая) может касаться U , и в этом случае она наверняка пройдет через крайнюю точку – точку типа x*.
Теорема доказана.
Линейная форма (2.1.1) в случае двух переменных принимает вид: (.)
Это есть уравнение прямой в плоскости (x1, x2), пересекающей оси x1 и x2 в точках и соответственно (рис.2.3.2).
Рис. .. Угол.
Величины c1 и c2 определяют наклон прямой, причём угол наклона к оси x1 задается формулой:
, так как ,
а
. (.)
L определяет расстояние от начала координат до прямой, которое определяется так:
(.)
Дадим теперь геометрическую интерпретацию задачи линейного программирования. Если требуется определить такие x1 и x2, которые придали бы линейной форме экстремальное значение, то геометрически это означает, что необходимо провести прямую L {см. (2.3.3)}, проходящую хотя бы через одну точку области и имеющую минимальное или максимальное расстояние d от начала координат (рис.2.3.3а).
Рис. .. Геометрическая интерпретация задачи линейного программирования для случаев минимума (а) и максимума (б).
В случае максимизации это расстояние должно быть минимальным для L< 0 (см. рис. 2.3.3а) и максимальным (см. рис. 2.3.3б) для L > 0.
Кроме этого, возможны два варианта: прямая имеет с допустимой областью одну общую точку в вершине области или совпадает с одним из ее ребер. Во втором варианте (рис. 2.3.4) имеет место вырожденный случай, то есть линейная функция цели совпадает с левой частью одного из ограничений.
Рис. .. Геометрическая интерпретация задачи линейного программирования для вырожденного случая.
Возможны также случаи, когда целевая функция не ограничена сверху (рис. 2.3.5) и система ограничений задачи несовместна (рис. 2.3.6).
Рис. .. Целевая функция f(x) не Рис. .. Несовместная система
ограничена сверху. ограничений.
Замечание.
Так как при построении некоторой поверхности уровня
,
где h – некоторая константа, при n = 2, эта поверхность представляет прямую c1x1+c2x2=h, то эта прямая в плоскости (x1, x2) пересекает оси ox1 и ox2 в точках соответственно (см. рис. 2.3.7).
Следовательно, для нахождения оптимального решения следует передвигать линию уровня, проходящую через многоугольник решений, в направлении вектора , перпендикулярного данной линии уровня, до тех пор, пока она не пройдет через последнюю ее общую точку с многоугольником решений. Координаты этой последней точки (невырожденный случай) или точек (вырожденный случай) и определяет оптимальный план данной задачи.
Рис. .. Поверхность уровня f(x)=c1x1+c2x2=h.
Обозначим CBA через , DOB через , OBA через γ .
.
Пусть K1 – угол наклона прямой c1x1+c2x2= h к оси ox1, а K2 – угол наклона вектора к оси ox1.
.
Из условия ортогональности прямой c1x1+c2x2 = h и вектора имеем
K1K2 = – 1, то есть
.
Следовательно, уравнение вектора , проходящего через точку (0,0)T, имеет вид:
, то есть .
Таким образом, в качестве направляющего вектора , следует брать вектор .
Таким образом, нахождение минимального значения функции отличается от поиска ее максимального значения при тех же ограничениях лишь направлением движения вдоль вектора , во втором случае он движется в противоположном направлении.
Задача линейного программирования для частного случая n=2 имеет вид:
найти x1, x2 , которые доставляют экстремум функции
, (.)
при
, (.)
. (.)
Поиск решения состоит из следующих шагов:
Построение прямых, уравнения которых соответствуют ограничениями (2.3.7) и (2.3.8) при замене в них знаков неравенств на знаки равенств.
Определение полуплоскостей, определяемых в каждом из ограничений задачи.
Нахождение многоугольника решений.
Построение вектора .
Построение прямой c1x1+ c2x2=h, проходящей через многоугольник решений.
Передвижение прямой c1x1+ c2x2=h в направлении вектора , результатом чего является либо нахождение точки, в которой целевая функция принимает экстремальное значение, либо установление факта неограниченности функции сверху (при нахождении максимального значения) или снизу (при нахождении минимального значения) на множестве планов.
Определение координат точки экстремума и вычисление значения целевой функции в этой точке.
Примеры.
1. Пусть для производства двух видов изделий A и B используется 3 вида сырья, причем необходимые данные сведены в следующую таблицу.
Таблица .
При этом изделия A и B могут производиться в любых соотношениях.
Требуется составить план выпуска, обеспечивающий максимальную прибыль.
Решение:
Предположим, что изготовлено x1 изделий вида A и x2 изделий вида B.
В силу условий задачи должны выполнятся условия:
(.)
Общая прибыль от реализации изделий составит
. (.)
Таким образом, имеем следующую математическую постановку задачи.
Среди всех неотрицательных решений системы линейных неравенств (2.3.9) найти такое, при котором функция F { см. (2.3.10)} принимает максимальное значение.
Для решения задачи воспользуемся геометрической интерпретацией. Заменим все неравенства системы ограничением на равенства. В результате
получаем уравнения прямых:
. (.))
Изобразим эти прямые на рисунке 2.3.8.
Каждая из построенных прямых делит плоскость на две полуплоскости, причём координаты одной полуплоскости удовлетворяют исходному неравенству, а другой – нет.
Чтобы определить истинную полуплоскость, берем какую-либо точку, принадлежащую одной из полуплоскостей и проверяем, удовлетворяет ли она данному неравенству. Если удовлетворяет, то это – искомая полуплоскость, иначе – другая полуплоскость. Например, для прямой I: 12x1+4x2=30 возьмём точку (0,0)T. Если подставим координаты этой точки в уравнение I, то получим 0<30, то есть координаты точки удовлетворяют исходному неравенству. Следовательно, полуплоскость, которой принадлежит точка (0,0)T является искомой.
Пересечение полученных полуплоскостей определяет многоугольник решений OABCDEK. Осталось найти точку, в которой F принимает максимальное значение. Для этого строим вектор и прямую 30x1+40x2 = h, где h – некоторая константа, причём такая, что прямая имеет общие точки с многоугольником решений.
Рис. .. Многоугольник решений – OABCDEK.
Пусть h=480. Строим прямую 30x1+40x2=480. Если взять какую-либо точку, принадлежащую прямой и многоугольнику решений, то её координаты определяют такой план производства, при котором прибыль от реализации равна 480.
Полагая далее h равным некоторому числу, большему чем 480, получаем различные параллельные прямые. Если они имеют общие точки с многоугольником решений, то эти точки определяют планы производства A и B, при котором прибыль превосходит 480.
Перемещая построенную прямую в направлении вектора убеждаемся, что последней общей точкой её с многоугольником решений является точка B, координаты которой и определяют оптимальный план выпуска изделий A и B.
Найдём координаты точки B, как точки пересечения прямых II и III:
Итак, координатами точки B является:
=12 ; =18 .
Следовательно, изготовив 12 единиц изделий вида A и 18 единиц изделий вида B, получаем максимальную прибыль
Fmax=3012+4018=1080.
2. Найти значение x1 и x2 , доставляющие экстремальные значения (минимум и максимум) функции при ограничениях:
. (*)
Заменим все неравенства в ограничениях равенствами, в результате получаем уравнения прямых:
.
Изобразим эти прямые на рисунке (см. рис. 2.3.9).
Рис. .. Многоугольник решений АВС.
Анализ показывает, что многоугольником решений задачи является треугольник ABC, а вектором –
Для нахождения экстремальных значений функции F=x1+x2 возьмем F=4, так как при этом значении прямая 4=x1+x2 имеет общую точку с многоугольником решений.
Передвигая данную прямую параллельно самой себе в направлении вектора находим, что её последней общей точкой с многоугольником решений является точка C. Следовательно, в этой точке функция принимает максимальное значение.
Так как точка C является пересечением I и III прямых, то ее координаты удовлетворяют системе из уравнений этих прямых:
Для нахождения минимального значения целевой функции F передвигаем прямую x1+ x2 = 4 в направлении, противоположном направлению вектора
Последней общей точкой прямой и многоугольника решений является точка A. Следовательно, минимальное значение функция F принимает в точке A, удовлетворяющей системе:
.
Итак, .
3. Найти максимальное значение функции
, при условиях
.
Решение:
Здесь ограничения заданы в виде равенств, число которых m=3, а число неизвестных равно 5. Поэтому, чтобы решить задачу геометрически на плоскости, её следует свести к задаче, в которой число неизвестных равно 2. Исключим переменные x3, x4 и x5 из целевой функции. Для этого воспользуемся уравнениями системы ограничений
и подставим x3, x4, x5 , выраженные через x1 и x2 , в целевую функцию.
В результате имеем:
.
Ограничения при этом имеют вид:
Построим многоугольник решений полученной задачи (рис.2.3.10).
Построим функцию (12 взято произвольно).
Строим вектор
Максимальное значение целевая функция принимает в точке C, то есть в точке пересечения I и II кривых
Найдем координаты точки C.
Рис. .. Многоугольник решений ABCD.
Вдоль каждой из граничных прямых, значение одной из переменных, исключенной при переходе к соответствующему неравенству равно 0. Поэтому в каждой из вершин полученного многоугольника решений по крайней мере две переменные исходной задачи принимает нулевые значения, так, например, в точке C x3= 0 и x4= 0.
Подставляя найденные значения и в III уравнение системы ограничений исходной задачи,то есть в уравнение , имеем:
.
Следовательно, оптимальным планом рассматриваемой задачи является план . Максимальное значение целевой функции равно
или, что то же самое, .
Задание.
Для предыдущей задачи найти минимальное значение целевой функции.
4. Найти максимальное значение функции
при условиях:
Решение:
Число неизвестных здесь равно 5. Поэтому, чтобы решить задачу геометрически на плоскости, ее следует свести к задаче, в которой число неизвестных равно 2. Для этого воспользуемся методом последовательного исключения неизвестных.
1. Из I и III уравнений
имеем:
. (.)
2. Из I и II уравнений
имеем:
. (*)
Из уравнения (2.3.12) имеем:
. (.)
Подстановка x2 из (2.3.13) в (*) даёт:
(.)
3. Из II и III уравнений
.
Сложив оба уравнения имеем:
. (.)
Подстановка x2 из (2.3.13) даёт:
(.)
Следовательно, имеем условие
. (.)
Переходим к условиям в виде неравенств, то есть убрав x1, x2, x5 из уравнений (2.3.17), получим условия, в которых есть только две переменные x3 и x4:
.
Обращаемся к целевой функции. Из уравнений (2.3.17) x1 и x5 имеют вид:
Подставим эти выражения в целевую функцию. В результате имеем:
Следовательно, исходная задача линейного программирования записывается так.
Найти максимальное значение при условиях
.
Таким образом, преобразованная система содержит две переменных. Следовательно, можно воспользоваться геометрическим методом: строить прямые, определить многоугольник решений и находить в нем крайние точки.
Задание.
В примере № 4 определить максимальное и минимальное значение целевой функции.
Симплекс-метод – это специальный метод оптимального (направленного) перебора, используемый при решении задач линейного программирования. Симплекс-метод обеспечивает сходимость к экстремальной точке за конечное число шагов, так как он предусматривает последовательный оптимальный просмотр вершин многогранника, число которых конечно, и является оптимальной процедурой отыскания экстремума.
Симплекс-метод заключается в последовательном переходе от одной вершины области допустимых значений к другой, соседней, в которой значение функции цели лучше, чем в исходной точке.
Известно, что если решение задачи линейного программирования существует, то оно достигается в одной из вершин многогранника решений.
Симплекс-метод позволяет найти крайнюю точку области многогранника решений и определить является ли эта точка точкой типа x*. Если найденная точка не является искомой, то метод обеспечивает переход в другую точку с уменьшением (увеличением) значения целевой функции . Через конечное число подобных точек точка x* либо находится, либо признаётся несуществующей.
Симплексный метод универсален, хотя и требует стандартную постановку задачи:
Табличный алгоритм симплекс метода
Для изготовления различных изделий , и система использует 3 различных вида сырья. Нормы расхода сырья на производство одного изделия приведены в следующей таблице.
Изделия , и могут производиться в любых соотношениях (сбыт обеспечен), накладываются ограничения по количеству сырья каждого вида.
Требуется составить такой план производства изделий, при котором общая стоимость всей произведённой предприятием продукции является максимальной. Составим математическую модель.
Обозначим искомый выпуск изделий через , B через , через .
Целевая функция имеет вид:
. (1)
В общем виде целевая функция принимает вид:
(1’)
Ограничения записываются так
. (2)
Или в общем виде, так
, (2’)
где . (3)
Запишем эту задачу в форме основной задачи линейного программирования (ОЗЛП). Для этого перейдём от ограничений неравенств к ограничением равенствам:
(4)
В общем виде ограничения виде равенств записываются так:
. (4’)
Преобразуем систему (4) к векторной форме.
. (5)
; ; ; ;
; ; .
Запишем опорный план (базисное решение).
Опорный план определяется системой трёхмерных единичных векторов ,,, которые образуют базис трёхмерного векторного пространства.
Составим симплексную таблицу для 1-ой итерации. Для этого по приведённым ниже формулам найдём следующие значения и запишем их в симплекс таблицу.
Сначала положим, что предприятие вообще не выпускает изделий, и поэтому целевая функция принимает нулевое значение, то есть
, где
— начальные значения коэффициентов в целевой функции.
Далее найдём начальные частичные суммы целевой функции .
Табл. 1.Симплекс таблица для первой итерации.
Как видно из табл. 1, значения всех основных переменных равны нулю, а дополнительные переменные принимают свои значения в соответствии с ограничениями задачи.
Эти значения переменных отвечают такому «плану», при котором ничего не производится, сырьё не используется и значение целевой функции равно нулю. (то есть стоимость произведённой продукции отсутствует). Естественно, такой план не является оптимальным.
Это видно из 4-йстроки табл. 1 так как в ней имеются три отрицательных числа Напомним, что условие оптимальности указывает на то, что в последней строке не должно быть отрицательных чисел. Эти отрицательные числа не только свидетельствуют о возможности увеличения общей стоимости производимой продукции, но и показывают, на сколько увеличится эта сумма при введении в план единицы того или другого вида продукции. Так число означает, что при включении в план производства одного изделия обеспечивается увеличение выпуска продукции на руб. Поэтому с экономической точек зрения наиболее целесообразным является включение в план производства изделий . Это же и необходимо сделать и на основании формального признака симплексного метода, поскольку максимальное по абсолютной величине отрицательное число стоит в 4-й строке столбца . Следовательно, в базис введём вектор .
Определяем вектор, подлежащий исключению из базиса. Для этого находим для , то есть . Найдя число , мы тем самым с экономической точки зрения определили, какое количество изделий предприятие может изготовлять с учётом норм расхода и имеющихся объёмов сырья каждого вида. Так как сырья данного вида соответственно имеется 360, 192 и 180 кг, а на одно изделие требуется затратить сырья каждого вида соответственно 12, 8 и 3 кг, то максимальное число изделий , которое может быть изготовлено предприятием, равно , то есть ограничивающим фактором для производства изделий является имеющийся объём сырья II вида. С учётом его наличия предприятие может изготовить 24 изделия . При этом сырьё II вида будет полностью использовано. Следовательно, вектор подлежит исключению из базиса. Столбец вектора и вторая 2-я являются направляющими. Составим таблицу для второй итерации.
Сначала заполним строку вектора, вновь введённого в базис, т.е. строку, номер которой совпадает с номером направляющей строки. Здесь направляющей строкой является вторая строка. Элементы этой строки получаются из соответствующих элементов табл. 1 делением их на разрешающий элемент (т.е. на 8).
Табл. 2.Симплекс таблица для второй итерации.
При этом в столбце записываем коэффициент стоящий в столбце вводимого в базис вектора . Затем заполняем элементы столбцов для векторов, входящих в новый базис. В этих столбцах на пересечении строк и столбцов одноименных векторов подставляем единицы, а все остальные элементы полагаем равными нулю.
Для определения остальных элементов табл. 2 применяем правило треугольника. Вычислим элементы табл. 2, стоящие в столбце вектора . Первый из них находится в 1-й строке этого столбца. Для его вычисления находим три числа:
Число, стоящее на месте этого элемента в предыдущей таблице. В нашем случае это число, стоящее в табл. 1 на пересечении столбца вектора и 1-й строки (360);
Число, стоящее в той же строке что и отыскиваемый элемент и в столбце вектора вводимого в базис из предыдущей симплекс таблицы. В нашем случае это число, стоящее в табл. 1 на пересечении столбца вектора и 1-й строки (12);
Число в строке введённого в базис вектора и в столбце отыскиваемого элемента в текущей симплекс таблице. В нашем случае это число, стоящее в табл. 2 на пересечении столбца вектора и 2-й строки (24).
Вычитая из первого числа произведение двух других, находим искомый элемент: ; записываем его в 1-й строке столбца вектора табл. 2. Аналогичным образом находим и все остальные элементы:
;
; ;
; ;
; .
По окончании расчёта всех элементов табл. 2 в ней получены новый опорный план и коэффициенты разложения векторов () через базисные векторы ,, и значения и . Как видно из этой таблицы, новым опорным планом задачи является план . При данном плане производства изготовлены 24 изделия и остаётся неиспользованным 72 кг сырья I вида и 108 кг сырья III вида. Стоимость всей производимой при этом плане продукции равна 384 руб. Указанные числа записаны в столбце вектора табл. 2. Как видно, данные этого столбца по-прежнему представляют собой параметры рассматриваемой задачи, хотя они значительные изменения. Изменились данные и других столбцов, а их экономическое содержание стало более сложным. Так, например, возьмём два столбца вектора . Число во 2-й строке этого столбца показывает, на сколько следует уменьшить изготовление изделий , если запланировать выпуск одного изделия . Числа 9 и в 1-й и 3-й строках вектора показывают соответственно, сколько потребуется сырья I и II вида при включении в план производства одного изделия , то это обеспечит увеличение выпуска продукции в выражении стоимости на 2 руб. Другими словами, если включить в план производства продукции одно изделие , то это потребует уменьшения выпуска изделия на ед. и потребует дополнительных затрат 9 кг сырья I вида и кг сырья III вида, а общая стоимость изготовляемой продукции в соответствии с новым оптимальным планом возрастёт на 2 руб. Таким образом, числа 9 и выступают как бы новыми «нормами» затрат сырья I и III вида на изготовление одного изделия (как видно из табл. 1, ранее они были равны 15 и 3), что объясняется уменьшением выпуска изделий .
Такой же экономический смысл имеют и данные столбца вектора табл. 2. Несколько иное экономическое содержание имеют, числа записанные в столбце вектора . Число во 2-й строке этого столбца, показывает, что увеличении объёмов сырья II вида на 1 кг позволило бы увеличить выпуск изделий на ед. Одновременно потребовалось бы дополнительно кг сырья I вида и кг сырья III вида. Увеличение выпуска изделий на ед. приведет к росту выпуска продукции на 2 руб.
Из изложенного выше экономического содержания данных табл. 2 следует, что найденный на II итерации план задачи не является оптимальным. Это видно и из 4-й строки табл. 2, поскольку в столбце вектора этой строки стоит отрицательное число . Значит, в базис следует ввести вектор , то есть в новом плане следует предусмотреть выпуск изделий . При определении возможного числа изготовления изделий следует учитывать имеющиеся количество сырья каждого вида, а именно: возможный выпуск изделий определяется для , то есть находим
.
Следовательно, исключению из базиса подлежит вектор , иными словами, выпуск изделий ограничен имеющимися в распоряжении предприятия сырьём I вида. С учётом имеющихся объёмов этого сырья предприятию следует изготовить 8 изделий . Число 9 является разрешающим элементом, а столбец вектора и 1-я строка табл. 2 являются направляющими.
Составляем таблицу для III итерации.
Табл. 3.Симплекс таблица для третей итерации.
В табл. 3 сначала заполняем элементы 1-й строки, которая представляет собой строку вновь вводимого в базис вектора . Элементы этой строки получаем из элементов 1-й строки табл. 2 делением последних на разрешающий элемент (то есть на 9). При этом в столбце данной строки записываем .
Затем заполняем элементы столбцов векторов базиса и по правилу треугольника вычисляем элементы остальных столбцов.
В результате в табл. 3 получаем новый опорный план и коэффициенты разложения векторов через базисные векторы , , и соответствующие значения и .
Проверяем является ли данный опорный план оптимальным или нет. Для этого рассмотрим 4-ю строку табл. 3. В этой строке среди чисел нет отрицательных. Это означает, что найденный опорный план является оптимальным и . Следовательно, план выпуска продукции, включающий изготовление 8 изделий и 20 изделий , является оптимальным. При данном плане выпуска изделий полностью используется сырьё I и II вида и остаётся неиспользованным 96 кг сырья III вида, а стоимость производимой продукции равна 400 руб.
Оптимальным планом производства продукции не предусматривается изготовление изделий . Введение в план выпуска продукции изделий вида привело бы к уменьшению указанной общей стоимости. Это видно из 4-й строки столбца где число 5 показывает, что при данном плане включение в него выпуска единицы изделия приводит лишь к уменьшению общей стоимости на 5 руб.
Пример реализации данного алгоритма в MATLAB.
function out = simplex(d)
% Программа реализующая симплекс метод.
% d - матрица данных в стандартной форме
% a11x1+a12x2+a13x3<=C1
% a21x1+a22x2+a23x3<=C2
% a31x1+a32x2+a33x3<=C3
%Найти max f(x)
% f(x)=z1x1+z2x2+z3x3
%d=[a11,a12,a13,c1;
% a21,a22,a23,c2;
% a31,a32,a33,c3;
% z1 ,z2 ,z3 ,0;]
clc;
d=[18,15,12,360;
6 , 4, 8,192;
5 , 3, 3,180;
9 ,10, 16, 0;]
%Преобразуем данные в симплес таблицу.
m=[0,0,0, d(4,1),d(4,2),d(4,3),0,0,0;
4,0,d(1,4),d(1,1),d(1,2),d(1,3),1,0,0;
5,0,d(2,4),d(2,1),d(2,2),d(2,3),0,1,0;
6,0,d(3,4),d(3,1),d(3,2),d(3,3),0,0,1;
0,0,0,(-1)*d(4,1),(-1)*d(4,2),(-1)*d(4,3),0,0,0;];
while m(1,1)==0
m
m=iter_simp(m);
end
m
function m_out = iter_simp(m)
mold=m;
%Поиск вектора (v), который будем вводить в базис.
%Это должен быть максимальный элемент
%по абсолютному значению, из
%отрицательных чисел последней строки.
max=0;
v=0;
for i=1:6
x=m(5,3+i);
if x<0
x=abs(x);
if x>max
max=x;
v=i;
end
end
end
%Определяем вектор подлежащий исключению из базиса (vi)
vi=2;
min=m(2,3)/m(2,3+v);
for i=2:4
x=m(i,3)/m(i,3+v);
if min>x
vi=i;
min=x;
end
end
%Разрешающий элемент
raz=m(vi,v+3);
%Сначала заполняем строку вектора вновь введённого в базис
for i=3:9
m(vi,i)=m(vi,i)/raz;
end
%Меняем вектор в первом столбце
m(vi,1)=v;
%Записываем цену
m(vi,2)=m(1,v+3);
%Вычисляем остальные числа
for i=2:5
if i~=vi
for j=3:9
x1=mold(i,j);
x2=mold(i,v+3);
x3=m(vi,j);
m(i,j)=x1-x2*x3;
end
end
end
%Критерий оптимальности
m(1,1)=1;
for i=4:9
if m(5,i)<0
m(1,1)=0;
end
end
m_out=m;
Недостатки симплекс метода.
Рассмотренный простейший симплекс-метод склонен к зацикливанию и медленно сходится, если длина ребра симплекса выбрана малой (выбор же большой длины ребра симплекса обеспечивает высокую скорость сходимости, но дает малую точность решения). Поэтому в вычислительной практике используются различные модификации простейшего метода, направленные на преодоление его указанных недостатков.
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования, состоящей, как мы уже знаем, в нахождении максимального значения функции
(д1)
при условиях
(д2)
(д3)
Определение
Задача, состоящая в нахождении минимального значения функции
(д4)
при условиях
(д5)
(д6)
называется двойственной по отношению к задаче (д1) – (д3). Задачи (д1) – (д3) и (д4) – (д6) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:
1. Целевая функция исходной задачи (д1) – (д3) задается на максимум, а целевая функция двойственной (д4) – (д6) – на минимум.
2. Матрица
(д7)
составленная из коэффициентов при неизвестных в системе ограничений (д2) исходной задачи (д1) – (д3), и аналогичная матрица
(д8)
в двойственной задаче (д4) – (д6) получаются друг из друга транспонированием (т. е. заменой строк столбцами, а столбцов – строками).
3. Число переменных в двойственной задаче (д4) – (д6) равно числу ограничений в системе (д2) исходной задачи (д1) – (д3), а число ограничений в системе (д5) двойственной задачи – числу переменных в исходной задаче.
4. Коэффициентами при неизвестных в целевой функции (д4) двойственной задачи (д4) – (д6) являются свободные члены в системе (д2) исходной задачи (д1) – (д3), а правыми частями в соотношениях системы (д5) двойственной задачи – коэффициенты при неизвестных в целевой функции (д1) исходной задачи.
5. Если переменная xj исходной задачи (д1) – (д3) может принимать только лишь положительные значения, то j–е условие в системе (д5) двойственной задачи (д4) – (д6) является неравенством вида “”. Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе (д2) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (д2) исходной задачи (д1) – (д3) и переменными двойственной задачи (д4) – (д6). Если i – соотношение в системе (д2) исходной задачи является неравенством, то i–я переменная двойственной задачи . В противном случае переменная уj может принимать как положительные, так и отрицательные значения.
Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (д2) прямой задачи и соотношения (д5) двойственной задачи являются неравенствами вида “”. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.
Пример
Составить двойственную задачу по отношению к задаче, состоящей в максимизации функции
(д9)
при условиях
(д10)
(д11)
Решение. Для данной задачи
и
Число переменных в двойственной задаче равно числу уравнений в системе (д10), т. е. равно трем. Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений (д10), т.е. числа 12, 24, 18.
Целевая функция исходной задачи (д9) – (д11) исследуется на максимум, а система условий (д10) содержит только уравнения. Поэтому в двойственной задаче целевая функция исследуется на минимум, а ее переменные могут принимать любые значения (в том числе и отрицательные). Так как все три переменные исходной задачи (д9) – (д11) принимают только лишь неотрицательные значения, то в системе условий двойственной задачи должны быть три неравенства вида “ ”. Следовательно, для задачи (д9) – (д11) двойственная задача такова: найти минимум функции при условиях
Пример
Для задачи, состоящей в максимизации функции
при условиях
сформулировать двойственную задачу.
Решение. Для данной задачи
,
В соответствии с общими правилами задача, двойственная по отношению к данной, формулируется следующим образом: найти минимум функции при условиях
Связь между решениями прямой и двойственной задач.
Рассмотрим пару двойственных задач, образованную основной задачей линейного программирования и двойственной к ней. Исходная задача: найти максимум функции
(д12)
при условиях
(д13)
(д14)
Двойственная задача: найти минимум функции
(д15)
при условиях
(д16)
Каждая из задач двойственной пары (д12) – (д14) и (д15), (д16) фактически является самостоятельной задачей линейного программирования и может быть решена независимо одна от другой. Однако при определении симплексным методом оптимального плана одной из задач тем самым находится решение и другой задачи.
Существующие зависимости между решениями прямой и двойственной задач характеризуются сформулированными ниже леммами и теоремами двойственности.
Лемма 1.
Если Х – некоторый план исходной задачи (д12) – (д14), a Y – произвольный план двойственной задачи (д15), (д16), то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y, т. е.
Лемма 2.
Если для некоторых планов X* и Y* задач (д12) – (д14) и (д15), (д16), то X* – оптимальный план исходной задачи, а Y* – оптимальный план двойственной задачи.
Теорема (первая теорема двойственности).
Если одна из задач двойственной пары (д12) – (д14) или (д15), (д16) имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, т. е.
Если же целевая функция одной задачи из двойственной пары неограничена (для исходной (д12) – (д14) – сверху, для двойственной (д15), (д16) –снизу), то другая задача вообще не имеет планов.
Теорема (вторая теорема двойственности).
План задачи (д12) – (д14) и план задачи (д15), (д16) являются оптимальными планами этих задач тогда и только тогда, когда для любого выполняется равенство
Геометрическая интерпретация двойственных задач.
Если число переменных в прямой и двойственной задачах, образующих данную пару, равно двум, то, используя геометрическую интерпретацию задачи линейного программирования, можно легко найти решение данной пары задач. При этом имеет место один из следующих трех взаимно исключающих друг друга случаев: 1) обе задачи имеют планы; 2) планы имеет только одна задача; 3) для каждой задачи двойственной пары множество планов пусто.
Пример.
Для задачи, состоящей в определении максимального значения функции при условиях
составить двойственную задачу и найти решение обеих задач.
Решение. Двойственной задачей по отношению к исходной является задача, состоящая в определении минимального значения функциипри условиях
Как в исходной, так и в двойственной задаче число неизвестных равно двум. Следовательно, их решение можно найти, используя геометрическую интерпретацию задачи линейного программирования (рис. 7 и 8).
Как видно из рис. 8, максимальное значение целевая функция исходной задачи принимает в точке В. Следовательно, Х*=(2, 6) является оптимальным планом, при котором . Минимальное значение целевая функция двойственной задачи принимает в точке Е (рис. 8). Значит, Y*=(1; 4) является оптимальным планом двойственной задачи, при котором Таким образом, значения целевых функций исходной и двойственной задач при их оптимальных планах равны между собой.
Рис. 7 рис. 8
Из рис 7. видно, что при всяком плане исходной задачи значение целевой функции не больше 46. Одновременно, как видно из рис. 8, значение целевой функции двойственной задачи при любом ее плане не меньше 46. Таким образом, при любом плане исходной задачи значение целевой функции не превосходит значения целевой функции двойственной задачи при ее произвольном плане.
Пример
Найти решение двойственной пары задач.
Исходная задача;
Двойственная задача:
Решение.
Как исходная, так и двойственная задача содержат по две переменные. Поэтому их решение находим, используя геометрическую интерпретацию задачи линейного программирования (рис. 7 и 8).
Из рис. 7 видно, что исходная задача не имеет оптимального плана из-за неограниченности снизу ее целевой функции на множестве допустимых решений.
Из рис. 10 следует, что двойственная задача не имеет планов, поскольку многоугольник решений ее пуст. Это означает, что если исходная задача двойственной пары не имеет оптимального плана из-за неограниченности на множестве допустимых решений ее целевой функции, то двойственная задача также не имеет планов.
Рис. 10.
Нахождение решения двойственных задач. Рассмотрим пару двойственных задач – основную задачу линейного программирования (д12) – (д14) и двойственную к ней задачу (д15), (д16).
Предположим, что с помощью симплексного метода найден оптимальный план X* задачи (д12) – (д14) и этот план определяется базисом, образованным векторами .
Обозначим через вектор-строку, составленную из коэффициентов при неизвестных в целевой функции (д12) задачи (д12) – (д14), а через – матрицу, обратную матрице Р, составленной из компонент векторов базиса. Тогда имеет место следующее утверждение.
Теорема.
Если основная задача линейного программирования имеет оптимальный план X*, то является оптимальным планом двойственной задачи.
Таким образом, если найти симплексным методом оптимальный план задачи (д12) – (д14), то, используя последнюю симплекс–таблицу, можно определить и и с помощью соотношения найти оптимальный план двойственной задачи (д15), (д16).
В том случае, когда среди векторов , составленных из коэффициентов при неизвестных в системе уравнений (д13), имеется т единичных, указанную матрицу образуют числа первых т строк последней симплекс–таблицы, стоящие в столбцах данных векторов. Тогда нет необходимости определять оптимальный план двойственной задачи умножением на , поскольку компоненты этого плана совпадают с соответствующими элементами (m+1)–й строки столбцов единичных векторов, если данный коэффициент , и равны сумме соответствующего элемента этой строки и если
Сказанное выше имеет место и для симметричной пары двойственных задач. При этом так как система ограничений исходной задачи содержит неравенства вида “ ”, то компоненты оптимального плана двойственной задачи совпадают с соответствующими числами (m+1)–й строки последней симплекс–таблицы решения исходной задачи. Указанные числа стоят в столбцах векторов, соответствующих дополнительным переменным.
Пример.
Для задачи, состоящей в определении максимального значения функции при условиях
составить двойственную задачу и найти ее решение.
Решение.
Двойственная задача по отношению к исходной состоит в нахождении минимума функции при условиях
Чтобы найти решение двойственной задачи, сначала находим решение исходной задачи методом искусственного базиса. Оно приведено в таблице 12.
Из последней симплекс-таблицы видно, что двойственная задача имеет решение
Оптимальные двойственные оценки удовлетворяют всем условиям двойственной задачи. При этом минимальное значение целевой функции двойственной задачи, равное совпадает с максимальным значением целевой функции исходной задачи.
Таблица 12
Экономическая интерпретация двойственных задач
Экономическую интерпретацию двойственных задач и двойственных оценок рассмотрим на примере.
Пример
Для производства трех видов изделий А, В и С используется три различных вида сырья. Каждый из видов сырья может быть использован в количестве, соответственно не большем 180, 210 и 244 кг. Нормы затрат каждого из видов сырья на единицу продукции данного вида и цена единицы продукции каждого вида приведены в таблице.
Определить план выпуска продукции, при котором обеспечивается ее максимальная стоимость, и оценить каждый из видов сырья, используемых для производства продукции. Оценки, приписываемые каждому из видов сырья, должны быть такими, чтобы оценка всего используемого сырья была минимальной, а суммарная оценка сырья, используемого на производство единицы продукции каждого вида,– не меньше цены единицы продукции данного вида.
Таблица
Решение.
Предположим, что производится x1 изделий А, изделий В и изделий С. Для определения оптимального плана производства нужно решить задачу, состоящую в максимизации целевой функции
(д17)
при следующих условиях
(д18)
(д19)
Припишем каждому из видов сырья, используемых для производства продукции, двойственную оценку, соответственно равную и у3.Тогда общая оценка сырья, используемого на производство продукции, составит
(д20)
Согласно условию, двойственные оценки должны быть такими, чтобы общая оценка сырья, используемого на производство единицы продукции каждого вида, была не меньше цены единицы продукции данного вида, т. е. и у3 должны удовлетворять следующей системе неравенств:
(д21)
(д22)
Как видно, задачи (д17) – (д19) и (д20) – (д22) образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий A, В и С, а решение двойственной – оптимальную систему оценок сырья, используемого для производства этих изделий. Чтобы найти решение этих задач, следует сначала отыскать решение какой–либо одной из них. Так как система ограничений задачи (д17) – (д19) содержит лишь неравенства вида “ ”, то лучше сначала найти решение этой задачи. Ее решение приведено в таблице 14.
Из этой таблицы видно, что оптимальным планом производства изделий является такой, при котором изготовляется 82 изделия В и 16 изделийС. При данном плане производства остается неиспользованным 80 кг сырья II вида, а общая стоимость изделий равна 1340 руб. Из таблицы 14 также видно, что оптимальным решением двойственной задачи является
Таблица
Переменные и обозначают условные двойственные оценки единицы сырья, соответственно I и III видов. Эти оценки отличны от нуля, а сырье 1 и III видов полностью используется при оптимальном плане производства продукции. Двойственная оценка единицы сырья II вида равна нулю. Этот вид сырья не полностью используется при оптимальном плане производства продукции.
Таким образом, положительную двойственную оценку имеют лишь те виды сырья, которые полностью используются при оптимальном плане производства изделий. Поэтому двойственные оценки определяют дефицитность используемого предприятием сырья. Более того, величина данной двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества сырья соответствующего вида на 1 кг. Так, увеличение количества сырья I вида на 1 кг приведет к тому, что появится возможность найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 5,75 руб. и станет равной 1340+5,75=1345,75 руб. При этом числа, стоящие в столбце вектора таблицы 14, показывают, что указанное увеличение общей стоимости изготовляемой продукции может быть достигнуто за счет увеличения выпуска изделий В на 5/8 ед. и сокращения выпуска изделий Сна 1/4 ед. Вследствие этого использование сырья II вида уменьшится на 1/8 кг. Точно так же увеличение на 1 кг сырья III вида позволит найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 1,25 руб. и составит 1340+1,25=1341,25 руб. Это будет достигнуто в результате увеличения выпуска изделий С на 1/4 ед. и уменьшения изготовления изделий В на 1/8 ед., причем объем используемого сырья II вида возрастет на 5/8 кг.
Продолжим рассмотрение оптимальных двойственных оценок. Вычисляя минимальное значение целевой функции двойственной задачи
видим, что оно совпадает с максимальным значением целевой функции исходной задачи.
При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получаем
Первое ограничение двойственной задачи выполняется как строгое неравенство. Это означает, что двойственная оценка сырья, используемого на производство одного изделия вида А, выше цены этого изделия и, следовательно, выпускать изделия вида А невыгодно. Его производство и не предусмотрено оптимальным планом прямой задачи. Второе и третье ограничения двойственной задачи выполняются как строгие равенства. Это означает, что двойственные оценки сырья, используемого для производства единицы соответственно изделий В и С, равны в точности их ценам. Поэтому выпускать эти два вида продукции по двойственным оценкам экономически целесообразно. Их производство и предусмотрено оптимальным планом прямой задачи.
Таким образом, двойственные оценки тесным образом связаны с оптимальным планом прямой задачи. Всякое изменение исходных данных прямой задачи может оказать влияние как на ее оптимальный план, так и на систему оптимальных двойственных оценок. Поэтому, чтобы проводить экономический анализ с использованием двойственных оценок, нужно знать их интервал устойчивости.
Требуется найти min f(x), на всём X = R n, то есть минимизация на всем пространстве.
Определение
Минимизация функции на множестве, заданном неравенствами, равенствами и другими ограничениями называется условной.
Пусть:
X = Rn (евклидово n-мерное пространство);
Функция f дифференцируема хотя бы один раз, тогда в точке минимума выполняется равенство:
f(x)=0, где (вектор частных производных по каждому аргументу)
В большинстве случаев это приводит к решению системы нелинейных уравнений, что само по себе проблема. Существуют релаксационные методы, в основе которых лежит построение последовательности {xi}, xiX со следующими свойствами:
f(x0)>f(x1)>...;
xix* = argmin{ f(x), xX}.
Рассмотрим методы нахождения локального минимума (т.е. корня уравнения f(x) =0). Все рассматриваемые методы делятся на несколько групп в зависимости от того, какой максимальный порядок производной функции f используется для вычисления последовательности. Порядок метода равен порядку старшей производной f, вычисляемый пр реализации этого метода. Если производные не используются, то методы нулевого порядка, затем - первого и так далее.
Общая схема безусловной оптимизации
Основная итерационная формула:
xk+1 = xk+ tkSk , где Sk - вектор, определяющий направление изменения xk
tk - скаляр, определяющий длину шага.
Sk может зависеть от xk: Sk = (xk), а может от (xk ,xk-1), от (xk ,xk-1, xk-2) и т.д.. В зависимости от этого критерия методы делятся на:
Одношаговые и двухшаговые методы имеют основное распространение.
Для вычисления t и S используются значение функции и первая производная.
Известно, что градиент функции в точке дает направление наибольшего возрастания функции в точке. Направление наибольшего убывания - это направление антиградиента.
Пусть Sk = -f(xk), tk > 0 - длина шага.
Пусть tk = t (т.е. не зависит от к)
xk+1 = xk - tf(xk)
Видно, что останавливаемся в любой точке, где f(xk)=0.
Пример:
f(x) = ax2, a>0, x-скаляр
xk+1=xk - 2taxk = (1- 2at)xk
Отсюда
1-2at<1 at<1- необходимое и достаточное условие существования предела
Если 0<tk<1/a - сходится,
tk>1/a - расходится,
tk=1/a - зацикливается.( tk=1/a x1=x0-2x0= -x0 x2=x1-2x1= -x1=x0 и т.д.)
Выбор постоянного шага приводит к осложнениям, так как a заранее часто не известно, а при малом значении a – много шагов; при большом – есть риск потери сходимости.
Оценим сходимость этого метода в общем случае.
Теорема (о сходимости метода градиентов)
Пусть f(x)- дифференцируема на Rn, f(x) удовлетворяет условию Липшица:
L>0, x, y верно || f(x)-f(y) || L ||x-y || (*)
(||x2|| = xi2 ), f(x)- ограничена снизу: f* такая, что f(x) f* >- (**)
и 0< t< 2/L (***)
Тогда при xk+1= xk - tf(xk), справедливо:
Замечание:
Сходимость градиента к нулю не гарантирует сходимости к минимуму.
Пример:
, градиент сходится к нулю, но функция не имеет локальных минимумов.
Равенство градиента нулю - необходимое условие минимума; если к нему добавить положительность второй производной, то будет достаточное условие локального минимума.
Таким образом доказана сходимость метод при определенных условиях. Оценить скорость сходимости в общем случае можно для более узкого класса функции
Общая схема методов: xk+1 = xk - *f ( x k )
Как известно выбор постоянного шага может привести к осложнениям.
Схема градиентного метода имеет вид xk+1 = xk - tk*f ( x k ). Если шаг выбрать с условием, что f(xk+1) - f(xk) -* tk * || f(xk)|| (*), где 0 < 1, то результат будет значительно лучше.
Иллюстрация:
Необходимо двигаться к х*. В начальной точке проводим касательную к линии уровня и делаем по перпендикуляру к касательной в этой точке, шаг соответствующей величины. Если оказываемся «далеко», то делим шаг пополам, проводим линию уровня, касательную и шагаем по перпендикуляру и т.д.
Алгоритм:
1.Выбираем t=const.
2.Проверяем выполнение соотношения (*).
3.Если выполняется, то вычисляем следующую точку; если не выполняется, тогда длину шага t делим на 2, проверяем (*) è так äалее.
Там, где f ( x ) = 0- останавливаемся.
Теорема (о градиентном метоле с дроблением шага)
Градиентный метод с дроблением шага обеспечивает следующее неравенство: || xk –x*|| const.*qk, где 0<q<1.
Без доказательства.
Определяет оптимальное значение шага на каждом такте.
Значение функции, полученное этим методом, меньше чем в предыдущем методе.
Характерная черта метода: градиенты функции в соседних точках ортогональны.
Доказать самостоятельно.
Графическая интерпретация:
В начальной точке проводим касательную к линии уровня и делаем шаг оптимальной величины в направлении перпендикуляра к касательной в данной точке. Получив новую точку, повторяем действия и так далее.
Теорема (о скорости сходимости метода наискорейшего спуска)
Скорость сходимости метода наискорейшего спуска - геометрическая.
, где (L,l -указаны ранее)
Без доказательства
Пусть f(x) имеет вид:, где ai>0 сильно различаются между собой. Поверхности уровней функции вытянуты вдоль тех осей xi, которым соответствуют малые ai.
Для более эффективного применения градиентных методов необходимо превращение поверхностей уровня в круги
Заменой переменных можно добиться того, чтобы в новых переменных yi поверхности уровней стали сферами. Для этого достаточно принять (тогда все коэффициенты квадратичной формы- единицы).
В случае, когда f(x) не квадратичная, а достаточно гладкая функция общего вида выбирают:
Это диагональные элементы матрицы вторых производных. Это преобразование не превратит поверхности уровня в сферы, но в некоторых случаях позволит уменьшить их вытянутость. Гарантировано исправить вид функции f(x) можно, если учесть все, а не только диагональные элементы матрицы вторых производных и преобразования координат вида:
Разложим f(x) в ряд Тейлора до 2-го слагаемого включительно:
(*)
- вектор
- матрица Гессе, матрица вторых производных.
Будем рассматривать квадратичную аппроксимацию f(x), тогда получим (*) без то есть предполагаем, что f(x) квадратичная форма. Эта форма имеет единственную точку min, который является корнем уравнения f ’(x)=0.
В данном случае:
Метод Ньютона
Пример:
Сделаем одну итерацию метода Ньютона для квадратичной функции
Этот пример показывает связь решения системы уравнений Ax-b = 0 и поиска минимума соответствующей функции f(x).
= A - матрица вторых производных.
Одна итерация метода Ньютона:
Но это точка минимума квадратичной функции. Таким образом для квадратичной функции метод Ньютона сходится за один шаг (матрица А должна быть положительно определена и симметрична, значения собственных чисел (растянутость) не играют роли).
Точка х1 гораздо ближе к х* , чем в градиентных методах, но надо вычислить матрицу Гессе и обратить ее. Градиентный метод медленнее, но без дополнительных вычислений.
Оценим скорость сходимости метода Ньютона:
Теорема (о скорости сходимости метода Ньютона):
Пусть f(x) дважды дифференцируема, матрица удовлетворяет условию
Липшица с константой L :
f(x) сильно выпукла: 0 l I 2 f(x) и начальное приближение удовлетворяет условию:
(есть требования к начальным условиям)
Тогда метод Ньютона сходится к х* с квадратичной скоростью
Доказательство:
Известно, что:
1)
Если на g’(x) удовлетворяет условию Липшица , то
Применим это отношение к 2 f(x), тогда
Пусть x = xk и
Дано (см. условие) тогда:
Таким образом .
Пусть q1= (обозначим). Выразим полученное неравенство через f(x0)
.........................................................................
Для сильно выпуклых функций известно
Тогда
Теорема доказана.
Если начальные условия не удовлетворяют требованиям теоремы, то метод может не сходиться.
Понятие о скорости сходимости
Пусть метод обеспечивает выполнение следующего неравенства
, где d- наибольшее из чисел, для которых выполняется это условие, тогда d- скорость сходимости метода.
Если обозначить k = , тогда скорость сходимости
d = , при k0 (k ).
Пусть k+1q k, 0 q 1. Для этого случая d =1- геометрическая скорость. Для метода Ньютона k+1= const k2 d =2 - поэтому скорость называется квадратичной.
Сравнительная таблица достоинств и недостатков градиентного метода и метода Ньютона:
Полезен метод Ньютона в случае квадратичной функции (сходится за один шаг).
Число обусловленности локального min.
Пусть - поверхности уровней f(x).
Рассмотрим следующую величину
Очевидно, что у окружности r=1, а у эллипса r>1 (увеличивается с увеличением растянутости).
Определение:
Числом обусловленности точки локального min называется . Это число дает основание для выбора метода.
Определение:
Говорят, что точка локального min плохо обусловлена, если число обусловленности велико, и хорошо обусловлена, если оно близко к 1.
Пример.
Пусть f(x) = 1/2 (Ax, x). А - диагональная матрица. Тогда число обусловленности есть отношение max диагонального элемента к min диагональному элементу.
Порядок применения методов.
На первом этапе применяются методы первого порядка, так как они обеспечивают глобальную сходимость (градиентные методы).
На втором этапе ( мало) - методы второго порядка (Ньютона).
Перечисленные методы являются классическими, они редко применяются в чистом виде, но служат базой для других методов. Смысл модификации метода в том, чтобы использовать достоинства обоих методов, обходя недостатки.
Также известен метод Марквардта-Левенберга
Если - градиентные методы
0- метод Ньютона.
Общий вид метода тяжелого шарика:
xk+1= xk - f(xk)+(xk-xk-1)
Это разностное уравнение, полученное из дифференциального уравнения, которое описывает движение шарика, катящегося по некоторой поверхности с постоянным трением. Введение инерции (xk-xk-1) увеличивает скорость сходимости.
Теорема(о скорости сходимости метода тяжелого шарика):
Ïóñòü 0 l I 2f(x) L I (ñèëüíàÿ âûïóêëîñòü)
0 1, 0 2(1+)/L,
тогда существует с=const такая, что || xk - x* || cqk ,
Без доказательства
Таким образом, метод сходится не быстрее геометрической прогрессии, как и градиентный метод; показатель геометрической прогрессии тот же, только с корнями, т.е. применение двухшагового метода при плохой обусловленности позволяет уменьшить эту обусловленность.
Модификация двухшагового метода- метод сопряженных градиентов.
xk+1 = xk - k f(xk) + k (xk-xk-1)
Отличается тем, что î k è k зависят от шага и выбираются следующим образом:
(k , k) = argmin f(xk - f(xk)+(xk-xk-1))
{,}
Для квадратичной функции
Но в Rn не может существовать более n ортогональных ненулевых векторов, поэтому для некоторого k n будет f(xk)=0, то есть точка xk- точка минимума.
Определение:
Векторы pi , связанные соотношением (Api, pj ) =0, называются сопряженными или А-ортогональными.
В методе сопряженных градиентов xk является точкой минимума квадратичной функции f(x) на подпространстве, порожденном первыми k градиентами. Следовательно, никакой метод, использующий только градиенты функции (точнее, в котором шаг делается по линейной комбинации предыдущих градиентов), не может сходиться быстрее, то есть метод сопряжённых градиентов является оптимальным по скорости сходимости в классе методов первого порядка.
xk+1= xk+ kpk , где k = argmin f(xk+ pk ), >0
pk= -f(xk)+kpk-1
0 = 0
Для квадратичной функции последовательность точек xi, определённая этими формулами, совпадает с последовательностью, полученной методом сопряжённых градиентов.
Эту модификацию удобнее применять для произвольных (неквадратичных) функций.
Рекомендуется применять процедуру обновления, т.е. через каждые n-шагов происходит сдвиг в направлении антиградиента.
То есть 0 = 0, затем n=0,..., mn=0, следовательно, pk= -f(xk)+0*pk-1= -f(xk)
(сдвиг в направлении антиградиента).
По скорости сходимости n шагов методы сопряженного градиента эквивалентны одному шагу метода Ньютона (для квадратичной функции метод сходится за один шаг).
Общая структура: xk+1 = xk - kkf(xk)
Достоинство:
Не надо вычислять обратную матрицу вторых производных.
Обозначим pk = -Hkf(xk)
yk= f(xk+1) -f(xk),
, A>0
Тогда для квадратичной функции имеем
yk = A(xk+1-xk) = kApk
k pk = ykA-1,
поэтому матрицу Hk+1 (необязательно для квадратичной функции) выбирают так, чтобы выполнялось так называемое квазиньютоновское условие:
Hk+1yk= kpk (Hk - должна стремиться к (2f(xk))-1
Проверим выполнение квазиньютоновского условия:
Для квадратичной функции метод сходится за n шагов, ãäå n – размерность пространства состояний. Скорость сходимости этого метода сверхлинейная (быстрее любой геометрической прогрессии). Сходимость глобальная. Объединяет достоинства градиентных методов и метода Ньютона.
Процедура применения:
На очередном шаге, имея Hk, делаем шаг в направлении pk. Получаем k (например, по методу наискорейшего спуска), получаем xk+1 , вычисляем yk и пересчитываем Hk+1 для следующего шага.
Недостаток: (по сравнению с методом сопряженных градиентов). Надо хранить и пересчитывать Hk размерности mn.
Метод Бройдена-Флетчера –Шенно.
где
Примечание:
Последовательности xk, генерируемые каждым вариантом, для квадратичной функции совпадают. Существует много других модификаций приведенных квазиньютоновских методов.
В их основе лежит аппроксимация градиента и матрицы вторых производных с помощью конечных разностей.
Пусть ej - орт j-й оси.
f (x + ej) f(x) + (f/x)j + O(2)
f/xj ( f(x + ej) - f(x) )/ ( f(x + ej) - f(x - ej) )/ (2)
Здесь под градиентом понимается конечная разность. Если слишком мала, то слишком велики погрешности при вычислении производных. Если велика, то из-за O(2) погрешности тоже велики. Таким образом, проблема этих методов - выбор .
Метод покоординатного спуска
Нужны направления. Раньше их задавал градиент, теперь его нет. Возможен случайный выбор, а можно по координатным осям.
Алгоритм:
Достоинство:
Требуется min функции вдоль только одной прямой.
Метод симплексов (Нелдера-Мида)
Алгоритм:
1.Фиксируем xo…xn ( n+1- точка)
Если n =2 , то выбираем равнобедренный треугольник.
2.
т.е. вычисляем отражённую точку.
Если f(xj’) < f(xj), то xj := xj’; k:=0, иначе k:=k+1
где k- количество идущих подряд неудачных отражений
3. Если k<n, то (если j<n, то j:=j+1 , иначе j:=0) goto 2.
4.Иначе сжатие: xl = argmin f(xj), 0 j n - ищем вершину, в которой функция минимальна (то есть наименьшее значение из всех существующих вершин.
5. Cжатие: xj = xl + ( xj - xl), j (сжатие в раз).
6. Если ||x0 – x1||, то j:=0, goto 2.
7. Печать xl.
Особенность: метод в ряде случаев позволяет найти глобальный минимум, т.е. позволяет перескакивать через хребты.
Существует много модификации метода.
Метод Пауэлла (сопряженных направлений)
Идея: Для двух точек x0,x1 делается шаг в произвольном направлении p0. Получаем точки x2,x3. Следующий шаг делаем в направлении p1. Находится x*.
Утверждается, что (Ap1,po)=0.
Поэтому для квадратичной функции метод сойдется за n-шагов. Это один из лучших методов прямого поиска.
Схема метода: xk+1 = xk + tkSk , где Sk -направление.
Необходимо определить tk.. Для этого надо найти минимум функции одной переменной (t) = f(xk + tSk). Будем искать точку локального минимума, поэтому ограничимся унимодальными функциями, т.е. имеющими один минимум. Больше ничего о функции неизвестно. Только можно вычислить (измерить) значения функции в точках.
Пусть функция задана на прямой, даны при этом точки a<b<c, и , точка минимума в [a, c]
Через эти точки проведем параболу:
Положим:
, т.е. имеем 3 уравнения и 3 неизвестных g0, g1, g2.
Находим g0, g1, g2
Рассмотрим два случая:
Так поступаем до тех пор, пока точка не окажется в достаточно малой окрестности одной из трех точек a, b, c. После чего такую точку считаем точкой минимума.
Метод можно обобщить на случай кубических и т.д. функций, но потребуется вычислять большее количество точек.
Если мы вычислим значения f в двух точках x1,x2 , то станет возможным исключение из рассмотрения некоторого множества точек, на котором гарантировано нет минимума, то есть имея измерения в двух точках можем сократить интервал поиска.
Как лучше выбирать точки, чтобы процесс быстрее сходился?
В методе дихотомии предлагается (отрезок [0,1] ).
Остается один из интервалов:. Выберем 3-й и 4-й эксперимент на -пару в середине оставшегося интервала. После n (n-четно) экспериментов min функции лежит в интервале .
Здесь каждый раз два эксперимента, но можно один, а в качестве другого брать один из предыдущих.
Интервал [a,b], вычислить функцию в точках .
На интервале [a,b] расположен минимум функции.
, где F1 и F2 некоторые числа 0<F1<1, 0<F2<1.
Анализируем перегибы функции внутри интервала, и также, как раньше, заменяем отрезок [a, b] на или . Идея метода в том, чтобы после замены, необходимо было вычислить только одну точку при гарантированном уменьшении длины отрезка, т.е.
, так как
(после замены отрезок уменьшится в 1/ F2 =
В новом отрезке должно быть(по правилу «золотого» сечения): так как
Тогда так как , , то.
Таким образом, уменьшение интервала в 1/ F2 = раз достигается с помощью вычисления функции в одной новой точке (см. процедуру выполнения). После n экспериментов имеем интервал неопределенности:
.
В пересчете на одно измерение этот метод лучше дихотомии.
Процедура выполнения:
Рассмотрим [a, b], вычислить функцию в точках .
В выражениях 1) и 2) появилась только одна новая точка. И так далее, пока длина отрезка [a, b] не станет меньше заданной величины.
Пусть у нас существует ограничение на количество вычисляемых точек N. Как выбирать средние точки , чтобы максимально уменьшить интервал, внутри которого лежит точка min?
, к- номер итерации.
Fj - числа Фибоначчи, обладающие свойством.
Fk+2 = Fk+1+ Fk
Два первых: 1;1
Как метод Фибоначчи связан с методом «золотого» сечения?
.
То есть асимптотически один метод переходит в другой. Окончательный интервал в методе «золотого» сечения всего на 17% больше чем в методе Фибоначчи. Если количество измерений не задано, то используется метод «золотого» сечения, если задано - то Фибоначчи.
Допустимое множество состоит из конечного числа элементов, поэтому решение задачи всегда можно найти за конечное число шагов, но в ряде случаев количество вариантов слишком велико, чтобы можно было организовать их полный перебор, и приходится искать методы целенаправленного перебора.
Пусть - все множество возможных вариантов. На этом множестве задан функционал качества f(x). Надо найти f(x)
Пусть мы можем оценить этот минимум на через параметр :
f(x)
Делим множество на два множества. Для каждого из этих множеств выписываем оценку:
f(x); ,
Будем постепенно получать дерево: ( -граница)
Способ получения этого дерева описывается ниже:
Выберем минимальный среди .
Пусть минимальный .
Делим на два множества, вычисляем оценки и т.д.
Пусть где-то получили множество ...= { } с оценкой ... (которая меньше всех других)
Тогда - оптимальный вариант.
Если оценка не минимальная, то находим тот лист дерева, у которого оценка минимальная и соответственно I вновь разбиваем на два множества и т.д.
Метод ветвей и границ (МВГ) дает экономию по сравнению с перебором всех вариантов.
Рассмотрим пример
Есть n городов. Надо объехать все города с минимальной стоимостью (расстоянием) и вернутся в исходный город. При этом каждый город посещается один раз (т.е. имеется Гамильтонов цикл, но с минимальной стоимостью).
Матрица стоимостей путей
A =
-стоимость пути от i до j.
м.б. , 0 , i, j
Допустимый маршрут содержит по одному элементу в каждой строке и столбце. Обратное неверно, так как возможны подциклы
Количество возможных вариантов n!.
Составим математическую модель:
Обозначим , причем
1 - если дуга входит в маршрут
0 - если дуга не входит в маршрут.
? , причем
= 1, j = , {0,1}
* в каждом столбце содержится один элемент
= 1, i =
* в каждой строке содержится один элемент
Эти ограничения разрешают циклы, поэтому эти условия являются необходимыми, но не достаточными.
Требование непрерывности маршрута обеспечиваются введением дополнительных N ограничений, где N = , каждое ограничение имеет вид:
n
i =, j =
Таким образом, матрица сильно разрежена, симплекс-метод применять не выгодно.
Используем МВГ.
Предположим, что мы выбирали некоторый путь S, его длина =, причем каждый из индексов используется один и только один раз.
Так как в путь S входит только один элемент из каждой строки и столбца, то можно проделать операцию нормализации матрицы A. Выберем произвольную строку i .
- наименьший элемент i -й строки и построим матрицу с элементами
= (изменена каждая строка)
Матрица определяет новую задачу коммивояжера, которая в качестве оптимальной будет иметь ту же последовательность городов.
=+
В каждой строке будет теперь, по крайней мере, один нулевой элемент.
Обозначим - минимальный элемент j-го столбца .
Построим матрицу с элементами =
Оптимальный путь тот же, а длина =+, где =+
Обозначим - решение задачи коммивояжера (ЗК).
=
Тогда величина - простейшая нижняя оценка решения :
(*)
это для МВГ.
Рассмотрим ЗК с матрицей .
Рассмотрим путь S, содержащий переход i j.
Тогда нижняя оценка пути:
+
Следовательно, для тех переходов, у которых = 0 будем иметь снова оценку (*). Естественно ожидать, что кратчайший путь содержит один из таких переходов.
Рассмотрим один из переходов i j, для которого = 0.
Обозначим (ij) -множество всех тех путей, которые не содержат переход i j.
Так как из города i надо куда-то идти, то множество (ij) содержит один из переходов i k, k j.
Так как в город j надо прийти, то множество (ij)содержит переход m j, где m i.
Следовательно, некоторый путь из множества (ij), содержащего переходы
i k , m j, будет иметь следующую нижнюю оценку:
++
Обозначим:
= +
Для любого из множества путей (ij) мы будем иметь оценку:
+ (**)
Мы хотим исключить некоторое множество вариантов (ij).Поэтому надо выбрать такой переход i j, для которого оценка (**) была бы максимальной.
=(+)
Таким образом, все множество возможных вариантов мы разбили на два множества: ,.
Для путей из множества - оценка (*).
Для путей их множества - оценка +.
Для матрица будет отличаться от матрицы тем, что
(переход i j запрещен , кот. выбран).
Рассмотрим множество и матрицу .
Так как все пути, принадлежащие этому множеству, содержат переход i j, то для его исследования достаточно рассмотреть ЗК, в которой города i и j совпадают
(из вычеркивается i -ая строка и j -й столбец).
Размерность этой задачи n - 1.
Так как переход j i невозможен, то элементы матрицы : .
Точнее, так как элемента может не быть, маршрут, определяемый дугой
( i, j ) содержит сколько-то (может быть ни одного) из ранее выбранных ребер помимо ребра ( i, j ).
Ребро ( i, j ) будет или изолировано от этих других ребер, или будет частью пути, включающего некоторые или все эти ребра.
Пусть p и q - начальный и конечный города этого пути. Возможно, что p=i или q=j. Положим .
Эта мера предохраняет от выбора ребра (q , p) в качестве последующего, а тем самым предохраняет от формирования замкнутого цикла длины < n.
В общем случае, среди всех полученных множеств вариантов выбираем то, для которого оценка минимальна.
Пример:
A : :
: 27+8=35
- определяем "веса" нулей (минимум по строке + минимум по столбцу)
- выбираем ноль с максимальным "весом",
- выбираем соответствующий путь и вычеркиваем столбец и строку.
Выбираем путь 32.
:
, 23 - запрещен (т.к. выбран 32)
:
оценка 35 + 4 =39
Выбираем путь 13; пути 31 нет
: 32 - запрещенный путь ( выб. в A1)
оценка 35 + 38 + 20 =93
: 13
оценка 39 + 37 =76
132 ; запрещенный путь: 21
:
оценка 39 + 35 =74
Путь 132 был . По : 241
Оптимальный путь: 13241
Вес: 74 = 24 + 4 + 45 + 1 (см. A)
строилось дерево:
Упражнение: Написать программу решения задачи о ранце с помощью метода ветвей и границ.
Модельная задача: поиск кратчайшего пути на графе.
Рис.1
На дугах проставлены расстояния между двумя вершинами. В вершинах - кратчайшее расстояние до конечной вершины .
Кратчайший путь имеет длину 5.
Этот граф без циклов.
Таким образом, можно разметить любой граф без циклов.
Двигаемся от конечной вершины к начальной:
любая вершина - состояние процесса,
дуги - переходы.
Таким образом, задача: на множестве всех траекторий выбрать ту, длина которой минимальна.
Абстрактная схема.
Пусть - конечное множества состояний и конечное множество управлений U. На некотором подмножестве U задана функция перехода : . Пусть есть последовательность состояний {,,...,} и последовательность управлений {,,...,}, для которых () =.
Определение Совокупность состояний и управлений называется траекторией процесса.
( множество состояний )
Введем множество траекторий Т, соединяющих начальные и конечные вершины.
Пусть на Т задан функционал:
(*)
Требуется найти траекторию с минимальным значением функционала:
J (t) ?
Заметим, что (*) можно представить в виде:
J (,...,) =
Функционал такого вида называется аддитивным. Следует подчеркнуть, что динамическое программирование применимо, если функционал аддитивный.
Метод динамического программирования позволяет свести минимизацию функции n переменных к n одномерным минимизациям.
Практические работы выполняются с использованием персональных компьютеров. Указания по технике безопасности совпадают с требованиями, предъявляемыми к пользователю ЭВМ. Другие опасные факторы отсутствуют.
Написание, отладка и проверка работоспособности синтаксического анализатора на основе графа детерминированного конечного автомата, соответствующего заданному регулярному выражению, порождающему конкретный язык.
8.2. Формулировка задания.
Для заданного варианта регулярного выражения написать регулярную грамматику.
Представить детерминированный конечный автомат, соответствующий регулярной грамматике.
Написать и проверить работоспособность соответствующего синтаксического анализатора.
Краткие сведения из теории
Конечный автомат — это устройство для распознавания строк какого-либо языка. Конечный автомат — это пятерка М = (К, , , S, F),
где K — конечное множество состояний;
— конечный входной алфавит;
— множество переходов;
S — начальное состояние (S К);
F — множество последних состояний (F К).
По мере считывания каждой литеры строки автоматом контроль передается от состояния к состоянию в соответствии с заданным множеством переходов.
Определение.
Если после считывания последней литеры строки автомат будет находиться в одном из последних состояний, то о строке говорят, что она принадлежит языку, принимаемому автоматом. В противном случае строка не принадлежит языку, принимаемому автоматом.
Пример.
Рассмотрим автомат M0 = (К, , , S, F),
где К ={А, В}, S = {0, 1}, S = {A}, F = {A},
= { (А, 0) = А, (А, 1) = В, (В, 0) = В, (В, 1) = А}.
Эти переходы означают, что "при чтении 0 в состоянии А управление передается в состояние А и т. д.
При чтении строки 0110010111 управление последовательно передается в следующем порядке через состояния А, А, В, А, А, А, В, В, А, В, А.
Так как А — есть последнее состояние, строка принимается конечным автоматом.
Однако, при чтении строки 00111 автомат проходит через состояния А, А, А, В, А, В. В не является последним состоянием строка 00111 не принимается, т.е. она не принадлежит языку, принимаемому этим автомат.
В связи с тем, что нули не влияют на состояние автомата, каждая единица изменяет его состояние с А на В и с В на А, и начальное состояние является тем же, что и последнее состояние. Язык, принимаемый автоматом, состоит из тех строк, которые содержат четное число единиц.
Переходы можно представить также с помощью таблицы и схематически:
Определение.
Автомат называется детерминированным, если в каждом элементе таблицы переходов содержится одно состояние. В недетерминированном ко нечном автомате это положение не выдерживается.
Следовательно, автомат — детерминированный.
Для выполнения лабораторной работы требуется умение писать программы на алгоритмическом языке, а также начальные знания по порождающим грамматикам.
Таким образом, последовательность выполнения лабораторной работы следующая:
Ознакомится с теорией регулярных грамматик.
В соответствии с заданным регулярным выражением написать регулярную грамматику.
Записать соответствующий детерминированный конечный автомат с указанием таблицы переходов.
Написать и отладить на компьютере синтаксический анализатор, распознающий выражения регулярного языка.
Привести контрольную распечатку.
Оформить отчет.
Работа считается выполненной только после оформления отчета, защиты и подписи преподавателя.
Программа "grammatika", представляющая синтаксический анализатор, соответствующий детерминированному конечному автомату М, имеет следующий вид:
program grammatika;
uses crt;
type perehod = record
old, term, new: char;
end;
var sost:array [1 .. 13] of perehod;
stroka: string [255];
sim, neterm: string [1];
dlina, n, i: integer;
ok: boolean;
begin { блок определения таблицы переходов }
sost[1].old :='S'; sost[1].term :='2'; sost[1].new := 'A';
sost[2].old :='A'; sost[2].term :='2'; sost[2].new := 'B';
sost[3].old :='B'; sost[3].term :='1’; sost[3].new := 'C';
sost[4].old := 'C'; sost[4].term := 'b'; sost[4].new := 'S';
sost[5].old := 'S'; sost[5].term := 'b'; sost[5].new := 'D';
sost[6].old :='D'; sost[6].term :='2'; sost[6].new :='E';
sost[7].old :='E'; sost[7] .term := '1'; sost[7].new :='F';
sost[8].old := 'F'; sost[8].term := 'b'; sost[8].new := 'D';
sost[9].old := 'F'; sost[9].term := '2'; sost[9].new := 'K';
sost[10].old:='B'; sost[10].term :='2'; sost[10].new := 'K';
sost[11].old := 'K'; sost[11].term := '2'; sost[11].new := 'L';
sost[12].old := 'L'; sost[12].term := '2'; sost[12].new := 'M';
sost[13].old := 'M'; sost[13].term := '2'; sost[13].new := 'L';
clrscr;
{ блок основной программы }
while TRUE do begin
writeln ('Введите строку символов’);
readln (stroka);
dlina := length (stroka);
n:=0;
ok :=' TRUE;
neterm := 'S';
while ok and (n < dlina) do
begin i := 0;
n:=n+ 1
sim := copy (stroka, n, 1);
ok := FALSE;
repeat i:=i+l;
if ((sost [i].old = neterm) and
(sost [i].term = sim)) then
begin
ok := TRUE;
neterm := sost[i].new;
end;
until ( ok or (i = 13));
end;
if ((neterm = 'S') or (neterm = 'B') or (neterm = 'F') or (neterm = 'L') and ok then writeln ('Данная строка принадлежит языку')
else writeln ('Данная строка не принадлежит языку'); readkey; end; end.
Замечание: листы отчета должны быть скреплены.
Вариант задания определяется по последним двум цифрам зачётной книжки.
Вариант определяется по списку группы у преподавателя. Если Ваш номер по списку группы больше чем количество вариантов, то из вашего номера вычитается количество вариантов, до тех пор, пока не получиться число меньше количества вариантов.
|
Вариант № 1. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -8x-9y -15x -1y < -62 -3x -10y > -136 3x -10y < -24 -10x +5y > -105 |
F = -5x-1y --> MAX -3x -4y > -44 -3x +3y > 3 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
5x1 + 4x2 + 5x3 max 17x1 + 3x2 + 5x3 390 13x1 + 7x2 + 12x3 251 7x1 + 7x2 + 3x3 266 128 |
6x1 + x2 + 5x3 max 7x1 + 17x2 + 17x3 242 16x1 + 5x2 + x3 329 18x1 + 3x2 + 3x3 325 128 |
|
Вариант № 2. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -4x-15y -11x -8y > -118 -3x -3y < -18 6x -8y < 10 -7x +14y < 56 |
F = -5x-5y --> MAX -1x -5y > -32 -5x -1y > -37 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
3x1 + 3x2 + 5x3 max 4x1 + 5x2 + 13x3 271 17x1 + 7x2 + 11x3 288 x1 + 4x2 + 10x3 355 157 |
4x1 + 3x2 + 5x3 max x1 + 2x2 + 18x3 383 x1 + 18x2 + 3x3 288 5x1 + 11x2 + 15x3 362 144 |
|
Вариант № 3. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -7x-9y -13x -9y > -218 1x -14y < -55 -1x +3y < 35 -12x +3y < -3 |
F = -5x-4y --> MAX -2x -3y > -26 -4x -1y > -30 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
4x1 + 4x2 + 5x3 max 7x1 + 4x2 + 17x3 355 3x1 + 5x2 + 4x3 400 4x1 + 4x2 + 8x3 302 288 |
5x1 + 4x2 + 3x3 max 19x1 + 10x2 + 9x3 267 7x1 + 6x2 + x3 369 16x1 + 11x2 + 5x3 292 128 |
|
Вариант № 4. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -8x-7y 1x +7y > 18 5x -5y > -15 -4x -1y < -10 -11x -6y > -105 |
F = -5x-6y -> MAX -5x -12y > -130 -6x -1y > -64 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
2x1 + 4x2 + 3 x3 max 4x1 + 18x2 + 8x3 263 6x1 + 17x2 + 3x3 326 7x1 + 14x2 + 12x3 293 83 |
3x1 + 3x2 + 7 x3 max 3x1 + 3x2 + 18x3 346 17x1 + 14x2 + 18x3 346 16x1 + 10x2 + x3 255 134 |
|
Вариант № 5. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -2x-7y -13x +3y < -10 -4x -7y < -39 -8x +7y > -18 -6x -7y > -89 |
F = 4x-2y --> MAX 4x +2y < 40 3x -3y < 3 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
4x1 + 4x2 + 4x3 max 18x1 + 8x2 + 7x3 325 3x1 + 11x2 + 14x3 364 8x1 + 4x2 + 2x3 254 153 |
4x1 + 5x2 + 5x3 max 7x1 + 14x2 + 11x3 241 18x1 + 13x2 + 18x3 282 3x1 + 14x2 + 11x3 329 95 |
|
Вариант № 6. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -14x-8y -7x -11y > -189 -6x +3y < 0 2x -10y < -18 -9x +1y > -133 |
F = -4x-4y --> MAX -3x -7y > -76 -6x -1y > -46 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
4x1 + 5x2 + 2x3 max 9x1 + 13x2 + 3x3 308 12x1 + 4x2 + 13x3 400 3x1 + 17x2 + x3 293 128 |
6x1 + 5x2 + 3x3 max 18x1 + 18x2 + 18x3 325 7x1 + 7x2 + 2x3 244 19x1 + 14x2 + 7x3 271 95 |
|
Вариант № 7. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -2x-12y -11x -8y > -216 2x -6y > -70 -8x +1y < -5 5x -9y < -4 |
F = -7x-3y --> MAX -6x -5y > -89 5x -2y < 32 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
2x1 + 2x2 + 2x3 max 6x1 + 4x2 + 9x3 358 18x1 + 4x2 + 2x3 260 13x1 + 4x2 + 10x3 260 130 |
4x1 + 5x2 + 4x3 max 3x1 + 17x2 + 7x3 302 x1 + 7x2 + 5x3 331 14x1 + 11x2 + 11x3 246 116 |
|
Вариант № 8. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -3x-8y 2x -12y > -154 -10x -7y > -192 -9x +2y < -3 5x -9y < -31 |
F = -6x-4y --> MAX 1x -4y > -31 7x -5y < -1 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
7x1 + 2x2 + 4x3 max 17x1 + 11x2 + 14x3 376 17x1 + 2x2 + 6x3 303 18x1 + 3x2 + 9x3 334 128 |
5x1 + 4x2 + 5x3 max 14x1 + 14x2 + 15x3 357 10x1 + 2x2 + 7x3 275 18x1 + 6x2 + 10x3 270 125 |
|
Вариант № 9. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -12x-7y -5x -9y > -169 6x -3y > -15 4x -8y < -16 -6x -5y < -46 |
F = -4x-5y --> MAX -2x -7y > -58 7x +3y < 69 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
4x1 + 4x2 + 3x3 max 9x1 + 14x2 + 9x3 347 17x1 + 5x2 + 6x3 396 18x1 + 7x2 + 6x3 358 130 |
5x1 + 2x2 + 5x3 max 13x1 + 2x2 + 5x3 398 19x1 + 2x2 + 10x3 316 6x1 + 3x2 + 19x3 369 262 |
|
Вариант № 10. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -7x-8y -4x -11y > -182 -4x +2y < 2 2x -14y < -40 -5x -1y > -71 |
F = -5x-5y --> MAX -2x -7y > -72 -8x -3y > -78 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
3x1 + 4x2 + 5x3 max 2x1 + 4x2 + 17x3 275 11x1 + 16x2 + 18x3 320 5x1 + 1x2 + 15x3 343 89,9 |
6x1 + 4x2 + 7x3 max 8x1 + 3x2 + 11x3 354 9x1 + 9x2 + 7x3 275 12x1 + 7x2 + 17x3 371 185,06 |
|
Вариант № 11. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -7x +2y 5x +3y < 87 4x -5y > -28 1x -8y < -22 -6x -7y < -69 |
F = -3x-4y --> MAX -3x -7y > -45 -4x -1y > -21 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
2x1 + 3x2 + 2x3 max 18x1 + 9x2 + 9x3 243 2x1 + 12x2 + 8x3 297 5x1 + 18x2 + 10x3 287 56 |
2x1 + 4x2 + 2x3 max x1 + 8x2 + 2x3 286 12x1 + 12x2 + 9x3 374 2x1 + 12x2 + 2x3 357 133 |
|
Вариант № 12. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = 3x-5y -1x -9y > -129 7x +1y < 82 -3x -5y < -54 -3x +1y < -3 |
F = -6x-5y --> MAX -3x -6y > -45 -6x -1y > -36 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
3x1 + 5x2 + 4x3 max 5x1 + 16x2 + 10x3 360 2x1 + 10x2 + 8x3 385 17x1 + 6x2 + 9x3 255 138 |
5x1 + 4x2 + 4x3 max x1 + 18x2 + 15x3 390 16x1 + 2x2 + 3x3 350 17x1 + 3x2 + 3x3 328 185 |
|
Вариант № 13. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -4x-5y -3x -5y > -86 2x -4y > -32 1x -8y < -29 -4x +1y < -7 |
F = -6x-4y --> MAX -2x -5y > -39 -5x -1y > -32 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
7x1 + 6x2 + 5x3 max 2x1 + x2 + 5x3 278 19x1 + 11x2 + 9x3 290 13x1 + 8x2 + 10x3 376 162 |
3x1 + 2x2 + 4x3 max 5x1 + 5x2 + 15x3 251 14x1 + 6x2 + 7x3 285 2x1 + 5x2 + 12x3 273 98 |
|
Вариант № 14. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -2x-11y 3x -9y > -66 -6x -4y > -92 -5x +1y < -11 2x -5y < -6 |
F = -4x-5y --> MAX -2x -5y > -39 -8x -4y > -76 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
5x1 + 7x2 + 6x3 max 16x1 + 17x2 + 15x3 333 4x1 + 19x2 + 14x3 312 x1 + 10x2 + 12x3 338 133 |
3x1 + 2x2 + 3x3 max 12x1 + 6x2 + 3x3 326 19x1 + 5x2 + 11x3 288 14x1 + 10x2 + 19x3 340 74 |
|
Вариант № 15. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = 2x-6y -3x -6y < -27 -4x +4y < 8 -7x +2y > -57 1x -10y > -68 |
F = -6x-4y --> MAX -7x -7y > -98 -10x -5y > -110 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
5x1 + 7x2 + 6x3 max 7x1 + 16x2 + 5x3 356 13x1 + 17x2 + 18x3 385 5x1 + 13x2 + 5x3 268 158 (144,3) |
4x1 + 6x2 + 6x3 max 6x1 + 13x2 + 17x3 260 5x1 + 5x2 + x3 361 6x1 + 17x2 + 9x3 328 218,4 |
|
Вариант № 16. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -2x-12y -6x -6y > -114 3x -4y > -29 2x -11y < -42 -4x -5y < -52 |
F = -5x-3y --> MAX -5x -7y > -61 -6x -2y > -50 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
3x1 + 3x2 + 3x3 max 17x1 + 14x2 + 14x3 353 16x1 + 3x2 + 5x3 367 9x1 + 13x2 + 10x3 368 75 |
4x1 + 4x2 + 6x3 max 9x1 + 14x2 + 13x3 308 6x1 + 3x2 + 14x3 284 7x1 + 5x2 + 19x3 288 155 |
|
Вариант № 17. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = 5x-6y 2x -6y > -60 -9x -1y > -93 -1x -2y < -18 -3x +1y < -4 |
F = -5x-3y --> MAX -3x -5y > -49 -6x -3y > -54 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
3x1 + 3x2 + 3x3 max 18x1 + 4x2 + 4x3 375 12x1 + 2x2 + 10x3 356 14x1 + 15x2 + 14x3 330 70 |
6x1 + 6x2 + 5x3 max 8x1 + 7x2 + 9x3 339 17x1 + 14x2 + 11x3 350 18x1 + 14x2 + 8x3 314 163 |
|
Вариант № 18. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = 5x-7y -1x +8y < 92 -6x -3y > -99 -2x -7y < -64 -4x +3y < 9 |
F = -4x-3y --> MAX -4x -6y > -56 -5x -1y > -28 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
3x1 + 2x2 + 3x3 max 2x1 + 16x2 + 7x3 255 14x1 + 2x2 + 7x3 287 17x1 + 2x2 + 7x3 309 128 |
4x1 + 2x2 + 6x3 max 7x1 + 3x2 + 16x3 351 8x1 + 2x2 + 18x3 267 16x1 + 7x2 + 12x3 261 131 |
|
Вариант № 19. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = 5x-7y -2x +10y < 114 -1x -7y < -65 -6x -2y > -88 -5x +3y < 11 |
F = -6x-8y --> MAX 1x -5y > -23 -8x -4y > -72 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
6x1 + 6x2 + 7x3 max 7x1 +8x2 + 13x3 248 14x1 + 11x2 + 13x3 304 x1 + 5x2 + 4x3 261 179 |
5x1 + 4x2 + 4x3 max 14x1 + 18x2 + 14x3 352 13x1 + 6x2 + 6x3 306 10x1 + x2 + 5x3 387 152 |
|
Вариант № 20. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = 2x +2y 3x -7y > -50 -5x +1y > -42 -5x -2y < -28 -3x -6y < -36 |
F = -4x-3y --> MAX -3x -6y > -51 -7x -4y > -60 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
4x1 + 6x2 + 7x3 max 4x1 + 3x2 + 14x3 336 4x1 + 8x2 + 17x3 367 6x1 + 12x2 + 10x3 351 238 |
5x1 + 5x2 + 4x3 max 8x1 + 6x2 + 2x3 393 11x1 + 6x2 + 3x3 245 9x1 + 14x2 + 16x3 398 175 |
|
Вариант № 21. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -7x +2y 4x +7y < 110 2x -2y > -14 3x -5y < -1 -2x -4y < -32 |
F = -7x-4y --> MAX -3x -6y > -51 -6x -1y > -43 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
5x1 + 4x2 + 7x3 max 5x1 + x2 + 9x3 254 11x1 + 18x2 + 11x3 389 6x1 + 4x2 + 13x3 329 218 |
6x1 + 4x2 + 3x3 max 8x1 + 6x2 + x3 351 9x1 + 10x2 + 16x3 337 18x1 + 7x2 + 3x3 261 145 |
|
|
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -1x-5y --> MAX -9x -7y > -127 2x -6y > -52 -4x -7y < -74 5x -5y < -10 |
F = -3x-4y --> MAX 3x +7y < 45 -5x -3y > -41 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
3x1 + 4x2 + 4x3 max 9x1 + 9x2 + 15x3 310 3x1 + 7x2 + 2x3 245 4x1 + 16x2 + 7x3 354 138 |
3x1 + 6x2 + 7x3 max 2x1 + 12x2 + 14x3 349 4x1 + 12x2 + 15x3 264 17x1 + 17x2 + 18x3 337 128 |
|
Вариант № 23. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -7x-3y -3x -8y > -114 -4x +2y < 2 -4x +3y > -30 -4x -5y < -43 |
F = -5x-3y --> MAX -2x -5y > -37 -6x -2y > -32 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
5x1 + 6x2 + 3x3 max 10x1 + 4x2 + 4x3 361 7x1 + 17x2 + 2x3 362 3x1 + 11x2 + 3x3 392 6141/20 |
7x1 + 2x2 + 7x3 max 15x1 + 14x2 + 19x3 254 11x1 + x2 + 13x3 274 18x1 + 4x2 + 17x3 261 9086/87 |
|
Вариант № 24. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = 4x-3y -5x -4y > -96 2x -5y > -48 -8x -1y < -45 4x -8y < -24 |
F = -3x-5y --> MAX -2x -6y > -44 -5x -3y > -48 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
3x1 + 3x2 + 3x3 max 18x1 + 5x2 + 7x3 258 14x1 + 13x2 + 8x3 255 14x1 + x2 + 7x3 288 105 |
6x1 + 6x2 + 3x3 max 16x1 + 9x2 + 2x3 264 15x1 + 3x2 + 2x3 319 6x1 + 10x2 + 3x3 370 370 |
|
Вариант № 25. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -5x-2y 4x -5y > -31 -5x -11y > -136 6x -3y < 39 -4x -7y < -60 |
F = -4x-6y --> MAX -2x -6y > -52 -6x -3y > -60 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
4x1 + 4x2 + 5x3 max 8x1 + 16x2 + 4x3 274 3x1 + x2 + 3x3 268 8x1 + 7x2 + 11x3 364 170 |
6x1 + 6x2 + 6x3 max 17x1 + 5x2 + 10x3 276 8x1 + 19x2 + 11x3 243 12x1 + 2x2 + 10x3 360 152 |
|
Вариант № 26. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = 4x-5y -3x -7y > -106 -6x +1y < -7 2x -5y < -16 -4x +2y > -26 |
F = -3x-5y --> MAX -3x -7y > -66 -8x -3y > -72 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
3x1 + 3x2 + 3x3 max 9x1 + 5x2 + x3 288 2x1 + 9x2 + 16x3 382 18x1 + 8x2 + 7x3 350 130 |
2x1 + 3x2 + 4x3 max 5x1 + 10x2 + 16x3 310 14x1 + 9x2 + 10x3 261 3x1 + 8x2 + 10x3 255 92 |
|
Вариант № 27. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -2x-7y 2x -6y > -46 -4x -5y > -70 1x -5y < -19 -3x +1y < -1 |
F = -2x-8y --> MAX -3x -6y > -45 3x -7y > -21 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
4x1 + 4x2 + 2x3 max 7x1 + 17x2 + 7x3 364 11x1 + 7x2 + 4x3 318 16x1 + 12x2 + 4x3 387 135 |
6x1 + 6x2 + 5x3 max 14x1 + 11x2 + 8x3 265 6x1 + 5x2 + 8x3 279 12x1 + 8x2 + x3 395 167 |
|
|
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = 2x-5y -1x -5y < -17 -3x +1y < -2 -2x -5y > -46 -2x -1y > -17 |
F = -1x-12y --> MAX -3x -5y > -46 5x -5y > -35 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
6x1 + 3x2 + 7x3 max 9x1 + 5x2 + 18x3 261 16x1 + 7x2 + 8x3 320 6x1 + 5x2 + 18x3 400 148 |
3x1 + 4x2 + 4x3 max 18x1 + 18x2 + 17x3 394 3x1 + 17x2 + 11x3 257 x1 + 16x2 + 11x3 306 93 |
|
Вариант № 29. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -2x +1y -2x -6y > -68 -4x +1y < -4 1x -7y < -13 -4x -3y > -52 |
F = -7x-3y --> MAX -1x -6y > -37 1x -8y < -23 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
3x1 + 2x2 + 3x3 max 8x1 + 11x2 + 8x3 341 18x1 + 11x2 + 17x3 328 12x1 + 9x2 + 9x3 286 59 |
4x1 + 4x2 + 4x3 max 9x1 + 14x2 + 19x3 358 7x1 + 6x2 + 5x3 256 4x1 + 4x2 + 2x3 360 148 |
|
Вариант № 30. |
|
|
Задача 1. Решить графическим способом. Найти MAX и MIN. |
Задача 2. Найти MAX. Подтвердить найденные решения, решив двойственную задачу линейного программирования. |
|
F = -1x-2y -2x -8y > -88 -4x +1y < -8 1x -7y < -19 -4x -4y > -72 |
F = 1x-6y --> MAX -3x -7y > -66 2x -4y > -16 |
|
Решить, используя симплекс метод. |
|
|
Задача 3. |
Задача 4. |
|
4x1 + 2x2 + 3x3 max 5x1 + 4x2 + 15x3 245 9x1 + 2x2 + 2x3 397 14x1 + 2x2 + 4x3 335 185 |
4x1 + 6x2 + 3x3 max 8x1 + 14x2 + 3x3 253 11x1 + 16x2 + 3x3 351 10x1 + 11x2 + 16x3 308 125 |
PAGE 46