ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.02.2026
Просмотров: 808
Скачиваний: 2
переменную x3 переводим в свободные, а свободную переменную x1 - в базисные.
В результате преобразования симплекс-таблицы получили следующую таблицу:
Базисные |
Свободные |
|
|
|
Свободные |
|
|
|
|
|
||||||||||||
|
|
|
переменные |
|
||||||||||||||||||
переменные |
члены |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
x3 |
|
|
|
|
x5 |
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
4 |
10 |
|
|
− |
|
|
4 |
|
|
|
|
|
− |
|
1 |
|
|
||||
|
|
|
|
|
11 |
|
|
|
|
11 |
|
|||||||||||
|
11 |
|
|
|
|
|
|
|
|
|
||||||||||||
x4 |
23 |
|
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
x2 |
5 |
8 |
|
|
− |
|
|
1 |
|
|
|
|
|
− |
|
3 |
|
|
||||
|
|
|
|
11 |
|
|
|
|
11 |
|
||||||||||||
|
11 |
|
|
|
|
|
|
|
|
|
||||||||||||
Z |
35 |
2 |
|
|
− 2 |
3 |
|
|
|
|
− |
|
9 |
|
|
|||||||
|
|
|
11 |
|
|
|
|
11 |
|
|||||||||||||
|
11 |
|
|
|
|
|
|
|
|
|
||||||||||||
Базисное |
решение |
X = (4 |
10 |
; 5 |
|
8 |
; 0; 23; 0) |
- |
||||||||||||||
11 |
11 |
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
допустимое, т.к. все свободные члены положительные. Решение оптимальное (минимум целевой функции), поскольку в строке целевой функции, кроме столбца свободных членов, все элементы одного знака (отрицательные). Оптимальное решение единственное, т.к. в строке целевой функции нет нулевых элементов. Данная симплекс-таблица соответствует точке А на рис.6.
Но поскольку требуется найти максимальное значение целевой функции, то итерации продолжаются.
В качестве разрешающего столбца можно выбрать любой столбец таблицы, т.к. они оба не удовлетворяют признаку оптимальности (максимуму). Выбираем столбец x3 .
Тогда разрешающей строкой будет строка x4 , т.к. min{231 } = 23 .
В результате преобразований получим следующую симплекс-таблицу:
31
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
Таб.3. Симплекс-таблица оптимального решения |
|
|
|
|
|
|
||||||||||||||||||
Базисные |
Свободные |
|
|
|
Свободные |
|
||||||||||||||||||
|
|
|
переменные |
|
||||||||||||||||||||
переменные |
члены |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
x4 |
|
|
|
|
x5 |
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
13 |
|
3 |
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
||
11 |
|
11 |
|
|
|
|
|
11 |
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
x3 |
23 |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
x2 |
7 |
9 |
|
|
|
|
1 |
|
|
|
|
|
|
|
− |
|
2 |
|
|
|
||||
|
|
|
|
11 |
|
|
|
|
|
11 |
|
|||||||||||||
|
11 |
|
|
|
|
|
|
|
|
|
||||||||||||||
Z |
87 |
|
5 |
|
2 |
|
3 |
|
|
|
|
|
1 |
5 |
|
|
|
|||||||
11 |
11 |
|
|
|
|
11 |
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
Базисное |
решение |
X = (13 |
3 |
; 7 |
|
9 |
; 23; 0; 0) |
- |
||||||||||||||||
|
11 |
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
11 |
|
|
|
|
|
|
|
|
|
|||||||
допустимое, т.к. все свободные члены положительные. Решение оптимальное (максимум целевой функции), поскольку в строке целевой функции все элементы одного знака (положительные). Оптимальное решение единственное, т.к. в строке целевой функции нет нулевых элементов. Данная симплекс-таблица соответствует точке С на рис.6.
Таким образом, наибольшее |
значение Z max |
= 87 |
|
5 |
|||||
11 |
|||||||||
|
3 |
|
|
9 |
|
|
|||
целевая функция имеет при X* = (13 |
; 7 |
; 23; 0; 0) . |
|
|
|
||||
11 |
11 |
|
|
|
|||||
|
|
|
|
|
|
||||
6. Двойственные задачи линейного программирования
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу,
называемую двойственной или сопряженной по отношению к исходной или прямой.
32
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
1. С и м м ет р и ч н а я |
п а р а |
в з а и м н о |
|||||
д в о й с т в ен н ы х з а д а ч : |
|
|
|||||
Рассматривается |
стандартная задача |
линейного |
|||||
программирования (СЗЛП): |
|
|
|||||
ì |
|
n |
x j ® max |
|
|
||
ïZ |
= å c j |
|
|
||||
ï |
|
j=1 |
|
|
|
|
|
ï n |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
СЗЛП : í å aij x j £ bi , i = 1, m |
|
|
|||||
ï j=1 |
|
|
|
|
|
||
ïx |
j |
³ 0 |
|
|
|
|
|
ï |
|
|
|
|
|
|
|
ï |
|
|
|
|
|
|
|
î |
|
|
|
|
|
|
|
Тогда двойственная ей задача (ДЗЛП) будет иметь вид:
|
m |
|
® min |
|
|
|
|||
ìF = å b y |
i |
|
|
|
|||||
ï |
i |
|
|
|
|
|
|
|
|
ï |
i=1 |
|
|
|
|
|
|
|
|
ï m |
|
|
|
|
|
|
|
|
|
ДЗЛП : íå aij yi ³ c j , j = 1, n |
|
|
|
||||||
ïi=1 |
|
|
|
|
|
|
|
|
|
ï |
|
|
|
|
|
|
|
|
|
³ 0, i = 1, m |
|
|
|
||||||
ïyi |
|
|
|
||||||
î |
|
|
|
|
|
|
|
|
|
Э к о н о м и ч е с к а я и н т е р п р е т а ц и я в з а и м н о |
|||||||||
д в о й с т в ен н ы х з а д а ч . |
|
|
|
||||||
СЗЛП: |
Составить |
такой |
план |
продукции |
|||||
X = {x1, x2,..., xn}, |
при |
|
котором выручка |
(прибыль) от |
|||||
реализации продукции будет максимальной при условии, что
потребление ресурсов по каждому виду продукции не превзойдет имеющиеся запасы.
ДЗЛП: Найти такой набор цен (оценок) ресурсов Y = {y1, y2,..., ym}, при которых общие затраты на ресурсы будут
минимальными, а созданная стоимость единицы продукции
каждого вида будет не менее выручки от реализации единицы продукции. Оценки Y = {y1, y2,..., ym} называются учетными или
теневыми.
Положительную двойственную оценку имеют лишь те виды ресурсов, которые полностью используются при
оптимальном плане производства продукции и увеличить этот
33
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
доход можно только при увеличении этих ресурсов. Поэтому
двойственные оценки определяют дефицитность используемых ресурсов: в оптимальном плане дефицитные ресурсы получают ненулевые оценки, а недефицитные - нулевые.
2. Н е с и м м е т р и ч н а я |
п а р а |
в з а и м н о |
|||||||||
д в о й с т в ен н ы х з а д а ч . |
|
|
|||||||||
Рассматривается |
|
|
каноническая задача |
линейного |
|||||||
программирования (КЗЛП): |
|
|
|||||||||
ì |
n |
|
|
® max |
|
|
|||||
ïZ = å c j x j |
|
|
|||||||||
ï |
j=1 |
|
|
|
|
|
|
|
|
|
|
ï |
n |
|
|
|
|
|
|
|
|
|
|
|
|
, i = 1, m |
|
|
|||||||
КЗЛП : í |
å aij x j = bi |
|
|
||||||||
ï j=1 |
|
|
|
|
|
|
|
|
|
|
|
ï |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ïx j ³ 0, j = 1, n |
|
|
|||||||||
ï |
|
|
|
|
|
|
|
|
|
|
|
î |
|
|
|
|
|
|
|
|
|
|
|
Двойственная задача имеет вид: |
|
|
|||||||||
|
m |
|
® min |
|
|
||||||
ìF = å b y |
i |
|
|
||||||||
ï |
i |
|
|
|
|
|
|
|
|
|
|
ï |
i=1 |
|
|
|
|
|
|
|
|
|
|
ДЗЛП : í |
|
|
|
|
|
|
|
|
|
|
|
ï m |
|
|
|
|
|
|
|
|
|
|
|
|
|
, j =1, m |
|
|
|||||||
ï |
å aij yi ³ c j |
|
|
||||||||
îi=1 |
|
|
|
|
|
|
|
|
|
|
|
3. О б щ а я |
|
|
|
|
|
п о с т а н о в к а |
|||
в з а и м о д в о й с т в е н н ы х з а д а ч . |
|
|
|||||||
Рассматривается |
общая |
задача |
линейного |
||||||
программирования (ОЗЛП): |
|
|
|||||||
ì |
|
= |
|
n |
|
|
® max |
|
|
ïZ |
å c j x j |
|
|
||||||
ï |
|
|
j=1 |
|
|
|
|
||
ï n |
|
|
x |
|
= b , i Î I, I Í M = {1...m} |
|
|||
ï å a |
|
|
|
||||||
ОЗЛП : í j=1 |
ij |
|
j |
i |
|
|
|
||
ï n |
|
|
|
|
|
|
|
|
|
ï å aij x j £ bi |
, i Î M \ I |
|
|
||||||
ï j=1 |
|
|
|
|
|
|
|
||
ï |
|
³ 0, j Î J |
Í N = {1...n} |
|
|
||||
ïx |
j |
|
|
||||||
î |
|
|
|
|
|
|
|
|
|
Двойственная задача:
34
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
|
m |
|
® min |
ìF = å b y |
i |
||
ï |
i |
|
|
ï |
i=1 |
|
|
ï m |
|
|
|
ï |
å aij yi = c j , j Î N \ J |
||
ДЗЛП : íi=1 |
|
|
|
ï m |
|
|
|
ï |
å aij yi ³ c j , j Î J |
||
ïi=1 |
|
|
|
ïîyi ³ 0, i Î M \ I
Замечание: Неотрицательная переменная одной задачи соответствует ограничению-неравенству другой задачи, и наоборот, ограничение-неравенство одной задачи соответствует неотрицательной переменной другой задачи.
Двойственная задача по отношению к исходной составляется согласно следующим правилам:
1.Одна задача является задачей максимизации с ограничениями £ , другая является задачей минимизации с ограничениями ³ .
2.Каждому ограничению одной задачи соответствует переменная другой задачи. Номер переменной совпадает с номером ограничения.
3.Ограничению, записанному в виде неравенства,
соответствует переменная двойственной задачи с условием неотрицательности.
4.Матрица условий одной задачи получается транспонированием матрицы условий другой задачи:
|
|
æ a |
a |
... |
a |
ö |
|
||
|
|
ç 11 |
|
12 |
|
|
1n |
÷ |
|
для исходной задачи |
A = |
ç a21 |
a22 |
... |
a2n ÷ |
, |
|||
ç ... |
|
... |
... ... |
÷ |
|||||
|
|
ç |
am2 |
... |
|
|
÷ |
|
|
|
|
èam1 |
amn ø |
|
|||||
|
|
æ a |
a |
|
... |
a |
|
ö |
|
для двойственной задачи |
A = |
ça11 |
a |
21 |
... |
am1 |
÷ |
|
|
ç ... |
... |
... ... |
÷ . |
||||||
|
|
ç 12 |
|
22 |
|
m2 |
÷ |
|
|
|
|
ça |
a |
2n |
... |
a |
mn |
÷ |
|
|
|
è 1n |
|
|
|
ø |
|
||
5. Коэффициенты целевой функции одной задачи
соответствуют свободным членам системы ограничений другой задачи.
35
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com