ВЗАИМНО ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

ВЗАИМНО ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ



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

Таблица 2

задача i (исходная) задача ii (двойственная)
(10) при ограничениях , , (11) ……………………………, .   и условии неотрицательности х1³0, х2³0,…, хn³0                     (12) составить такой план выпуска продукции , при котором прибыль от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов. (13) при ограничениях , , (14) ……………………………., . и условии неотрицательности y1³0, y2³0,…, yn³0                     (15) составить такой набор цен ресурсов , при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будет не менее прибыли от реализации этой продукции.

Обе задачи обладают следующими свойствами:

1. В одной задаче ищут максимум линейной функции, в другой — минимум.

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

3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида «≤» а в задаче минимизации — все неравенства вида «≥».

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

для задачи i а   

для задачи ii а¢   

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

6. Условия неотрицательности переменных имеются в обеих задачах.

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

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

1. Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду «≤», а если минимум - к виду «≥». для этого неравенства, в которых данное требование не выполняется, умножить на (-1).

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

3. Найти матрицу а1′ , транспонированную к матрице а1.

4. Сформулировать двойственную задачу на основании полученной матрицы а1′ и условия неотрицательности переменных.

Пример двойственной задачи

Составить задачу, двойственную следующей задаче:

при ограничениях:

,

,

,

,

 

Решение. Так как исходная задача на максимизацию, то приведем все неравенства системы ограничений к виду «≤», для чего обе части первого и четвертого неравенства умножим на (-1), получим:

,

,

,

2. Составим расширенную матрицу системы:

а1=

      
3. Найдем матрицу  транспонированную к а1:

а1¢=

4. Сформулируем двойственную задачу:

при ограничениях

,

,

  

ТРАНСПОРТНАЯ ЗАДАЧА

Особенности экономико-математической модели транспортной задачи:

• система ограничений есть система уравнений (т.е. транспортная задача задана в канонической форме);

• коэффициенты при переменных системы ограничений равны единице или нулю;

• каждая переменная входит в систему ограничений два раза.

Для математической формулировки транспортной задачи в общей постановке обозначим через cij коэффициенты затрат, через мi - мощности поставщиков, через nj - мощности потребителей, где  m - число поставщиков, n - число потребителей. Тогда система ограничений примет вид:

                                                      (16)

                                                      (17)

Система (16) включает в себя уравнение баланса по строкам, а система (17) - по столбцам таблицы поставок. Линейная функция в данном случае

.                                                (18)

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

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

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

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

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

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

 

Пример транспортной задачи

Построить экономико-математическую модель следующей задачи. имеются три поставщика и четыре потребителя. мощность поставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары “поставщик - потребитель” сведены в таблицу поставок (табл. 3).

Таблица 3

поставщики

мощность поставщиков

потребители и их спрос

1 2 3 4
20 110 40 110
1 60 1 х11 2 х12 5 х13 3 х14
2 120 1 х21 6 х22 5 х23 2 х24
3 106 6 х31 3 х32 7 х33 4 х34

 

В левом верхнем углу произвольной (ij-клетки (i - номер строки, j - номер столбца) стоит так называемый коэффициент затрат - затраты на перевозку единицы груза от i-го поставщика к j-му потребителю, например, в левом верхнем углу клетки (1, 4) стоит число 3, следовательно, перевозка единицы груза от 1-го поставщика к 4-му потребителю обойдется в 3 условных денежных единицы и т. д.

Задача ставится следующим образом: найти объемы перевозок для каждой пары «поставщик — потребитель» так, чтобы:

1) мощности всех поставщиков были реализованы;

2) спросы всех потребителей были удовлетворены;

3) суммарные затраты на перевозку были бы минимальны.

Решение. Построим экономико-математическую модель данной задачи, искомый объем перевозки от i-го поставщика к j-му потребителю обозначим черёз xij и назовём поставкой клетки (i,j). Например, х12 - искомый объем перевозки от 1- го поставщика ко 2-му потребителю или поставка клетки (1,2) и т. д. заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения неизвестных х. так, например, объем груза, забираемого от 1 -го поставщика, должен быть равен мощности этого поставщика - 60 единицам, т.е.  (уравнение баланса по первой строке). Таким образом, чтобы мощность каждого из поставщиков была реализована, необходимо составить уравнения баланса для каждой строки таблицы поставок, т. е.

,

,                                                                 (19)

.  

 

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

,

,                                                                             (20)

,

.     

 

Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует дополнительно предположить, что

 

Суммарные затраты р на перевозку выражаются через коэффициенты затрат и поставки следующим образом;

                   (21)

Найдем первоначальное базисное распределение поставок для транспортной задачи методом «северо-западного угла».

Решение. дадим переменной х11 максимально возможное значение или, иными словами, максимально возможную поставку в клетку (1,1) - “северо-западный” угол таблицы поставок: х11= min {60, 20) = 20. После этого спрос 1-го потребителя будет полностью удовлетворен, в результате чего первый столбец таблицы поставок выпадет из последующего рассмотрения (заполненные клетки будем перечеркивать сплошной линией (табл. 4) клетки, выпавшие из последующего рассмотрения, перечеркнуты пунктирной линией. в таблице поставок найдем новый “северо-западный” угол - клетку (1,2) и дадим в нее максимально возможное значение. Учитывая, что 1-й поставщик уже отдал 20 единиц груза и у него осталось только 40 = 60 - 20 единиц груза, получаем, что . После этого мощность 1-го поставщика полностью реализована и из рассмотрения выпадет первая строка таблицы поставок (перечеркиваем сплошной линией клетку (1,2) и пунктирной линией оставшиеся свободные клетки первой строки). в оставшейся таблице снова находим “северо-западный угол” и т. д. в результате получаем следующее исходное распределение поставок (табл.4).

Таблица 4.

  20 110 40 110
60 1 20 2 40 5 5
120 1 6 70 5 40 2 10
100 6 3 7 4 100

Решение методом наименьших затрат.

Решение. Находим в таблице поставок (табл.4) клетки с наименьшим коэффициентом затрат. Таких клеток две – (1,1) и (2,1) с коэффициентами затрат, равными 1. сравним максимально возможные поставки для этих клеток: для клетки (1,1) , для клетки (2,1) .

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

Таблица 5

  20 110 40 110
60 1   2 5 3  
120 1 20 6 5 2
100 6   3   7 7

 

В оставшейся таблице наименьшим коэффициентом затрат обладают две клетки: с12 = с24= 2. Сравним максимально возможные поставки для этих клеток: для клетки (1,2) ; для клетки (2,4) . Даем поставку в клетку (2,4), для которой максимально возможная поставка оказалась больше: х24 =100. При этом из рассмотрения выпадает вторая строка таблицы поставок (табл. 6).

Таблица 6

  20 110 40 110
60 1   2 5 3
120 1 20 6 5 2 100
100 6   3   7 4

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

 

 

Таблица 7

  20 110 40 110
60 1   2 60 5 3
120 1 20 6 5 2 100
100 6   3 50 7 40 4 10

МЕТОД МНОЖИТЕЛЕЙ ЛАГРАНЖА

Пусть решается задача определения условного экстремума функции  при ограничениях  

Составим функцию

 ,                                                    (22)

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

                                  (23)

Легко заметить, что  т.е. в (23) входят уравнения связи. Таким образом, задача нахождения условного экстремума функции  сводится к нахождению локального экстремума функции l ( x ). Если стационарная точка найдена, то вопрос о существовании экстремума в простейших случаях решается на основании достаточных условий экстремума - исследования знака второго дифференциала  в стационарной точке при условии, что переменные приращения , связаны соотношениями

                                      (24)

полученными путем дифференцирования уравнений связи.

Пример решения задачи

Найти наибольшее и наименьшее значения функции

при условии, что х1, х2, х3 удовлетворяют уравнению /

Решение. Уравнение связи определяет в пространстве сферу единичного радиуса с центром в начале координат рис. 3.

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

Рис. 3.

 

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

Составим функцию Лагранжа:

Найдем частные производные этой функции по х1, х2, х3, .

,

,

,

.

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

,

,

,

.

 

Решая систему, получим стационарные точки, в которых найдем значения функции z:

1. ,

2. ,

3. ,

4. ,

5. ,

6. .

Выберем из всех значений наибольшее и наименьшее:  а
. Легко видеть, в каких точках сферы доcтигаются эти значения.



Последнее изменение этой страницы: 2021-04-05; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.231.230.177 (0.02 с.)