![]() Главная страница Случайная лекция ![]() Мы поможем в написании ваших работ! Порталы: БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика ![]() Мы поможем в написании ваших работ! |
Глава I. Линейное программирование
1.1. Примеры задач линейного программирования. Пример 1. Пусть малое предприятие «Стакан» продает два вида прохладительных напитков, скажем, «Колокольчик» и «Буратино». Оба напитка изготавливаются тут же на месте из имеющихся запасов газированной воды, фруктового сиропа, лимонной кислоты и льда. Нормы расхода сырья на одну порцию готовой продукции и его запасы приведем для удобства в виде таблицы.
Допустим, что одна проданная порция «Колокольчика» приносит предприятию 5 рублей прибыли, порция «Буратино» - 6 рублей. Также предположим, что нет никаких проблем с изготовлением необходимого количества порций напитков и, что спрос перекрывает предложение. Возникает вполне естественный вопрос - сколько порций того и другого напитка следует произвести из имеющегося сырья, чтобы получить максимальную прибыль? Составим математическую модель данной задачи. Во-первых, введем переменные. Пусть Во-вторых, введем оптимизируемую целевую функцию, в данном случае прибыль: F Тот факт, что следует найти максимум, функции F В-третьих, запишем имеющиеся (нетривиальные) ограничения по сырью, вытекающие из того, что объем израсходованного на производство напитков сырья не превышает его суточного запаса.
Добавим сюда тривиальные (очевидные) ограничения:
Условие (1) вместе с ограничениями (2), (3) и дают требуемую математическую модель, которая является частным случаем задачи линейного программирования (см. п. 1.2.). Как мы увидим позже, модель примера №1 является однородной задачей линейного программирования (см. п. 1.3.). Дадим обобщение примера №1. Пример 2. Пусть предприятие выпускает к-типов продукции, используя т-видов ресурсов. При этом расход i-го вида ресурса на единицу j-го вида продукции составляют Модель задачи имеет в этом случае вид: F где
1.2. Постановка задачи линейного программирования. Основные понятия. Определение 1. Задача линейного программирования состоит в оптимизации линейной функции, зависящей от конечного числа вещественных переменных, при заданной системе линейных ограничений (имеющих вид равенства или неравенства). Определение 2. Зависящая от Пусть и
Тогда где - скалярное произведение векторов в n-мерном арифметическом пространстве Элементы пространства Определение 3. Ограничения вида: или или называются линейными. Если положить или или Другими словами, ограничение, имеющее вид равенства или неравенства, называется линейным, если справа стоит константа, а слева – линейная функция. Определение 4. Ограничения вида: - называются тривиальными. Эти ограничения записывают обычно в конце системы ограничений задачи линейного программирования (ЛП). Все остальные ограничения называются нетривиальными. Таким образом, общая задача ЛП может быть представлена в виде:
Здесь запись Определение 5. Оптимизируемая в задаче ЛП функции F называется целевой функцией этой задачи. Итак, задача ЛП определяется оптимизируемой линейной целевой функцией, нетривиальными линейными ограничениями типа равенства или неравенства и тривиальными ограничениям (которые могут отсутствовать). Обозначение: Для сокращения записи будем далее писать В векторном виде задача (1) имеет вид:
где Определение 6. Матрица А= Заметим, что матрица А имеет размеры m Определение 7. Вектор Определение 8. Вектор Определение 9. Множество всех допустимых решений образует область допустимых решений (ОДР) задачи ЛП. Определение 10. Вектор Определение 11. Свободный член Ясно, что Определение 12. Допустимое решение Смысл названия «вектор роста» становится ясным, если заметить, что вектор по переменной
Как известно из анализа, градиент функции Определение 13. Линией (на плоскости) или поверхностью (в пространстве) уровня функции где с – некоторая произвольная константа. 1.3. Различные формы задачи ЛП
Помимо общей задачи ЛП, выделяют однородную, каноническую и симплексную формы задачи ЛП. Определение 1. Задача ЛП называется однородной, если все ограничения имеют вид неравенства. Частными случаями однородной задачи являются задача о ресурсах (или производственная):
и задача об издержках:
В первом случае требуется найти максимум функции F («прибыли») при ограниченных «ресурсах» Определение 2. Задача ЛП называется канонической, если все нетривиальные ограничения имеют вид равенства и на все переменные наложены тривиальные ограничения. Поскольку, переменную Таким образом, каноническая задача ЛП может быть записана в виде:
или в координатной форме:
Определение 3. Каноническая задача ЛП называется симплексной, если: 1) система линейных ограничений имеет разрешенный вид, то есть матрица системы 2) столбец свободных членов 3) целевая функция F зависит только от свободных переменных. Разъясним смысл некоторых терминов, встречающихся в этом определении. Во-первых, напомним, что матрица размера т´т называется единичной (и обозначается Е=Е 1) 2) Например, единичными называются матрицы: Во-вторых, говорят, что система линейных уравнений (4) имеет разрешенный вид, если ее матрица содержит, возможно после перестановки столбцов, единичную подматрицу Е размера т Определение 4. Переменные, соответствующие базисным столбцам, называются также базисными, а остальные переменные – свободными. Если исходная матрица системы (4) содержит т линейно независимых строк (или столбцов), то есть ее ранг равен т, то, как известно, с помощью метода Гаусса система может быть приведена к равносильной системе, имеющей разрешенный вид. При этом в качестве базисных могут быть выбраны любые т линейно независимых столбцов исходной системы. Напомним, что метод Гаусса состоит в приведении матрицы системы к ступенчатому виду с помощью элементарных преобразований, к которым относятся: 1) перестановка строк; 2) умножение строки на число 3) замена одной из строк ее суммой с другой строкой, умноженой на некоторое произвольное число Как правило, базисными будем считать последние т столбцов матрицы системы. Замечание: Далее слова «матрица системы А содержит единичную подматрицу» будут означать, что матрица системы А после перестановки столбцов содержит единичную подматрицу Е размера т Определение 5. Решение системы (4) называется базисным, если все свободные переменные равны нулю. Определение 6. Допустимое базисное решение называется опорным решением. Напомним, что вектор Таким образом решение В дальнейшем будет показано, что оптимальное решение канонической задачи ЛП является опорным.
1.4. Связь между различными типами задачи ЛП.
Покажем, что общая задача ЛП может быть сведена как к однородной задаче ЛП, так и к канонической. I. Вначале сведём общую задачу к однородной. В соответствии с определением 1 п.1.3 для этого достаточно каждое ограничение вида равенства:
заменить на равносильную систему неравенств: Все ограничения задачи будут иметь вид неравенства и задача станет однородной. При этом число ограничений, конечно же, увеличится. II. Теперь сведем общую задачу ЛП к канонической. Для этого следует, во-первых, представить каждое неравенство в виде равенства и, во-вторых, добиться того, чтобы все переменные задачи были неотрицательны. Для каждого неравенства системы ограничений вида «меньше»
добавим новую (балансовую) переменную
Для каждого неравенства системы ограничений вида «больше» введем переменную Ясно, что так определенные балансовые переменные Для каждой переменной Заменив все такие Пример 1. Пусть дана задача ЛП
Требуется преобразовать исходную общую задачу ЛП к другим формам задачи ЛП. 1. Сведем эту задачу к однородной форме. Заменяя равенство из (1) на систему неравенств получим соответствующую однородную задачу:
2. Сведем задачу к каноничной форме. Добавим неотрицательные балансовые переменные Заменим переменную
Тогда получим каноническую задачу:
фактически равносильную исходной. Таким образом, показано, что общая, однородная и канонические формы задачи ЛП могут быть сведены друг к другу. Сведение произвольной канонической задачи ЛП к симплексной форме будет рассмотрено в следующих параграфах. Укажем на один частный случай сведения однородной задачи ЛП к симплексной форме. Пусть дана задача о ресурсах, то есть однородная задача ЛП вида:
причем все Сведем эту задачу к канонической с помощью введения балансовых переменных
Полученная каноническая задача ЛП на самом деле является симплексной, поскольку, во-первых, столбец свободных членов
1.5. Графический метод решения задачи ЛП.
Рассмотрим графический метод решения однородной двумерной задачи ЛП на конкретном примере. Пример №1. Решение. Найдем вначале область допустимых решений (ОДР). Решим графически первое неравенство:
Для этого построим вначале прямую линию, соответствующую уравнению:
Поскольку, если Теперь решим графически второе неравенство:
Ему соответствует прямая, заданная уравнением:
Ее мы построим несколько иначе. Перепишем уравнение (21) в виде: Тогда при Уравнение
заменяем на уравнение
Ясно, что прямая проходит через т. М5 (5;0), и имеет угловой коэффициент к = 2. При этом самому неравенству соответствует верхняя полуплоскость, отмеченная штрихами вверх от прямой (3). Тривиальному неравенству Изобразим на рисунке 1 вектор роста Построим теперь линию уровня
Мы взяли здесь константу С =11, для того чтобы точки пересечения прямой (3) с осями
Мы знаем, что значение функции F увеличивается в направлении вектора роста
На этой линии очевидно и будет достигаться максимальное значение целевой функции F в ОДР, поскольку при дальнейшем движении линии уровня в направлении вектора роста, она перестает пересекаться с ОДР. Итак, максимальное значение функция F(х) имеет в точке
Чтобы решить эту систему, сложим оба уровня. Тогда получим, что Из первого уравнения находим, что Итак, координаты точки С найдены – С (6;2). Найдем максимальное значение функции: Задача решена Ответ: максимальное значение целевой функции F достигается в точке С (6;2) и равно 29:
1.6. Выпуклые множества на плоскости и в пространстве.
Определение 1. Множество А Пусть
где Векторное равенство (2) равносильно системе:
Система (3) может быть преобразована в равносильную систему:
где
где В векторном виде система (5) примет вид: где Определение 2. Выпуклой (линейной) комбинацией векторов где все Равенство (6) показывает, что каждая точка Теорема 1. Пересечение любого числа выпуклых множеств является выпуклым множеством. Доказательство. Пусть Покажем, что множество А – выпукло. Пусть
Но, отсюда, очевидно, следует, что каждая точка отрезка Определение 3. Выпуклой оболочкой множества 1) 2) Лемма 1. Выпуклая оболочка множества А совпадает с пересечением всех выпуклых множеств, содержащих А. Доказательство. Пусть В0 – пересечение всех выпуклых множеств, содержащих А. Тогда очевидно В0, содержит А. С другой стороны по теореме 1 множество В0 само выпукло. Отсюда следует, что В0= VA, поскольку выполнены свойства 1) и 2). Лемма 2. Отрезок Доказательство. Пусть Лемма 3. Если выпуклое множество где Доказательство. Докажем это по индукции. Для двух точек
Пусть Пусть и Тогда и
Теорема 2. Выпуклая оболочка VA множества А Доказательство: Пусть В0 – множество всех таких комбинаций векторов множества А. Как следует из леммы 3 множество В0 содержится в любом выпуклом множестве В, содержащем А. Осталось показать, что само В0 – выпукло. Пусть Пусть - - выпуклая комбинация векторов Отметим, что треугольник и пирамида являются выпуклыми оболочками своих вершин, и, следовательно, каждая их точка является выпуклой комбинацией векторов-вершин. Определение. Выпуклая оболочка Предполагается, что точки лежат в общем положении, то есть не содержатся ни в какой гиперплоскости. Рассмотрим некоторую точку Первый случай. На каждой прямой l , проходящей через 1) 2) Второй случай. Существует содержащая Если Третий случай. Определение. Пусть точка Другими словами любой отрезок, содержащий угловую точку Замечание. Условие 2) Из (7) можно заменить в предыдущих рассуждениях на условие: Определение. Множество Значение угловых точек для описания выпуклого множества в Теорема 3. Замкнутое выпуклое множество
1.7. Геометрическая интерпретация однородной задачи линейного программирования.
Рассмотрим вначале однородную задачу линейного программирования на плоскости. Каждому ограничению вида неравенства:
- соответствует замкнутая полуплоскость
Системе ограничений однородной задачи:
- соответствует пересечение полуплоскостей
- также соответствуют полуплоскости При этом Таким образом, ОДР однородной задачи ЛП на плоскости представляет из себя пересечение конечного числа замкнутых полуплоскостей. Очевидно, каждая полуплоскость является выпуклым множеством. По теореме 1 п. 1.5. их пересечение также выпукло. Определение 1. Область, которая являеться пересечением конечного числа замкнутых полуплоскостей называется замкнутой выпуклой многоугольной областью. Если замкнутая выпуклая многоугольная область ограничена, то она называется замкнутым выпуклым многоугольником. В примере №1 п.1.4. это замкнутый выпуклый пятиугольник ОАВСД. Целевой функции.
соответствует вектор роста
На рисунке 1. п 1.4. это линии (А) и (В). При этом значение функции Таким образом, геометрически однородная задача ЛП на плоскости может быть сформулирована следующим образом: найти крайнюю (угловую) точку, в которой линия уровня все еще пересекает замкнутую выпуклую многоугольную область при параллельном переносе этой линии в направлении вектора роста (или в противоположном направлении). В трехмерном пространстве R3 каждому линейному неравенству
Соответствует одно из замкнутых полупространств, на которые делит все пространство R3 плоскость pi , определенная уравнением:
Соответственно вектор роста
где С – некая произвольная константа. Определение 2. Область, которая являеться пересечением конечного числа замкнутых полупространств в R3 называется выпуклой многогранной областью. Ограниченная выпуклая многогранная область называется выпуклым многогранником. Однородная задача ЛП в пространстве R3 может быть сформулирована так: найти крайнюю (угловую) точку, в которой поверхность уровня при движении в направлении вектора роста (или в противоположном направлении) все еще пересекает заданную выпуклую многогранную область. Заметим, что при этом поверхность уровня представляет из себя плоскость, определяемую уравнением (9). Вектор роста Соответствующая формулировка в n – мерном пространстве Rn фактически совпадает с данной. Единственное отличие состоит в том, что уравнение поверхности уровня:
задает не плоскость, а гиперплоскость в Rn. 1.8. Симплекс-метод решения задачи линейного программирования. 1.8.1. Пример решения задачи линейного программирования симплекс-методом.
Рассмотрим однородную задачу ЛП из примера №1 п. 1.5.:
Добавив к левым частям системы неравенств соответствующие балансовые переменные
Для удобства и единообразия запишем определение целевой функции
Запишем (2) и (3) в виде первой симплекс таблицы:
Первые три строки таблицы (4) содержат по сути расширенную матрицу системы линейных уравнений (2), к которой слева приписан столбец переменной Далее, переменная Вторая строка таблицы определяет переменную Третья строка определяет Значение целевой функции определяем по индексной строке: В дальнейшем мы покажем, что оптимальное решение канонической задачи ЛП является опорным, и, следовательно, его следует искать среди опорных решений. Симплекс-таблица (4) и дает одно из таких решений. Как проверить, является ли оно оптимальным? Оказывается, просто. Как мы увидим далее, если коэффициенты Но условие Мы видим, что в таблице (4) условие неотрицательности всех элементов индексной строки (разумеется, кроме правой части Выберем любой из этих столбцов, например, первый и назовем его ведущим. Определим для каждого
Дата добавления: 2014-10-14; просмотров: 722; Нарушение авторских прав ![]() Мы поможем в написании ваших работ! |