Курс лекци Русакова по методам оптимизации (1083216), страница 6
Текст из файла (страница 6)
Следовательно, план выпуска продукции,включающий изготовление 8 изделий B и 20 изделий C , являетсяоптимальным. При данном плане выпуска изделий полностью используетсясырьё I и II вида и остаётся неиспользованным 96 кг сырья III вида, астоимость производимой продукции равна 400 руб.Оптимальным планом производства продукции не предусматриваетсяизготовление изделий A . Введение в план выпуска продукции изделий видаA привело бы к уменьшению указанной общей стоимости. Это видно из 4-йстроки столбца P1 где число 5 показывает, что при данном плане включениев него выпуска единицы изделия A приводит лишь к уменьшению общейстоимости на 5 руб.Пример реализации данного алгоритма в MATLAB.function out = simplex(d)% Программа реализующая симплекс метод.% d - матрица данных в стандартной форме% a11x1+a12x2+a13x3<=C1% a21x1+a22x2+a23x3<=C2% a31x1+a32x2+a33x3<=C3%Найти max f(x)% f(x)=z1x1+z2x2+z3x348%d=[a11,a12,a13,c1;%a21,a22,a23,c2;%a31,a32,a33,c3;%z1 ,z2 ,z3 ,0;]clc;d=[18,15,12,360;6 , 4, 8,192;5 , 3, 3,180;9 ,10, 16, 0;]%Преобразуем данные в симплес таблицу.m=[0,0,0,d(4,1),d(4,2),d(4,3),0,0,0;4,0,d(1,4),d(1,1),d(1,2),d(1,3),1,0,0;5,0,d(2,4),d(2,1),d(2,2),d(2,3),0,1,0;6,0,d(3,4),d(3,1),d(3,2),d(3,3),0,0,1;0,0,0,(-1)*d(4,1),(-1)*d(4,2),(-1)*d(4,3),0,0,0;];while m(1,1)==0mm=iter_simp(m);endmfunction m_out = iter_simp(m)mold=m;%Поиск вектора (v), который будем вводить в базис.%Это должен быть максимальный элемент%по абсолютному значению, из%отрицательных чисел последней строки.max=0;v=0;for i=1:6x=m(5,3+i);if x<0x=abs(x);if x>maxmax=x;v=i;endendend%Определяем вектор подлежащий исключению из базиса (vi)vi=2;min=m(2,3)/m(2,3+v);for i=2:4x=m(i,3)/m(i,3+v);if min>xvi=i;min=x;endend%Разрешающий элементraz=m(vi,v+3);%Сначала заполняем строку вектора вновь введённого в базисfor i=3:9m(vi,i)=m(vi,i)/raz;end%Меняем вектор в первом столбцеm(vi,1)=v;%Записываем ценуm(vi,2)=m(1,v+3);49%Вычисляем остальные числаfor i=2:5if i~=vifor j=3:9x1=mold(i,j);x2=mold(i,v+3);x3=m(vi,j);m(i,j)=x1-x2*x3;endendend%Критерий оптимальностиm(1,1)=1;for i=4:9if m(5,i)<0m(1,1)=0;endendm_out=m;Недостатки симплекс метода.Рассмотренный простейший симплекс-метод склонен к зацикливаниюи медленно сходится, если длина ребра симплекса выбрана малой (выборже большой длины ребра симплекса обеспечивает высокую скоростьсходимости, но дает малую точность решения).
Поэтому в вычислительнойпрактике используются различные модификации простейшего метода,направленные на преодоление его указанных недостатков.1.09 Двойственныезадачилинейногопрограм-мированияКаждой задаче линейного программирования можно определеннымобразомсопоставитьнекоторуюдругуюзадачу(линейногопрограммирования), называемую двойственной или сопряженной поотношению к исходной или прямой задаче. Дадим определение двойственнойзадачи по отношению к общей задаче линейного программирования,50состоящей, как мы уже знаем, в нахождении максимального значенияфункции(д1)при условиях(д2)(д3)ОпределениеЗадача, состоящая в нахождении минимального значения функции(д4)при условиях(д5)(д6)называется двойственной по отношению к задаче (д1) – (д3).
Задачи(д1) – (д3) и (д4) – (д6) образуют пару задач, называемую в линейномпрограммировании двойственной парой. Сравнивая две сформулированныезадачи, видим, что двойственная задача составляется согласно следующимправилам:1. Целевая функция исходной задачи (д1) – (д3) задается на максимум,а целевая функция двойственной (д4) – (д6) – на минимум.2. Матрица51(д7)составленнаяизкоэффициентовпринеизвестныхвсистемеограничений (д2) исходной задачи (д1) – (д3), и аналогичная матрица(д8)в двойственной задаче (д4) – (д6) получаются друг из другатранспонированием (т. е. заменой строк столбцами, а столбцов – строками).3.
Число переменных в двойственной задаче (д4) – (д6) равно числуограничений в системе (д2) исходной задачи (д1) – (д3), а число ограниченийв системе (д5) двойственной задачи – числу переменных в исходной задаче.4. Коэффициентами при неизвестных в целевой функции (д4)двойственной задачи (д4) – (д6) являются свободные члены в системе (д2)исходной задачи (д1) – (д3), а правыми частями в соотношениях системы (д5)двойственной задачи – коэффициенты при неизвестных в целевой функции(д1) исходной задачи.5.
Если переменная xj исходной задачи (д1) – (д3) может приниматьтолько лишь положительные значения, то j–е условие в системе (д5)двойственной задачи (д4) – (д6) является неравенством вида “ ≥ ”. Если жепеременная xj может принимать как положительные, так и отрицательныезначения, то 1 – соотношение в системе (д2) представляет собой уравнение.Аналогичные связи имеют место между ограничениями (д2) исходной задачи(д1) – (д3) и переменными двойственной задачи (д4) – (д6). Если i –соотношение в системе (д2) исходной задачи является неравенством, то i–япеременная52двойственнойзадачи.Впротивномслучаепеременная уj может принимать как положительные, так и отрицательныезначения.Двойственные пары задач обычно подразделяют на симметричные инесимметричные.
В симметричной паре двойственных задач ограничения(д2) прямой задачи и соотношения (д5) двойственной задачи являютсянеравенствами вида “ ”. Таким образом, переменные обеих задач могутпринимать только лишь неотрицательные значения.ПримерСоставить двойственную задачу по отношению к задаче, состоящей вмаксимизации функции(д9)при условиях(д10)(д11)Решение. Для данной задачииЧисло переменных в двойственной задаче равно числу уравнений всистеме (д10), т. е. равно трем. Коэффициентами в целевой функциидвойственной задачи являются свободные члены системы уравнений (д10),т.е. числа 12, 24, 18.Целевая функция исходной задачи (д9) – (д11) исследуется намаксимум, а система условий (д10) содержит только уравнения.
Поэтому вдвойственной задаче целевая функция исследуется на минимум, а ее53переменныемогутприниматьлюбыезначения(втомчислеиотрицательные). Так как все три переменные исходной задачи (д9) – (д11)принимают только лишь неотрицательные значения, то в системе условийдвойственнойзадачидолжныбытьтринеравенствавида“”.Следовательно, для задачи (д9) – (д11) двойственная задача такова: найтиминимум функциипри условияхПримерДля задачи, состоящей в максимизации функциипри условияхсформулировать двойственную задачу.Решение. Для данной задачи,В соответствии с общими правилами задача, двойственная поотношению к данной, формулируется следующим образом: найти минимумфункции54при условияхСвязь между решениями прямой и двойственной задач.Рассмотрим пару двойственных задач, образованную основной задачейлинейного программирования и двойственной к ней.
Исходная задача: найтимаксимум функции(д12)при условиях(д13)(д14)Двойственная задача: найти минимум функции(д15)при условиях(д16)Каждая из задач двойственной пары (д12) – (д14) и (д15), (д16)фактически является самостоятельной задачей линейного программированияи может быть решена независимо одна от другой. Однако при определениисимплексным методом оптимального плана одной из задач тем самымнаходится решение и другой задачи.Существующие зависимости между решениями прямой и двойственнойзадач характеризуются сформулированными ниже леммами и теоремамидвойственности.Лемма 1.Если Х – некоторый план исходной задачи (д12) – (д14), a Y –произвольный план двойственной задачи (д15), (д16), то значение целевой55функции исходной задачи при плане Х всегда не превосходит значенияцелевой функции двойственной задачи при плане Y, т. е.Лемма 2.ЕслидлянекоторыхX* иплановY* задач (д12)–(д14) и (д15), (д16), то X* – оптимальный план исходной задачи, а Y* –оптимальный план двойственной задачи.Теорема (первая теорема двойственности).Если одна из задач двойственной пары (д12) – (д14) или (д15),(д16) имеет оптимальный план, то и другая имеет оптимальный план изначения целевых функций задач при их оптимальных планах равны междусобой, т.
е.Еслижецелеваяпары неограничена (дляфункцияоднойисходной (д12)задачи–(д14)издвойственной– сверху,длядвойственной (д15), (д16) –снизу), то другая задача вообще не имеет планов.Теорема (вторая теорема двойственности).Планзадачи (д12)–(д14) ипланзада-чи (д15), (д16) являются оптимальными планами этих задач тогда и толькотогда, когда для любоговыполняется равенствоГеометрическая интерпретация двойственных задач.56Если число переменных в прямой и двойственной задачах, образующихданную пару, равно двум, то, используя геометрическую интерпретациюзадачи линейного программирования, можно легко найти решение даннойпары задач.
При этом имеет место один из следующих трех взаимноисключающих друг друга случаев: 1) обе задачи имеют планы; 2) планыимеет только одна задача; 3) для каждой задачи двойственной парымножество планов пусто.Пример.Для задачи, состоящей в определении максимального значенияфункциипри условияхсоставить двойственную задачу и найти решение обеих задач.Решение. Двойственной задачей по отношению к исходной являетсязадача,функциисостоящаявопределенииминимальногозначенияпри условияхКак в исходной, так и в двойственной задаче число неизвестных равнодвум. Следовательно, их решение можно найти, используя геометрическуюинтерпретацию задачи линейного программирования (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
