Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Тема 2.1. Задачи линейного программирования. Двойственные задачи линейного программирования.
Пункт 1. Понятие задачи линейного программирования.
Пункт 2.
Пункт 3. Понятие двойственной задачи линейного программирования.
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования, состоящей, как мы уже знаем, в нахождении максимального значения функции
при условиях
Определение. Задача, состоящая в нахождении минимального значения функции
при условиях
называется двойственной по отношению к задаче (25) – (27). Задачи (25) – (27) и (28) – (30) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:
1. Целевая функция исходной задачи (25) – (27) задается на максимум, а целевая функция двойственной (28) – (30) – на минимум.
2. Матрица
(31)
составленная из коэффициентов при неизвестных в системе ограничений (33) исходной задачи – (27), и аналогичная матрица
(32)
в двойственной задаче (28) – (30) получаются друг из друга транспонированием (т. е. заменой строк столбцами, а столбцов – строками).
3. Число переменных в двойственной задаче (28) – (30) равно числу ограничений в системе (26) исходной задачи (25) – (27), а число ограничений в системе (29) двойственной задачи – числу переменных в исходной задаче.
4. Коэффициентами при неизвестных в целевой функции (28) двойственной задачи (28) – (30) являются свободные члены в системе (26) исходной задачи (25) – (27), а правыми частями в соотношениях системы (29) двойственной задачи – коэффициенты при неизвестных в целевой функции (25) исходной задачи.
5. Если переменная xj исходной задачи (25) – (27) может принимать только лишь положительные значения, то j–е условие в системе (29) двойственной задачи (28) – (30) является неравенством вида “”. Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 –соотношение в системе (27) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (26) исходной задачи (25) – (27) и переменными двойственной задачи (28) – (30). Если i – соотношение в системе (26) исходной задачи является неравенством, то i–я переменная двойственной задачи . В противном случае переменная уj может принимать как положительные, так и отрицательные значения.
Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (26) прямой задачи и соотношения (29) двойственной задачи являются неравенствами вида “ ”. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.
Пример. Составить двойственную задачу по отношению к задаче, состоящей в максимизации функции
(33)
при условиях
(34)
(35)
Решение. Для данной задачи
и
Число переменных в двойственной задаче равно числу уравнений в системе (34), т. е. равно трем. Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений (34), т.е. числа 12, 24, 18.
Целевая функция исходной задачи (33) – (35) исследуется на максимум, а система условий (34) содержит только уравнения. Поэтому в двойственной задаче целевая функция исследуется на минимум, а ее переменные могут принимать любые значения (в том числе и отрицательные). Так как все три переменные исходной задачи (33) – (35) принимают только лишь неотрицательные значения, то в системе условий двойственной задачи должны быть три неравенства вида “ ”. Следовательно, для задачи (33) – (35) двойственная задача такова: найти минимум функции при условиях
Связь между решениями прямой и двойственной задач
Рассмотрим пару двойственных задач, образованную основной задачей линейного программирования и двойственной к ней. Исходная задача: найти максимум функции
(36)
при условиях
(37)
(38)
Двойственная задача: найти минимум функции
(39)
при условиях
(40)
Каждая из задач двойственной пары (36) – (38) и (39), (40) фактически является самостоятельной задачей линейного программирования и может быть решена независимо одна от другой. Однако при определении симплексным методом оптимального плана одной из задач тем самым находится решение и другой задачи.
Существующие зависимости между решениями прямой и двойственной задач характеризуются сформулированными ниже леммами и теоремами двойственности.
Лемма 1.1 Если Х – некоторый план исходной задачи (36) – (38), a Y – произвольный план двойственной задачи (39), (40), то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y, т. е.
Лемма 1.2 Если для некоторых планов X* и Y* задач (36) – (38) и (39), (40), то X* – оптимальный план исходной задачи, а Y* – оптимальный план двойственной задачи.
Теорема (первая теорема двойственности). Если одна из задач двойственной пары (36) – (38) или (39), (40) имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, т. е.
Если же целевая функция одной задачи из двойственной пары неограничена (для исходной (36) – (38) – сверху, для двойственной (39), (40) – снизу), то другая задача вообще не имеет планов.
Теорема (вторая теорема двойственности). План задачи (43) – (45) и план задачи (46), (47) являются оптимальными планами этих задач тогда и только тогда, когда для любого выполняется равенство
Геометрическая интерпретация двойственных задач
Если число переменных в прямой и двойственной задачах, образующих данную пару, равно двум, то, используя геометрическую интерпретацию задачи линейного программирования, можно легко найти решение данной пары задач. При этом имеет место один из следующих трех взаимно исключающих друг друга случаев: 1) обе задачи имеют планы; 2) планы имеет только одна задача; 3) для каждой задачи двойственной пары множество планов пусто.
Пример. Для задачи, состоящей в определении максимального значения функции при условиях
составить двойственную задачу и найти решение обеих задач.
Решение. Двойственной задачей по отношению к исходной является задача, состоящая в определении минимального значения функции при условиях
Как в исходной, так и в двойственной задаче число неизвестных равно двум. Следовательно, их решение можно найти, используя геометрическую интерпретацию задачи линейного программирования (рис. 7 и 8).
Как видно из рис. 8, максимальное значение целевая функция исходной задачи принимает в точке В.Следовательно, Х*=(2, 6) является оптимальным планом, при котором . Минимальное значение целевая функция двойственной задачи принимает в точке Е (рис. 8). Значит, Y*=(1; 4) является оптимальным планом двойственной задачи, при котором Таким образом, значения целевых функций исходной и двойственной задач при их оптимальных планах равны между собой.
Из рис. 7 видно, что при всяком плане исходной задачи значение целевой функции не больше 46. Одновременно, как видно из рис. 8, значение целевой функции двойственной задачи при любом ее плане не меньше 46. Таким образом, при любом плане исходной задачи значение целевой функции не превосходит значения целевой функции двойственной задачи при ее произвольном плане.
Пример.
Найти решение двойственной пары задач.
Исходная задача;
Двойственная задача:
Решение. Как исходная, так и двойственная задача содержат по две переменные. Поэтому их решение находим, используя геометрическую интерпретацию задачи линейного программирования (рис. 7 и 8). Из рис. 7 видно, что исходная задача не имеет оптимального плана из-за неограниченности снизу ее целевой функции на множестве допустимых решений.
Из рис. 10 следует, что двойственная задача не имеет планов, поскольку многоугольник решений ее пуст. Это означает, что если исходная задача двойственной пары не имеет оптимального плана из-за неограниченности на множестве допустимых решений ее целевой функции, то двойственная задача также не имеет планов.
Тема 2.2. Симплекс-метод.
Решение любой задачи линейного программирования можно найти симплексным методом. Прежде чем применять указанный метод, следует записать исходную задачу в форме основной задачи линейного программирования, если она не имеет такой формы записи.
Симплексный метод решения задачи линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный план и каждый ее опорный план является невырожденным). Указанный переход возможен, если известен какой-нибудь исходный опорный план.
Рассмотрим задачу, для которой этот план можно непосредственно записать.
Пусть требуется найти максимальное значение функции
при условиях
Здесь и – заданные постоянные числа
Векторная форма данной задачи имеет следующий вид: найти максимум функции
(22)
при условиях
(23)
(24)
где
Так как
то по определению опорного плана является опорным планом данной задачи (последние компонент вектора Х равны нулю). Этот план определяется системой единичных векторов которые образуют базис m-мерного пространства. Поэтому каждый из векторов а также вектор могут быть представлены в виде линейной комбинации векторов данного базиса. Пусть
Положим
Так как векторы – единичные, то и а
Теорема 5 (признак оптимальности опорного плана). Опорный план задачи (22) – (24) является оптимальным, если для любого j
Теорема 6. Если для некоторого j=k и среди чисел нет положительных , то целевая функция (22) задачи (22) – (24) не ограничена на множестве ее планов.
Теорема 7. Если опорный план Х задачи (22) – (24) невырожден и , но среди чисел есть положительные (не все ), то существует опорный план X' такой, что
Сформулированные теоремы позволяют проверить, является ли найденный опорный план оптимальным, и выявить целесообразность перехода к новому опорному плану.
Исследование опорного плана на оптимальность, а также дальнейший вычислительный процесс удобнее вести, если условия задачи и первоначальные данные, полученные после определения исходного опорного плана, записать так, как показано в табл. 3.
В столбце С6 этой таблицы записывают коэффициенты при неизвестных целевой функции, имеющие те же индексы, что и векторы данного базиса.
В столбце записывают положительные компоненты исходного опорного плана, в нем же в результате вычислений получают положительные компоненты оптимального плана. Столбцы векторов представляют собой коэффициенты разложения этих векторов по векторам данного базиса.
В табл. 3 первые m строк определяются исходными данными задачи, а показатели (m+1)-й строки вычисляют. В этой строке в столбце вектора записывают значение целевой функции, которое она принимает при данном опорном плане, а в столбце вектора – значение
Значение Zj находится как скалярное произведение вектора на вектор
Значение равно скалярному произведению вектора P0 на вектор :
После заполнения таблицы 3 исходный опорный план проверяют на оптимальность. Для этого просматривают элементы -й строки таблицы. В результате может иметь место один из следующих трех случаев:
1) для j=m+1, (при ). Поэтому в данном случае числа для всех j от 1 до n;
2) для некоторого j, и все соответствующие этому индексу величины
3) для некоторых индексов j, и для каждого такого j , по крайней мере, одно из чисел положительно.
В первом случае на основании признака оптимальности исходный опорный план является оптимальным. Во втором случае целевая функция не ограничена сверху на множестве планов, а в третьем случае можно перейти от исходного плана к новому опорному плану, при котором значение целевой функции увеличится. Этот переход от одного опорного плана к другому осуществляется исключением из исходного базиса какого-нибудь из векторов и введением в него нового вектора. В качестве вектора, вводимого в базис, можно взять любой из векторов имеющий индекс j, для которого . Пусть, например, и решено ввести в базис вектор
Для определения вектора, подлежащего исключению из базиса, находят для всех Пусть этот минимум достигается при i=r. Тогда из базиса исключают вектор , а число называют разрешающим элементом.
Столбец и строку, на пересечении которых находится разрешающий элемент, называют направляющими.
После выделения направляющей строки и направляющего столбца находят новый опорный план и коэффициенты разложения векторов через векторы нового базиса, соответствующего новому опорному плану. Это легко реализовать, если воспользоваться методом Жордана–Гаусса. При этом можно показать, что положительные компоненты нового опорного плана вычисляются по формулам
(25)
а коэффициенты разложения векторов через векторы нового базиса, соответствующего новому опорному плану, – по формулам
(26)
После вычисления и согласно формулам (25) и (26) их значения заносят в табл. 4. Элементы -й строки этой таблицы могут быть вычислены либо по формулам
(27)
(28)
либо на основании их определения.
Таблица 3
Таблица 4
Наличие двух способов нахождения элементов -й строки позволяет осуществлять контроль правильности проводимых вычислений.
Из формулы (27) следует, что при переходе от одного опорного плана к другому наиболее целесообразно ввести в базис вектор , имеющий индекс j, при котором максимальным по абсолютной величине является число . Однако с целью упрощения вычислительного процесса в дальнейшем будем вектор, вводимый в базис, определять, исходя из максимальной абсолютной величины отрицательных чисел . Если же таких чисел несколько, то в базис будем вводить вектор, имеющий такой же индекс, как и максимальное из чисел , определяемых данными числами
Итак, переход от одного опорного плана к другому сводится к переходу от одной симплекс-таблицы к другой. Элементы новой симплекс-таблицы можно вычислить как с помощью рекуррентных формул (25)-(28), так и по правилам, непосредственно вытекающим из них. Эти правила состоят в следующем.
В столбцах векторов, входящих в базис, на пересечении строк и столбцов одноименных векторов проставляются единицы, а все остальные элементы данных столбцов полагают равными нулю.
Элементы векторов и в строке новой симплекс-таблицы, в которой записан вектор, вводимый в базис, получают из элементов этой же строки исходной таблицы делением их на величину разрешающего элемента. В столбце в строке вводимого вектора проставляют величину , где k – индекс вводимого вектора.
Остальные элементы столбцов вектора и новой симплекс-таблицы вычисляют по правилу треугольника. Для вычисления какого-нибудь из этих элементов находят три числа:
1) число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы;
2) число, стоящее в исходной симплекс-таблице на пересечении строки, в которой находится искомый элемент новой симплекс-таблицы, и столбца, соответствующего вектору, вводимому в базис;
3) число, стоящее в новой симплекс-таблице на пересечении столбца, в котором стоит искомый элемент, и строки вновь вводимого в базис вектора (как отмечено выше, эта строка получается из строки исходной симплекс-таблицы делением ее элементов на разрешающий элемент).
Эти три числа образуют своеобразный треугольник, две вершины которого соответствуют числам, находящимся в исходной симплекс-таблице, а третья – числу, находящемуся в новой симплекс-таблице. Для определения искомого элемента новой симплекс-таблицы из первого числа вычитают произведение второго и третьего.
После заполнения новой симплекс-таблицы просматривают элементы -й строки. Если все , то новый опорный план является оптимальным. Если же среди указанных чисел имеются отрицательные, то, используя описанную выше последовательность действий, находят новый опорный план. Этот процесс продолжают до тех пор, пока либо не получают оптимальный план задачи, либо не устанавливают ее неразрешимость.
При нахождении решения задачи линейного программирования мы предполагали, что эта задача имеет опорные планы и каждый такой план является невырожденным. Если же задача имеет вырожденные опорные планы, то на одной из итераций одна или несколько переменных опорного плана могут оказаться равными нулю. Таким образом, при переходе от одного опорного плана к другому значение функции может остаться прежним. Более того, возможен случай, когда функция сохраняет свое значение в течение нескольких итераций, а также возможен возврат к первоначальному базису. В последнем случае обычно говорят, что произошло зацикливание. Однако при решении практических задач этот случай встречается очень редко, поэтому мы на нем останавливаться не будем.
Итак, нахождение оптимального плана симплексным методом включает следующие этапы:
1. Находят опорный план.
2. Составляют симплекс-таблицу.
3. Выясняют, имеется ли хотя бы одно отрицательное число . Если нет, то найденный опорный план оптимален. Если же среди чисел имеются отрицательные, то либо устанавливают неразрешимость задачи, либо переходят к новому опорному плану.
4. Находят направляющие столбец и строку. Направляющий столбец определяется наибольшим по абсолютной величине отрицательным числом , а направляющая строка – минимальным из отношений компонент столбца вектора к положительным компонентам направляющего столбца.
5. По формулам (25) – (28) определяют положительные компоненты нового опорного плана, коэффициенты разложения векторов Pj по векторам нового базиса и числа , . Все эти числа записываются в новой симплекс-таблице.
6. Проверяют найденный опорный план на оптимальность. Если план не оптимален и необходимо перейти к новому опорному плану, то возвращаются к этапу 4, а в случае получения оптимального плана или установления неразрешимости процесс решения задачи заканчивают.
Пример 9.
Для изготовления различных изделий А, В и С предприятие использует три различных вида сырья. Нормы расхода сырья на производство одного изделия каждого вида, цена одного изделия А, В и С, а также общее количество сырья каждого вида, которое может быть использовано предприятием, приведены в табл. 5.
Таблица 5
|
Вид сырья |
Нормы затрат сырья (кг) на одно изделие |
Общее количество сырья (кг) |
||
|
А |
В |
С |
||
|
I II III |
18 6 5 |
15 4 3 |
12 8 3 |
360 192 180 |
|
Цена одного изделия (руб.) |
9 |
10 |
16 |
|
Изделия А, В и С могут производиться в любых соотношениях (сбыт обеспечен), но производство ограничено выделенным предприятию сырьем каждого вида.
Составить план производства изделий, при котором общая стоимость всей произведенной предприятием продукции является максимальной.
Решение. Составим математическую модель задачи. Искомый выпуск изделий А обозначим через x1, изделий В –через , изделий С – через . Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные должны удовлетворять следующей системе неравенств:
(29)
Общая стоимость произведенной предприятием продукции при условии выпуска x1 изделий А, изделий В и изделий С составляет
(30)
По своему экономическому содержанию переменные могут принимать только лишь неотрицательные значения:
(31)
Таким образом, приходим к следующей математической задаче: среди всех неотрицательных решений системы неравенств (29) требуется найти такое, при котором функция (30) принимает максимальное значение.
Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений
Эти дополнительные переменные по экономическому смыслу означают не используемое при данном плане производства количество сырья того или иного вида. Например, – это неиспользуемое количество сырья I вида.
Преобразованную систему уравнений запишем в векторной форме:
где
Поскольку среди векторов имеются три единичных вектора, для данной задачи можно непосредственно записать опорный план. Таковым является план Х=(0; 0; 0; 360; 192; 180), определяемый системой трехмерных единичных векторов которые образуют базис трехмерного векторного пространства.
Составляем симплексную таблицу для I итерации (табл. 6), подсчитываем значения и проверяем исходный опорный план на оптимальность:
Для векторов базиса
Таблица 6
|
i |
Базис |
Сб |
P0 |
9 |
10 |
16 |
0 |
0 |
0 |
|
|
|
|
P1 |
P2 |
Р3 |
p4 |
Р5 |
P6 |
|
|
1 2 3 4 |
P4 р5 p6 |
0 0 0 |
360 192 180 0 |
18 6 5 -9 |
15 4 3 -10 |
12 8 3 -16 |
1 0 0 0 |
0 1 0 0 |
0 0 1 0 |
Как видно из таблицы 6, значения всех основных переменных равны нулю, а дополнительные переменные принимают свои значения в соответствии с ограничениями задачи. Эти значения переменных отвечают такому “плану”, при котором ничего не производится, сырье не используется и значение целевой функции равно нулю (т. е. стоимость произведенной продукции отсутствует). Этот план, конечно, не является оптимальным.
Это видно и из 4-й строки табл. 6, так как в ней имеется три отрицательных числа: и Отрицательные числа не только свидетельствуют о возможности увеличения общей стоимости производимой продукции, но и показывают, на сколько увеличится эта сумма при введении в план единицы того или другого вида продукции.
Поскольку максимальное по абсолютной величине отрицательное число стоит в 4-й строке столбца вектора Р3, то в базис введем вектор Р3. определяем вектор, подлежащий исключению из базиса. Для этого находим
Найдя число мы тем самым с экономической точки зрения определили, какое количество изделий С предприятие может изготовлять с учетом норм расхода и имеющихся объемов сырья каждого вида. Так как сырья данного вида соответственно имеется 360, 192 и 180 кг, а на одно изделие С требуется затратить сырья каждого вида соответственно 12, 8 и 3 кг, то максимальное число изделий С, которое может быть изготовлено предприятием, равнот. е. ограничивающим фактором для производства изделий С является имеющийся объем сырья II вида. С учетом его наличия предприятие может изготовить 24 изделия С. При этом сырье II вида будет полностью использовано.
Следовательно, вектор Р5 подлежит исключению из базиса. Столбец вектора Р3 и 2-я строка являются направляющими. Составляем таблицу для II итерации (табл. 7).
Таблица 7
|
i |
Базис |
Сб |
Р0 |
9 |
10 |
16 |
0 |
0 |
0 |
|
|
|
|
P1 |
P2 |
P3 |
p4 |
p5 |
Р6 |
|
|
1 2 3 4 |
P4 p3 p6 |
0 16 0 |
72 24 108 384 |
9 3/4 11/4 3 |
9 1/2 3/2 -2 |
0 1 0 0 |
1 0 0 0 |
-3/2 1/8 -3/8 2 |
0 0 1 0 |
Сначала заполняем строку вектора, вновь введенного в базис, т. е. строку, номер которой совпадает с номером направляющей строки. Здесь направляющей является 2-я строка. Элементы этой строки табл. 7 получаются из соответствующих элементов таблицы 6 делением их на разрешающий элемент (т. е. на 8). При этом в столбце Сб записываем коэффициент , стоящий в столбце вводимого в базис вектора . Затем заполняем элементы столбцов для векторов, входящих в новый базис. В этих столбцах на пересечении строк и столбцов одноименных векторов проставляем единицы, а все остальные элементы полагаем равными нулю.
Для определения остальных элементов табл. 7 применяем правило треугольника. Эти элементы могут быть вычислены и непосредственно по рекуррентным формулам.
Вычислим элементы табл. 7, стоящие в столбце вектора Р0. Первый из них находится в 1-й строке этого столбца. Для его вычисления находим три числа:
1) число, стоящее в табл. 6 на пересечении столбца вектора Р0 и 1-й строки (360);
2) число, стоящее в табл. 6 на пересечении столбца вектора P3 и 1-й строки (12);
3) число, стоящее в табл. 7 на пересечении столбца вектора Р0 и 2-й строки (24).
Вычитая из первого числа произведение двух других, находим искомый элемент: 360 – 12 х 24=72; записываем его в 1-й строке столбца вектора Р0 табл. 7.
Второй элемент столбца вектора Р0 табл. 7 был уже вычислен ранее. Для вычисления третьего элемента столбца вектора Р0 также находим три числа. Первое из них (180) находится на пересечении 3-й строки и столбца вектора Р0 табл. 6, второе (3) – на пересечении 3-й строки и столбца вектора P3 табл. 6, третье (24) – на пересечении 2-й строки и столбца вектора Р0 табл. 8. Итак, указанный элемент есть 180 – 24 х 3=108. Число 108 записываем в 3-й строке столбца вектора Р0 табл. 7.
Значение F0 в 4-й строке столбца этого же вектора можно найти двумя способами:
1) по формуле , т.е.
2) по правилу треугольника; в данном случае треугольник образован числами 0, -16, 24. Этот способ приводит к тому же результату: 0 - (-16) х 24=384.
При определении по правилу треугольника элементов столбца вектора Р0 третье число, стоящее в нижней вершине треугольника, все время оставалось неизменным и менялись лишь первые два числа. Учтем это при нахождении элементов столбца вектора P1 табл. 7. Для вычисления указанных элементов первые два числа берем из столбцов векторов P1 и Р3 табл. 6, а третье число – из табл. 7. Это число стоит на пересечении 2-й строки и столбца вектора P1последней таблицы. В результате получаем значения искомых элементов: 18 – 12 х (3/4) =9; 5 – 3 х (3/4) = 11/4.
Число в 4-й строке столбца вектора P1 т абл. 7 можно найти двумя способами:
1) по формуле Z1-С1=(C,P1)-C1 имеем
2) по правилу треугольника получим
Аналогично находим элементы столбца вектора P2.
Элементы столбца вектора Р5 вычисляем по правилу треугольника. Однако построенные для определения этих элементов треугольники выглядят иначе.
При вычислении элемента 1-й строки указанного столбца получается треугольник, образованный числами 0,12 и 1/8. Следовательно, искомый элемент равен 0 – 12 х (1/8) = -3/2. Элемент, стоящий в 3-й строке данного столбца, равен 0 - 3 х (1 /8) = -3/8.
По окончании расчета всех элементов табл. 7 в ней получены новый опорный план и коэффициенты разложения векторов через базисные векторы P4, P3, P6 и значения и . Как видно из этой таблицы, новым опорным планом задачи является план X=(0; 0; 24; 72; 0; 108). При данном плане производства изготовляется 24 изделия С и остается неиспользованным 72 кг сырья 1 вида и 108 кг сырья III вида. Стоимость всей производимой при этом плане продукции равна 384 руб. Указанные числа записаны в столбце вектора Р0 табл. 7. Как видно, данные этого столбца по-прежнему представляют собой параметры рассматриваемой задачи, хотя они претерпели значительные изменения. Изменились данные и других столбцов, а их экономическое содержание стало более сложным. Так, например, возьмем данные столбца вектора Р2. Число 1/2 во 2-й строке этого столбца показывает, на сколько следует уменьшить изготовление изделий С, если запланировать выпуск одного изделия В. Числа 9 и 3/2 в 1-й и 3-й строках вектора P2показывают соответственно, сколько потребуется сырья I и II вида при включении в план производства одного изделия В, а число – 2 в 4-й строке показывает, что если будет запланирован выпуск одного изделия В, то это обеспечит увеличение выпуска продукции в стоимостном выражении на 2 руб. Иными словами, если включить в план производства продукции одно изделие В, то это потребует уменьшения выпуска изделия С на 1/2 ед. и потребует дополнительных затрат 9 кг сырья I вида и 3/2 кг сырья III вида, а общая стоимость изготовляемой продукции в соответствии с новым оптимальным планом возрастет на 2 руб. Таким образом, числа 9 и 3/2 выступают как бы новыми “нормами” затрат сырья I и III вида на изготовление одного изделия В (как видно из табл. 6, ранее они были равны 15 и 3), что объясняется уменьшением выпуска изделий С.
Такой же экономический смысл имеют и данные столбца вектора Р1 табл. 7. Несколько иное экономическое содержание имеют числа, записанные в столбце вектора Р5. Число 1/8 во 2-й строке этого столбца, показывает, что увеличение объемов сырья II вида на 1 кг позволило бы увеличить выпуск изделий С на 1/8 ед. Одновременно потребовалось бы дополнительно 3/2 кг сырья I вида и 3/8 кг сырья III вида. Увеличение выпуска изделий С на 1/8 ед. приведет к росту выпуска продукции на 2 руб.
Из изложенного выше экономического содержания данных табл. 7 следует, что найденный на II итерации план задачи не является оптимальным. Это видно и из 4-й строки табл. 7, поскольку в столбце вектора P2 этой строки стоит отрицательное число – 2. Значит, в базис следует ввести вектор P2, т. е. в новом плане следует предусмотреть выпуск изделий В. При определении возможного числа изготовления изделий В следует учитывать имеющееся количество сырья каждого вида, а именно: возможный выпуск изделий В определяется для , т. е. находим
Следовательно, исключению из базиса подлежит вектор Р4 иными словами, выпуск изделий В ограничен имеющимся в распоряжении предприятия сырьем I вида. С учетом имеющихся объемов этого сырья предприятию следует изготовить 8 изделий В. Число 9 является разрешающим элементом, а столбец вектора P2 и 1-я строка табл. 7 являются направляющими. Составляем таблицу для III итерации (табл. 8).
Таблица 8
|
i |
Базис |
Сб |
P0 |
9 |
10 |
16 |
0 |
0 |
0 |
|
|
|
|
P1 |
P2 |
P3 |
p4 |
p5 |
Р6 |
|
|
1 2 3 4 |
P2 P3 Р6 |
10 16 0 |
8 20 96 400 |
1 1/4 5/4 5 |
1 0 0 0 |
0 1 0 0 |
1/9 -1/18 -1/6 2/9 |
-1/6 5/24 -1/8 5/3 |
0 0 1 0 |
В табл. 8 сначала заполняем элементы 1-й строки, которая представляет собой строку вновь вводимого в базис вектора Р2. Элементы этой строки получаем из элементов 1-й строки табл. 7 делением последних на разрешающий элемент (т.е. на 9). При этом в столбце Сб данной строки записываем .
Затем заполняем элементы столбцов векторов базиса и по правилу треугольника вычисляем элементы остальных столбцов. В результате в табл. 8 получаем новый опорный план X=(0; 8; 20; 0; 0; 96) и коэффициенты разложения векторов через базисные векторы и соответствующие значения и
Проверяем, является ли данный опорный план оптимальным или нет. Для этого рассмотрим 4-ю строку, табл. 8. В этой строке среди чисел нет отрицательных. Это означает, что найденный опорный план является оптимальным и
Следовательно, план выпуска продукции, включающий изготовление 8 изделий В и 20 изделий С, является оптимальным. При данном плане выпуска изделий полностью используется сырье I и II видов и остается неиспользованным 96 кг сырья III вида, а стоимость производимой продукции равна 400 руб.
Оптимальным планом производства продукции не предусматривается изготовление изделий А. Введение в план выпуска продукции изделий вида А привело бы к уменьшению указанной общей стоимости. Это видно из 4-й строки столбца вектора P1, где число 5 показывает, что при данном плане включение в него выпуска единицы изделия А приводит лишь к уменьшению общей величины стоимости на 5 руб.
Решение данного примера симплексным методом можно было бы проводить, используя лишь одну таблицу (табл. 9). В этой таблице последовательно записаны одна за другой все три итерации вычислительного процесса.
Таблица 9
|
i |
Базис |
Сб |
Р0 |
9 |
10 |
16 |
0 |
0 |
0 |
|
|
|
|
|
P1 |
P2 |
P3 |
p4 |
p5 |
Р6 |
|
1 2 3 4 1 2 3 4 1 2 3 4 |
P4 р5 p6 P4 p3 p6 P2 p3 p6 |
0 0 0 0 16 0 0 16 0 |
360 192 180 0 72 24 108 384 8 20 96 400 |
18 6 5 -9 9 3/4 11/4 3 1 1/4 5/4 5 |
15 4 3 -10 9 1/2 3/2 -2 1 0 0 0 |
12 8 3 -16 0 1 0 0 0 1 0 0 |
1 0 0 0 1 0 0 0 1/9 -1/18 -1/6 2/9 |
0 1 0 0 -3/2 1/8 -3/8 2 -1/6 5/24 -1/8 5/3 |
0 0 1 0 0 0 1 0 0 0 1 0 |
Пример 10.
Найти максимум функции при условиях
Решение. Систему уравнений задачи запишем в векторной форме:
где
Так как среди векторов имеется три единичных вектора, то для данной задачи можно непосредственно найти опорный план. Таковым является план Х=(0, 0, 20, 24; 0; 18). Составляем симплексную таблицу (табл. 10) и проверяем, является ли данный опорный план оптимальным.
Таблица 10
|
i |
Базис |
Сб |
Р0 |
2 |
-6 |
0 |
0 |
5 |
0 |
|
|
|
|
|
P1 |
P2 |
P3 |
p4 |
p5 |
Р6 |
|
1 2 3 4 |
p3 P4 p6 |
0 0 0 |
20 24 18 0 |
-2 -1 3 -2 |
1 -2 -1 6 |
1 0 0 0 |
0 1 0 0 |
1 3 -12 -5 |
0 0 1 0 |
Как видно из табл. 10, исходный опорный план не является оптимальным. Поэтому переходим к новому опорному плану. Это можно сделать, так как в столбцах векторов P1 и p5, 4-я строка которых содержит отрицательные числа, имеются положительные элементы. Для перехода к новому опорному плану введем в базис вектор p5 и исключим из базиса вектор p4. Составляем таблицу II итерации.
Таблица 11
|
i |
Базис |
Сб |
Р0 |
2 |
-6 |
0 |
0 |
5 |
0 |
|
|
|
|
|
P1 |
P2 |
P3 |
p4 |
p5 |
Р6 |
|
1 2 3 |
p3 P5 p6 |
0 5 0 |
12 8 114 40 |
-5/3 -1/3 -1 -11/3 |
5/3 -2/3 -9 8/3 |
1 0 0 0 |
-1/3 1/3 4 5/3 |
0 1 0 0 |
0 0 1 0 |
Как видно из табл. 11, новый опорный план задачи не является оптимальным, так как в 4-й строке столбца вектора P1стоит отрицательное число -11/3. Поскольку в столбце этого вектора нет положительных элементов, данная задача не имеет оптимального плана.
Тема 2.3. Двойственный симплекс-метод.
Двойственный симплекс-метод, как и симплекс-метод, используется при нахождении решения задачи линейного программирования, записанной в форме основной задачи, для которой среди векторов , составленных из коэффициентов при неизвестных в системе уравнений, имеется m единичных. Вместе с тем двойственный симплекс–метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными). Такую задачу и рассмотрим теперь, предварительно предположив, что единичными являются векторы т. е. рассмотрим задачу, состоящую в определении максимального значения функции
(54)
при условиях
(55)
(56)
где
и среди чисел имеются отрицательные.
В данном случае есть решение системы линейных уравнений (55). Однако это решение не является планом задачи (54) – (56), так как среди его компонент имеются отрицательные числа.
Поскольку векторы – единичные, каждый из векторов можно представить в виде линейной комбинации данных векторов, причем коэффициентами разложения векторов по векторам служат числаТаким образом, можно найти
Определение 14. Решение системы линейных уравнений (55), определяемое базисом , называется псевдопланом задачи (54) – (56), если для любого
Теорема 11. Если в псевдоплане , определяемом базисом , есть хотя бы одно отрицательное число такое, что все , то задача (54) – (56) вообще не имеет планов.
Теорема 12. Если в псевдоплане , определяемом базисом , имеются отрицательные числа такие, что для любого из них существуют числа aij<0, то можно перейти к новому псевдоплану, при котором значение целевой функции задачи (54) – (56) не уменьшится.
Сформулированные теоремы дают основание для построения алгоритма двойственного симплекс-метода.
Пусть – псевдоплан этой задачи. На основе исходных данных составляют симплекс-таблицу (табл. 15), в которой некоторые элементы столбца вектора являются отрицательными числами. Если таких чисел нет, то в симплекс-таблице записан оптимальный план задачи (54) – (56), поскольку, по предположению, все . Поэтому для определения оптимального плана задачи при условии, что он существует, следует произвести упорядоченный переход от одной симплекс–таблицы к другой до тех пор, пока из столбца вектора не будут исключены отрицательные элементы. При этом все время должны оставаться неотрицательными все элементы (т +1)–й строки, т.е. для любого
Таким образом, после составления симплекс-таблицы проверяют, имеются ли в столбце вектора отрицательные числа. Если их нет, то найден оптимальный план исходной задачи. Если же они имеются (что мы и предполагаем), то выбирают наибольшее по абсолютной величине отрицательное число. В том случае, когда таких чисел несколько, берут какое–нибудь одно из них: пусть это число bl. Выбор этого числа определяет вектор, исключаемый из базиса, т. е. в данном случае из базиса выводится вектор Pl. Чтобы определить, какой вектор следует ввести в базис, находим , где
Пусть это минимальное значение принимается при , тогда в базис вводят вектор Рr. Число является разрешающим элементов. Переход к новой симплекс–таблице производят по обычным правилам симплексного метода. Итерационный процесс продолжают до тех пор, пока в столбце вектора Р0 не будет больше отрицательных чисел. При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i–й строке симплекс–таблицы (табл. 15) в столбце вектора Р0 стоит отрицательное число bi, а среди остальных элементов этой строки нет отрицательных, то исходная задача не имеет решения.
Таким образом, отыскание решения задачи (54) – (56) двойственным симплекс-методом включает следующие этапы:
1. Находят псевдоплан задачи.
2. Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану.
3. Выбирают разрешающую строку с помощью определения наибольшего по абсолютной величине отрицательного числа столбца вектора Р0 и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+1)–и строки к соответствующим отрицательным элементам разрешающей строки.
4. Находят новый псевдоплан и повторяют все действия начиная с этапа 2.
Таблица 15
Пример 17.
Найти максимальное значение функции при условиях
Решение. Запишем исходную задачу линейного программирования в форме основной задачи: найти максимум функции при условиях
Умножим второе и третье уравнения системы ограничений последней задачи на –1 и перейдем к следующей задаче: найти максимум функции
(57)
при условиях
(58)
(59)
Составим для последней задачи двойственную задачу. Такой является задача, в результате решения которой требуется найти минимальное значение функции
(60)
при условиях
(61)
(62)
Выбрав в качестве базиса векторы и , составим симплексную таблицу (табл. 16) для исходной задачи (57) – (59).
Таблица 16
|
i |
Базис |
Сб |
Р0 |
1 |
1 |
2 |
0 |
0 |
|
|
|
|
|
P1 |
P2 |
P3 |
p4 |
p5 |
|
1 2 3 4 |
p3 P4 p5 |
2 0 0 |
8 –4 –6 16 |
1 –1 –1 1 |
1 1 –2 1 |
1 0 0 0 |
0 1 0 0 |
0 0 1 0 |
Из этой таблицы видим, что планом двойственной задачи (57) – (59) является . При этом плане Так как в столбце вектора Р0 таблица 16 имеются два отрицательных числа (–4 и –6), а в 4–й строке отрицательных чисел нет, то в соответствии с алгоритмом двойственного симплекс–метода переходим к новой симплекс–таблице. (В данном случае это можно сделать, так как в строках векторов Р4 и Р5 имеются отрицательные числа. Если бы они отсутствовали, то задача была бы неразрешима. Вектор, исключаемый из базиса, определяется наибольшим по абсолютной величине отрицательным числом, стоящим в столбце вектора Р0. В данном случае это число –6. Следовательно, из базиса исключаем вектор Р5. Чтобы определить, какой вектор необходимо ввести в базис, находимгде Имеем
Значит, в базис вводим вектор P2. Переходим к новой симплекс–таблице (табл. 17).
Таблица 17
|
i |
Базис |
Сб |
Р0 |
1 |
1 |
2 |
0 |
0 |
|
|
|
|
|
P1 |
P2 |
P3 |
p4 |
p5 |
|
1 2 3 4 |
p3 P4 p2 |
2 0 1 |
5 –7 3 13 |
1/2 –3/2 1/2 1/2 |
0 0 1 0 |
1 0 0 0 |
0 1 0 0 |
1/2 1/2 –1/2 1/2 |
Из этой таблицы видно, что получен новый план двойственной задачи При этом плане значение ее линейной формы равно Таким образом, с помощью алгоритма двойственного симплекс–метода произведен упорядоченный переход от одного плана двойственной задачи к другому.
Так как в столбце вектора Р0 таблицы 17 стоит отрицательное число –7, то рассмотрим элементы 2–й строки. Среди этих чисел есть одно отрицательное –3/2. Если бы такое число отсутствовало, то исходная задача была бы неразрешима. В данном случае переходим к новой симплекс-таблице (табл. 18).
Таблица 18
|
i |
Базис |
Сб |
Р0 |
1 |
1 |
2 |
0 |
0 |
|
|
|
|
|
P1 |
P2 |
P3 |
p4 |
p5 |
|
1 2 3 4 |
p3 P1 p2 |
2 1 1 |
8/3 14/3 2/3 32/3 |
0 1 0 0 |
0 0 1 0 |
1 0 0 0 |
1/3 –2/3 1/3 1/3 |
2/3 –1/3 –1/3 2/3 |
Как видно из таблицы 18, найдены оптимальные планы исходной и двойственной задач. Ими являются и .
При этих планах значения линейных форм исходной и двойственной задач равны между собой:
Пример 18.
Найти максимальное значение функции при условиях
Решение. Умножая первое и третье уравнения системы ограничений задачи на –1, в результате приходим к задаче нахождения максимального значения функции при условиях
Взяв в качестве базиса векторы Р3, Р4 и Р5, составляем симплекс-таблицу (табл. 19).
Таблица 19
|
i |
Базис |
Сб |
Р0 |
2 |
3 |
0 |
5 |
0 |
|
|
|
|
|
P1 |
P2 |
P3 |
p4 |
p5 |
|
1 2 3 4 |
p3 P4 p5 |
0 5 0 |
–12 10 –18 50 |
2 1 –3 3 |
–1 2 2 7 |
1 0 0 0 |
0 1 0 0 |
0 0 1 0 |
В 4-й строке таблице 19 нет отрицательных чисел. Следовательно, если бы в столбце вектора Р0 не было отрицательных чисел, то в таблице 19 был бы записан оптимальный план. Поскольку в указанном столбце отрицательные числа имеются и такие же числа содержатся в соответствующих строках, переходим к новой симплекс–таблице (таблица 20). Для этого исключим из базиса вектор Р5 и введем в базис вектор Р1. В результате получим псевдоплан X=(6;0;-24;4)
Таблица 20
|
i |
Базис |
Сб |
Р0 |
2 |
3 |
0 |
5 |
0 |
|
|
|
|
|
P1 |
P2 |
P3 |
p4 |
p5 |
|
1 2 3 4 |
p3 P4 p1 |
0 5 2 |
–24 4 6 32 |
0 0 1 0 |
1/3 8/3 –2/3 9 |
1 0 0 0 |
0 1 0 0 |
2/3 1/3 –1/3 1 |
Так как в строке вектора Р3 нет отрицательных чисел, то исходная задача не имеет решения.