Задача линейного программирования (озлп). Каноническая и вспомогательная задачи лп



страница1/4
Дата16.10.2012
Размер0.65 Mb.
ТипДокументы
  1   2   3   4
Тема 2 «Линейное программирование»


    1. Задачи линейного программирования (ЛП).

    2. Основная задача линейного программирования (ОЗЛП).

    3. Каноническая и вспомогательная задачи ЛП.

    4. Способы решения ОЗЛП и существование решения.

    5. Численные методы решения задач ЛП.

      1. Алгоритм симплекс-метода для задачи на минимум.

      2. Алгоритм симплекс-метода для задачи на максимум.

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

      4. Двойственный симплекс-метод.

    6. Двойственные задачи ЛП и основные теоремы двойственности.

      1. Постановка задачи.

      2. Теоремы двойственности.


2.1. Задачи линейного программирования
Мы уже рассматривали самые простые задачи, где выбор показателя эффективности (целевой функции) W достаточно явно диктуется целевой направленностью операции, а ее условия известны заранее (детерминированный случай). Тогда показатель эффективности зависит только от двух групп параметров: заданных условий и элементов решения x, т.е.

. (2.1)

Напомним, что в числе заданных условий фигурируют и ограничения, налагаемые на элементы решения. Пусть решение х представляет собой совокупность n элементов решения х1, х2, ..., хn (иначе – n-мерный вектор).

Требуется найти такие значения х1, х2, ..., хn, которые обращают величину W в максимум или в минимум (оба слова в математике объединяются под одним термином “экстремум”).

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

Трудности, возникающие при решении задач математического программирования, зависят:

а) от вида функциональной зависимости, связывающей W с элементами решения;

б) от “размерности” задачи, т.е. от количества элементов решения х1, х2, ..., хn;

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

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

а) показатель эффективности (целевая функция) W линейно зависит от элементов решения х1, х2, ..., хn ;

б) ограничения, налагаемые на элементы решения, имеют вид линейных равенств или неравенств относительно х1, х2, ..., хn.


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

Приведем пример задачи линейного программирования.

1. Задача о пищевом рационе. Ферма производит откорм скота с коммерческой целью. Для простоты допустим, что имеется всего четыре вида продуктов: П1, П2, П3, П4; стоимость единицы каждого продукта равна соответственно с1, с2, с3, с4. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков – не менее b1 единиц; углеводов – не менее b2 единиц; жиров – не менее b3 единиц. Для продуктов П1, П2, П3, П4 содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано в табл. 2.1, где аij (i = 1, 2, 3, 4; j = 1, 2, 3) – какие-то определенные числа; первый индекс указывает номер продукта, второй – номер элемента (белки, углеводы, жиры).

Требуется составить такой пищевой рацион (т. е. назначить количество продуктов П1, П2, П3, П4, входящих в него), чтобы условия по белкам, углеводам, жирам были выполнены, и при этом стоимость рациона была минимальна.

Таблица 2.1

Продукт

Элементы

белки

углеводы

жиры

П1

а11

а12

а13

П2

а21

а22

а23

П3

а31

а32

а33

П4

а41

а42

а43


Составим математическую модель. Обозначим х1, х2, x3, х4 – количество продуктов П1, П2, П3, П4, входящих в рацион. Показатель эффективности, который требуется минимизировать, – стоимость рациона (обозначим ее L); она линейно зависит от элементов решения х1, х2, x3, х4.

Тогда стоимость всего рациона можно найти по формуле



или, короче,

. (2.2)

Итак, вид целевой функции известен и она линейна. Запишем теперь в виде формул граничные условия по белкам, углеводам и жирам. Учитывая, что в одной единице продукта П1 содержится а11 единиц белка, в х1 единицах а11 х1 единиц белка, в х2 единицах продукта П2 содержится а21 x2 единиц белка и т. д., получим три неравенства:
(2.3)
Эти линейные неравенства представляют собой ограничения, накладываемые на элементы решения.

Таким образом, поставленная задача сводится к следующей: найти такие неотрицательные значения переменных х1, х2, x3, х4, чтобы они удовлетворяли ограничениям неравенств (2.3) и одновременно обращали в минимум линейную функцию этих переменных (2.2).
2.2. Основная задача линейного программирования
Любую задачу линейного программирования можно свести к стандартной форме записи, так называемой “основной задаче линейного программирования (ОЗЛП), которая формулируется так: найти неотрицательные значения переменных х1, х2,…, хn, которые удовлетворяли бы условиям:
(2.4)
и обращали бы в максимум линейную функцию этих переменных

. (2.5)
Совокупность неотрицательных решений (вектор) x = (х1, х2,…, хn), удовлетворяющая условию (2.4), называется допустимым решением задачи линейного программирования.

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

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

В различных ситуациях удобно использовать различные виды записи общей задачи ЛП. Рассмотрим наиболее распространенные из них:

  1. Произвольная форма записи, как в определении.

  2. Стандартная форма записи:

1) найти неотрицательные значения переменных х1, х2,…, хn, которые удовлетворяли бы условиям:

и минимизировали бы целевую функцию

;

2) в матричном виде

CX → min; AXB; X ≥ 0.
, ; ,

где .
3. Каноническая форма записи:

1) найти неотрицательные значения переменных х1, х2,…, хn, которые удовлетворяли бы условиям

и минимизировали (максимизировали) целевую функцию



2) в матричном виде:

CX → extr; AX = B; X ≥ 0.
; ; ,

где .
2.3. Каноническая и вспомогательная задачи ЛП
Для численного решения задач ЛП требуется предварительно приводить их к каноническому виду, т.е. найти неотрицательные значения х1, х2,…, хn, которые минимизировали бы целевую функцию



при следующих условиях:


Каноническая форма задачи характеризуется следующими тремя признаками:

  1. однородной системой ограничений в виде системы уравнений;

  2. однородными условиями неотрицательности, распространяющимися на все переменные, участвующие в задаче;

  3. минимизацией линейной функции.

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

.


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


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



.
В данной задаче нарушены все три признака канонической формы записи:

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

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

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

Полученная задача запишется в виде

.



Пример. Привести задачу ЛП к канонической форме на минимум.

Рассмотрим задачу ЛП в произвольной форме:


В данной задаче нарушены все три признака канонической формы.

1. Начнем с преобразования смешанной системы ограничений в систему уравнений. Введем слабые переменные в левые части неравенств со знаками “плюс” или “минус” в зависимости от знака неравенства. Слабой переменной ставится знак “+”, если в соответствующем неравенстве знак меньше, иначе – знак “–”. В результате система ограничений запишется в следующем виде:


2. Перейдем к преобразованию условий неотрицательности. Этими условиями не охвачена только одна переменная x2. Действительно, из ограничения x1  4 очевидно следует неотрицательность переменной x1, а неотрицательность переменной x3 задана явно пятым ограничением в исходной задаче x3  0.

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

Первый прием.

Представим переменную x2 в виде разности двух неотрицательных переменных:.

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




В результате получим задачу, содержащую не 6, а 7 переменных.

Второй прием.

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





3. Переходим к задаче минимизации линейной функции L:


Вспомогательная задача ЛП. Численные методы решения задач ЛП состоят из двух этапов: подготовительного и основного. Подготовительный этап состоит в выделении допустимого базиса в канонической задаче ЛП:

.

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

Прежде чем искать решение задачи ЛП, попробуем найти решение системы уравнений

При m = n система имеет единственное решение, которое при неотрицательности всех величин будет допустимым, оно же будет и оптимальным (поскольку других допустимых решений нет). Этот тривиальный случай нас не интересует.

При m < n система уравнений имеет бесчисленное множестве решений и задача ЛП становится объектом исследования. В этом случае необходимо выбрать m неизвестных (к примеру ), таких, чтобы определитель, составленный из коэффициентов при этих неизвестных, не обращался в нуль.

Тогда рассматриваемая система будет иметь вид



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

Одно из возможных решений можно найти, если переменные xm+1, …, xn положить равными нулю. Такое решение называется базисным. Оно имеет вид

.

Переменные x1, …, xm называют базисными, набор переменных x1, …, xm называют базисом, а переменные xm+1, …, xn называют небазисными или свободными. В одной системе уравнений может существовать несколько различных базисов.

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

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

.

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

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

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


.

Перед тем, как приступать к решению вспомогательной задачи линейного программирования, необходимо привести задачу к канонической форме записи. Поскольку данный пример уже задан в канонической форме, то выделяем допустимый базис. Переменная x2 входит только в первое уравнение, значит, её можно взять в качестве первой базисной переменной. Во втором и третьем уравнениях нет возможности выделить такие переменные, поэтому строим вспомогательную задачу. Для этого вводим во второе и третье уравнения искусственные переменные x5 ≥ 0, x6 ≥ 0, и сразу же выражаем их. Тогда целевая функция вспомогательной задачи равна сумме этих переменных z = x5 + x6, и вспомогательная задача будет иметь вид



.
Базис вспомогательной задачи состоит из переменных x2, x5, x6, допустимое базисное решение имеет вид

Заметим, что базисная переменная x2 не искусственная, а основная, поэтому в целевую функцию z она не включена. Целевая функция вспомогательной задачи включает только искусственные переменные.
2.4. Способы решения ОЗЛП и его существование
При решении задач ЛП часто пользуются геометрическими интерпретациями в разных вариантах. Рассмотрим задачу линейного программирования в произвольной форме записи
. (2.6)

(2.7)
. (2.8)
Известно, что одно линейное равенство в двумерном пространстве Е2 () определяет прямую линию, неравенство () определяет полуплоскость; одно линейное равенство в Е3, т.е. , задает плоскость, неравенство в Е3 задает полупространство; соответствующий объект, определяемый одним линейным равенством из (2.8) при n > 3, называется гиперплоскостью, одно соотношение из (2.7) определяет полупространство.

Выпуклой называется такая область GЕn, где Еn – размерность пространства векторной переменной X = (x1, …, xn), для которой справедливо следующее свойство: если из любых двух значений векторов x1= (x11, …, xn1) и x2= (x12, …, xn2), принадлежащих этой области (x1 G, x2 G), образовать выпуклую линейную комбинацию, и вектор х3 будет
,
где λ – произвольное действительное число, для которого 0 ≤ λ ≤ 1, то вектор x3 = (x13, …, xn3) также будет принадлежать этой области: x3G.

Ясно, что Еn (множество всех n-мерных векторов) выпукло. Также очевидно, что гиперплоскость в Еn и полупространства, ею образуемые, также выпуклые множества.

Пересечение двух или нескольких выпуклых множеств есть также выпуклое множество. В силу этого, пересечение конечного числа полупространств или гиперплоскостей есть множество выпуклое. Другими словами, любая система линейных уравнений или неравенств (ограничений (4.2) – (4.3) с n неизвестными определяет выпуклое множество векторов-решений системы. Если определяемое системой ограничений (4.2) – (4.3) допустимое множество векторов-решений ограничено, то это ограниченное множество называется выпуклым многогранником.

Возникает вопрос, всегда ли эта задача имеет решение. Нет, не всегда. Во-первых, может оказаться, что уравнения (2.7) вообще несовместны (противоречат друг другу). Может оказаться и так, что они совместны, но не в области неотрицательных решений, т.е. не существует ни одной совокупности чисел удовлетворяющей условиям (2.7). Наконец, может быть и так, что допустимые решения ОЗЛП существуют, но среди них нет оптимального: функция L в области допустимых решений не ограничена сверху.

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

Чтобы представить себе принципиальную сторону ОЗЛП, обратимся к геометрической интерпретации. Пусть число уравнений m на два меньше числа переменных n (nm = 2). Такой частный случай дает возможность геометрической интерпретации ОЗЛП на плоскости.

Мы знаем, что n линейно независимых уравнений (2.7) всегда можно разрешить относительно каких-то m базисных переменных, выразив их через остальные, свободные, число которых равно nm = k (в нашем случае k = 2). Предположим, что свободные переменные – это х1 и x2 (если это не так, то всегда можно заново перенумеровать переменные), а остальные: х3, x4,..., хn – базисные. Тогда вместо m уравнений (2.7) мы получим тоже m уравнений, но записанных в другой форме, разрешенных относительно х3, x4,..., хn.


Рис. 2.1
(2.9)

Будем изображать пару значений свободных переменных точкой с координатами (х1, х2) (рис. 2.1). Так как переменные х1, х2 должны быть неотрицательными, то допустимые значения свободных переменных лежат только выше оси Ох1 (на которой x2 = 0) и правее оси Ох2 (на которой x1 = 0).

Это мы отметим штриховкой, обозначающей “допустимую” сторону каждой оси.

Теперь построим на плоскости х1Ох2 область допустимых решений или же убедимся, что ее не существует. Базисные переменные х3, x4,..., хn тоже должны быть неотрицательными и удовлетворять уравнениям (2.9). Каждое такое уравнение ограничивает область допустимых решений. Действительно, положим в первом уравнении (2.9) х3 = 0; получим уравнение прямой линии
.



Рис. 2.2
На этой прямой х3 = 0; по одну сторону от нее расположена область, в которой х3 > 0, по другую – х3< 0. Отметим штриховкой ту сторону (полуплоскость), где х3 > 0 (рис. 2.2). Пусть эта сторона оказалась правее и выше прямой х3 = 0. Значит, вся область допустимых решений (ОДР) лежит в первом координатном углу, правее и выше прямой х3 = 0.

Аналогично поступим и со всеми остальными условиями (2.9). Каждое из них изобразится прямой со штриховкой, указывающей “допустимую” полуплоскость, где может лежать решение (рис. 2.3).


Рис. 2.3

Таким образом, мы построили n прямых: две оси координат (Ох1 и Ох2) и (n – 2) прямых х3 = 0, x4 = 0,..., хn = 0. Каждая из них определяет “допустимую” полуплоскость, где может лежать решение.
  1   2   3   4

Похожие:

Задача линейного программирования (озлп). Каноническая и вспомогательная задачи лп iconВопросы экзаменационных билетов по курсу "линейное программирование"
Постановка и различные формы записи задач линейного программирования: стандартная, каноническая, общая. Эквивалентность задач линейного...
Задача линейного программирования (озлп). Каноническая и вспомогательная задачи лп iconЗадачи линейного программирования (оптимизация)
Задачей линейного программирования (злп) называется задача отыскания экстремума (максимума или минимума) линейной функции от нескольких...
Задача линейного программирования (озлп). Каноническая и вспомогательная задачи лп iconЗадача линейного программирования
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы
Задача линейного программирования (озлп). Каноническая и вспомогательная задачи лп iconРешение задачи линейного программирования
Решить задачу линейного программирования. Используя теорию двойственности, доказать правильность полученного решения
Задача линейного программирования (озлп). Каноническая и вспомогательная задачи лп iconТранспортная задача линейного программирования
Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей
Задача линейного программирования (озлп). Каноническая и вспомогательная задачи лп iconЛекция-семинар: Построение математических моделей целочисленного линейного программирования
Для одной и той же оптимизационной задачи можно построить несколько моделей целочисленного линейного программирования
Задача линейного программирования (озлп). Каноническая и вспомогательная задачи лп iconЗадача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях
Цель данного курсового проекта составить план производства требуемых изделий, обеспечивающий максимальную прибыль от их реализации,...
Задача линейного программирования (озлп). Каноническая и вспомогательная задачи лп iconМногоиндексные задачи распределения ресурсов в иерархических системах
Задача распределения ресурсов в иерархических системах формализуется в виде многоиндексной задачи линейного программирования с ограничениями...
Задача линейного программирования (озлп). Каноническая и вспомогательная задачи лп iconМатематический факультет
Задача о наименьшем покрытии множества, как задача целочисленного линейного программирования
Задача линейного программирования (озлп). Каноническая и вспомогательная задачи лп iconДвойственный симплекс-метод и доказательство теоремы двойственности
Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org