Взаимно двойственные задачи линейного программирования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для математической формулировки транспортной задачи в общей постановке обозначим через c_ij коэффициенты затрат, через М_i — мощности поставщиков, через N_j — мощности потребителей, где
i= 1, 2,..., m; j = 1, 2,..., n; m — число поставщиков, n — число потребителей. Тогда система ограничений примет вид:

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

Математическая формулировка транспортной задачи в общей постановке будет следующей: на множестве неотрицательных (допустимых) решений системы ограничений (4.1), (4.2) найти такое решение Х = (х₁₁, х₁₂,.., х_ij, …,х_mn), при котором значение линейной функции (4.3) минимально.

Произвольное допустимое решение Х = Х = (х₁₁, х₁₂,.., х_ij, …,х_mn) системы ограничений (4.1), (4.2) назовем распределением поставок. Такое решение задает заполнение таблицы поставок, поэтому в дальнейшем значение произвольной переменной х_ij и содержимое соответствующей клетки таблицы поставок будут отождествляться.

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

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

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

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

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

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

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

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

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

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

Решение. Построим экономико-математическую модель данной задачи, Искомый объем перевозки от i-го поставщика к j-му потребителю обозначим черёз x_ij и назовём поставкой клетки (i,j). Например, х₁₂ — искомый объем перевозки от 1- го поставщика ко 2-му потребителю или поставка клетки (1,2) и т. д. Заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения неизвестных х. Так, например, объем груза, забираемого от 1 -го поставщика, должен быть равен мощности этого поставщика — 60 единицам, т.е.
х₁₁+ х₁₂ + х₁₃ + х₁₄ = 60 (уравнение баланса по первой строке). Таким образом, чтобы мощность каждого из поставщиков была реализована, необходимо составить уравнения баланса для каждой строки таблицы поставок, т. е.

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

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

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

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

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

Решение. Находим в таблице поставок (см. табл.4.1.1) клетки с наименьшим коэффициентом затрат. Таких клеток две – (1,1) и (2,1) с коэффициентами затрат, равными 1. Сравним максимально возможные поставки для этих клеток: для клетки (1,1) х₁₁ = min {60, 20}= 20, для клетки (2,1) x₂₁= min {120, 20}=20.

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

В оставшейся таблице наименьшим коэффициентом затрат обладают две клетки: с₁₂ = с₂₄= 2. Сравним максимально возможные поставки для этих клеток: для клетки (1,2) х₁₂ = min {60, 110} = 60; для клетки (2,4) х₂₄ = min {120-20, 110} = 100. Даем поставку в клетку (2,4), для которой максимально возможная поставка оказалась больше: х₂₄ =100. При этом из рассмотрения выпадает вторая строка таблицы поставок (табл. 4.1.4).

Аналогично, продолжая заполнение таблицы поставок шаг за шагом, получаем х₁₂ = min{60, 110} = 60,x₃₂ = min {100, 110—60} = 50,
х₃₄ =min {100—50, 110—100}=10, x₃₃ = min {100-60, 40} = 40, табл. 4.1.5

Пусть решается задача определения условного экстремума функции z=f(X) при ограничениях φ_i(x₁,x₂,…,x_n)=0, i=1,2,…,m,m<n.

которая называется функцией Лагранжа. λ_i — постоянные множители (множители Лагранжа). Отметим, что множителям Лагранжа можно придать экономический смысл. Если f(х₁, х₂,..., х_n) — доход, соответствующий плану Х =(х₁, х₂,..., х_n), а функция φ_i (х₁, х₂,х_n) — издержки i-го ресурса, соответствующие этому плану, то λ_i — цена (оценка) i-го ресурса, характеризующая изменение экстремального значения целевой функции в зависимости от изменения размера i-го ресурса (маргинальная оценка). L(X) — функция n+m переменных (х₁, х₂,..., х_n, λ₁, λ₂,…, λ_m). Определение стационарных точек этой функции приводит к решению системы уравнений

Легко заметить, что L′ _λ_i (Х) =φ_i (Х), т.е. в (5.2) входят уравнения связи. Таким образом, задача нахождения условного экстремума функции z=f(X) сводится к нахождению локального экстремума функции L(X). Если стационарная точка найдена, то вопрос о существовании экстремума в простейших случаях решается на основании достаточных условий экстремума — исследования знака второго дифференциала d²L(X) в стационарной точке при условии, что переменные приращения Δх_j, связаны соотношениями

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

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

при условии, что х₁, х₂, х₃ удовлетворяют уравнению

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

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