Содержание
Введение
1. Общая постановка задачи линейного программирования (ЛП)
2. Приведение задачи линейного программирования кстандартной форме
3. Примеры экономических задач, приводящихся к задачам ЛП
4. Геометрический метод решение задачЛП
5. Симплексный метод решения задач ЛП
6. Теоремы двойственности и ихиспользование в задачах ЛП
6. Транспортная задача и её решение методом потенциалов
Заключение
Литература
Введение
В настоящеевремя оптимизация находит применение в науке, технике и в любой другой области человеческойдеятельности.
Оптимизация- целенаправленная деятельность, заключающаясяв получении наилучших результатов при соответствующих условиях.
Поискиоптимальных решений привели к созданию специальных математических методов и ужев 18 веке были заложены математические основы оптимизации (вариационное исчисление,численные методы и др.). Однако до второй половины 20 века методы оптимизации вомногих областях науки и техники применялись очень редко, поскольку практическоеиспользование математических методов оптимизации требовало огромной вычислительнойработы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев — невозможно.
Постановказадачи оптимизации предполагает существование конкурирующих свойств процесса, например:
· количество продукции — расходсырья
· количество продукции — качествопродукции
Выбор компромиcсного вариантадля указанных свойств и представляет собой процедуру решения оптимизационной задачи.
При постановкезадачи оптимизации необходимо:
1. Наличие объекта оптимизации и цели оптимизации. При этом формулировкакаждой задачи оптимизации должна требовать экстремального значения лишь одной величины,т.е. одновременно системе не должно приписываться два и более критериев оптимизации,т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого.Приведем примеры.
Типичныйпример неправильной постановки задачи оптимизации:
«Получитьмаксимальную производительность при минимальной себестоимости».
Ошибказаключается в том, что ставится задача поиска оптимальности 2-х величин, противоречащихдруг другу по своей сути.
Правильнаяпостановка задачи могла быть следующая:
а) получить максимальную производительность при заданной себестоимости;
б) получить минимальную себестоимость при заданной производительности;
В первомслучае критерий оптимизации — производительность, а во втором — себестоимость.
2. Наличие ресурсов оптимизации, под которыми понимают возможностьвыбора значений некоторых параметров оптимизируемого объекта.
3. Возможность количественной оценки оптимизируемой величины,поскольку только в этом случае можно сравнивать эффекты от выбора тех или иных управляющихвоздействий.
4. Учет ограничений.
Обычнооптимизируемая величина связана с экономичностью работы рассматриваемого объекта(аппарат, цех, завод). Оптимизируемый вариант работы объекта должен оцениватьсякакой-то количественной мерой — критерием оптимальности.
Критериемоптимальности называется количественная оценкаоптимизируемого качества объекта.
На основаниивыбранного критерия оптимальности составляется целевая функция, представляющая собойзависимость критерия оптимальности от параметров, влияющих на ее значение. Вид критерияоптимальности или целевой функции определяется конкретной задачей оптимизации.
Таким образом,задача оптимизации сводится к нахождению экстремума целевой функции.
В зависимостиот своей постановки, любая из задач оптимизации может решаться различными методами,и наоборот — любой метод может применяться для решения многих задач. Методы оптимизациимогут быть скалярными (оптимизация проводится по одному критерию), векторными (оптимизацияпроводится по многим критериям), поисковыми (включают методы регулярного и методыслучайного поиска), аналитическими (методы дифференциального исчисления, методывариационного исчисления и др.), вычислительными (основаны на математическом программировании,которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим,эвристическим и т.д.), теоретико-вероятностными, теоретико-игровыми и др. Подвергатьсяоптимизации могут задачи как с ограничениями, так и без них.
Линейноепрограммирование — один из первых и наиболее подробно изученных разделов математическогопрограммирования. Именно линейное программирование явилось тем разделом, с которогоначала развиваться сама дисциплина «математическое программирование».Термин «программирование» в названии дисциплины ничего общего с термином«программирование (т.е. составление программ) для ЭВМ» не имеет, так какдисциплина «линейное программирование» возникла еще до того времени, когдаЭВМ стали широко применяться при решении математических, инженерных, экономическихи др. задач. Термин «линейное программирование» возник в результате неточногоперевода английского «linear programming». Одно из значений слова «programming»- составление планов, планирование. Следовательно, правильным переводом «linear programming»было бы не «линейное программирование», а «линейное планирование»,что более точно отражает содержание дисциплины. Однако, термин линейное программирование,нелинейное программирование и т.д. в нашей литературе стали общепринятыми.
Итак, линейноепрограммирование возникло после Второй Мировой Войны и стал быстро развиваться,привлекая внимание математиков, экономистов и инженеров благодаря возможности широкогопрактического применения, а так же математической «стройности».
Можно сказать,что линейное программирование применимо для построения математических моделей техпроцессов, в основу которых может быть положена гипотеза линейного представленияреального мира: экономических задач, задач управления и планирования, оптимальногоразмещения оборудования и пр.
Задачамилинейного программирования называются задачи, в которых линейны как целевая функция,так и ограничения в виде равенств и неравенств. Кратко задачу линейного программированияможно сформулировать следующим образом: найти вектор значений переменных, доставляющихэкстремум линейной целевой функции при m ограничениях в виде линейных равенств илинеравенств.
Линейноепрограммирование представляет собой наиболее часто используемый метод оптимизации.К числу задач линейного программирования можно отнести задачи:
· рационального использования сырья и материалов;задачи оптимизации раскроя;
· оптимизации производственной программы предприятий;
· оптимального размещения и концентрации производства;
· составления оптимального плана перевозок,работы транспорта;
· управления производственными запасами;
· и многие другие, принадлежащие сфере оптимальногопланирования.
Так, пооценкам американских экспертов, около 75% от общего числа применяемых оптимизационныхметодов приходится на линейное программирование. Около четверти машинного времени,затраченного в последние годы на проведение научных исследований, было отведенорешению задач линейного программирования и их многочисленных модификаций.
Первыепостановки задач линейного программирования были сформулированы известным советскимматематиком Л.В. Канторовичем, которому за эти работы была присуждена Нобелевскаяпремия по экономике.
Значительноеразвитие теория и алгоритмический аппарат линейного программирования получили сизобретением и распространением ЭВМ и формулировкой американским математиком Дж.Дансингом симплекс-метода.
В развитиеи совершенствование этих систем вложен труд и талант многих математиков, аккумулированопыт решения тысяч задач. Владение аппаратом линейного программирования необходимокаждому специалисту в области математического программирования. Линейное программированиетесно связано с другими методами математического программирования (например, нелинейногопрограммирования, где целевая функция нелинейная).
Задачис нелинейной целевой функцией и линейными ограничениями называют задачами нелинейногопрограммирования с линейными ограничениями. Оптимизационные задачи такого рода можноклассифицировать на основе структурных особенностей нелинейных целевых функций.Если целевая функция Е — квадратичная функция, то мы имеем дело с задачей квадратичногопрограммирования; если Е — это отношение линейных функций, то соответствующая задачаносит название задачи дробно-линейного программирования, и т.д. Деление оптимизационныхзадач на эти классы представляет значительный интерес, поскольку специфические особенноститех или иных задач играют важную роль при разработке методов их решения.
1. Общая постановка задачилинейного программирования (ЛП)
Задачалинейного программирования (ЛП) состоит в нахожденииминимума (или максимума) линейной функции при линейных ограничениях.
Общаяформа задачи имеет вид: найти /> приусловиях
/>
Где
/>
Здесь идалее нам удобнее считать с и аі вектор — строками, а x и b= (b1,...,bm)T — вектор столбцами.
Нарядус общей формой широко используются также каноническая и стандартнаяформы. Как в канонической, так и в стандартной форме
/>
т.е. всепеременные в любом допустимом решении задачи должны принимать неотрицательные значения(такие переменные принято называть неотрицательные в отличие от так называемыхсвободных переменных, на область значений которых подобное ограничение ненакладывается). Отличие же между этими формами состоит в том, что в одном случаеI2 = 0, а в другом — I1 = 0.
ЗадачаЛП в канонической форме:
/> (2.1)
/> (2.2)
/> (2.3)
ЗадачаЛП в стандартной форме:
/>
В обоихслучаях А есть матрица размерности m x n, i-я строка которой совпадает с векторомаi.
ЗадачаЛП в общей форме сводится (в определенном смысле) к задаче ЛП в канонической (стандартной)форме. Под этим понимается существование общего способа построения по исходной задаче(в общей форме) новой задачи ЛП (в нужной нам форме), любое оптимальное решениекоторой «легко» преобразуется в оптимальное решение исходной задачи инаоборот. (Фактически, связь между этими задачами оказывается еще более тесной).Тем самым мы получаем возможность, не теряя общности, заниматься изучением задачЛП, представленных либо в канонической, либо в стандартной форме. Ввиду этого нашидальнейшие рассмотрения задач ЛП будут посвящены, главным образом, задачам в каноническойформе. 2. Приведениезадачи линейного программирования к стандартной форме
Любая задачалинейного программирования приводится к стандартной (канонической) форме основнойзадачи линейного программирования, которая формулируется следующим образом: найтинеотрицательные значения переменных X1, X2, Xn, удовлетворяющих ограничениям в виде равенств:
A11X1 + A12X2 + … + A1nXn = B1;
A21X1 + A22X2 + … + A2nXn = B2;
……………………………………
Am1X1 + Am2X2 + … + AmnXn = Bm;
Xj ≥ 0, j=1,…,n
и обращающихв максимум линейную функцию этих переменных:
E = C1X1 + C2X2 + … + CnXn Þ max
При этомтакже требуется, чтобы правые части равенств были неотрицательны, т.е. должны соблюдатьсяусловия:
Bj ≥ 0, j=1,…,n
Приведениек стандартной форме необходимо, так как большинство методов решения задач линейногопрограммирования разработано именно для стандартной формы. Для приведения к стандартнойформе задачи линейного программирования может потребоваться выполнить следующиедействия:
перейтиот минимизации целевой функции к ее максимизации;
изменитьзнаки правых частей ограничений;
перейтиот ограничений-неравенств к равенствам;
избавитьсяот переменных, не имеющих ограничений на знак.
Для решениянашей задачи воспользуемся симплекс-методом, так как этот метод предназначен длярешения задач линейного программирования любой размерности.
3. Примеры экономическихзадач, приводящихся к задачам ЛП
Несмотряна требование линейности функций критериев и ограничений, в рамки линейного программированияпопадают многочисленные задачи распределения ресурсов, управления запасами, сетевогои календарного планирования, транспортные задачи и прочие.
Рассмотримнекоторые из них.
Определениеоптимального ассортимента. Имеются m видов ресурсов в количествах b1, b2,., bi,bm и n видов изделий. Задана матрица A=||aij||, i=1,.,m, j=1,.,n,где aij характеризует нормы расхода i-го ресурса на единицу j-го видаизделий. Эффективность производства j-го вида изделий характеризуется показателемCj, удовлетворяющим условию линейности. Нужно определить такой план выпускаизделий (оптимальный ассортимент), при котором суммарный показатель эффективностибудет наибольший.
Обозначимколичество единиц k-го вида изделий, выпускаемых предприятием, через xk,/>. Тогда математическая модель этой задачи будет иметьтакой вид:
/> (3.1)
при ограничениях
/> (3.2)
Кроме ограниченийна ресурсы (3.2) в эту модель можно ввести дополнительные ограничения на планируемыйуровень выпуска продукции />, xi:xj: xk = bi: bj: bk для всехi, j, k и т.д.
Оптимальноераспределение взаимозаменяемых ресурсов. Имеютсяm видов взаимозаменяемых ресурсов а1, а2,., аm,используемых при выполнении n различных работ (задач). Объемы работ, которые должныбыть выполнены, составляют b1, b2,., bi, bnединиц. Заданы числа />, указывающие, сколькоединиц j-й работы можно получить из единицы і-го ресурса, а также Cij — затраты на производство j-й работы из единицы i-го ресурса. Требуется распределитьресурсы по работам таким образом, чтобы суммарная эффективность выполненных работбыла максимальной (или суммарные затраты — минимальными).
Даннаязадача называется общей распределительной задачей. Количество единиц i-го ресурса,которое выделено на выполнение работ j-го вида, обозначим через xij.
Математическаямодель рассматриваемой задачи такова:
/> (3.3)
при ограничениях
/> (3.4)
/> (3.5)
Ограничение(3.4) означает, что план всех работ должен быть выполнен полностью, а (3.5) означает,что ресурсы должны быть израсходованы целиком.
Примеромэтой задачи может быть задача о распределении самолетов по авиалиниям.
Задачао смесях. Имеется р компонентов, при сочетаниикоторых в разных пропорциях получают разные смеси. Каждый компонент, а следовательнои смесь, содержит q веществ. Количество k-го вещества k = 1, 2,., q, входящее всостав единицы і-го компонента и в состав единицы смеси, обозначим через аikи аk соответственно.
Предположим,что аk зависит от аik линейно, то есть если смесь состоитиз x1 единиц первого компонента, x2 — единицу второго компонентаи т.д., то
/>
Заданор величин Ci, характеризующих стоимость, массу или калорийность единицыi-го компонента, и q величин bk, указывающих минимально необходимое процентноесодержание k-го вещества в смеси. Обозначим через x1, x2,.,xрзначение компонента р-го вида, входящего в состав смеси.
Математическаямодель этой задачи имеет такой вид:
/> (3.6)
при ограничении
/> (3.7)
/>
Ограничение(3.7) означает, что процентное содержание k-го вещества в единице смеси должно бытьне меньше bk.
К этойже модели принадлежит также задача определения оптимального рациона кормления скота.4. Геометрический методрешение задач ЛП
Задача 1. При откорме каждое животное должно получить не менее14 ед.питательного вещества S1, не менее 15 ед. веществаS2 и не менее 10 веществаS3. Для составления рационаиспользуют два вида корма. Содержание количества единиц питательных веществ в 1килограмме каждого вида корма и стоимость одного килограмма корма дана в таблице1.
Таблица 1Питательные вещества Количество единиц питательных веществ в 1 кг. корма корм 1 корм 2
S1 1 2
S2 1 3
S3 2 1 Стоимость 1 кг. корма 3 7
Составить рацион минимальной стоимости.
Решение:
X1 + 2X2 ≥ 14
X1 + 3X2 ≥ 15
2X1 + X2 ≥ 10
X1, X2 ≥ 0
/>3X1 + 7 X2 → min
X1 + 2X2 = 14
X1 + 3X2 =15
2X1 + X2 = 10
/>
5. Симплексный метод решениязадач ЛП
Задача 2. Для изготовления 4-ёх видов продукции P1, P2, P3, P4 используют два видасырья: S1 и S2. Запасы сырья, количество единиц сырья, затрачиваемых на изготовлениеединицы продукции, а так же величина прибыли, получаемая от реализации единицы продукции,приведены в таблице 2.
Таблица 2.Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции
P1
P2
P3
P4
S1 3 1 1 1 2
S2 7 1 2 3 1 Прибыль от единицы продукции 9 14 15 10
Составить план производства, обеспечивающий получений максимальнойприбыли.
Решение:
1. Формальная постановка задачи имеет следующий вид:
9X1 + 14X2 + 15 X3 + 10X4 → max
X1 + X2 + X3 + 2X4 ≤ 3
X1 + 2X2 + 3X3 + X4 ≤ 7
X1, X2, X3, X4 ≥ 0
2. Приведем к стандартной (канонической) форме:
F = 9X1 + 14X2 +15X3 + 10X4 + 0X5 + 0X6
X1 + X2 + X3 + 2X4 + X5 = 3
X1 + 2X2 +3X3 + X4 + X6 = 7
X1, X2, X3, X4 ≥ 0
3. Запишем систему ограничений в векторной форме:
X1 (1/1) + X2 (1/2) + X3 (1/3) + X4 (2/1) + X5 (1/0)+ X6 (0/1) = (3/7)
P1 P2 P3 P4 P5 P6 P0
P5, P6 — базисные
4. Запишем первоначальный опорный план:
Х0 (0, 0, 0, 0, 3,7), F0 = 9*0 + 14*0 +15*0 +10*0+ 0*3 +0*7 = 0
Составим соответствующую плану 1 симплексную таблицу: Базис Сб Р0 Р1 Р2 Р3 Р4 Р5 Р6 9 14 15 10 Р5 3 1 1 1 2 1 Р6 7 1 2 3 1 1 -9 -14 -15 -10
Вычислим оценки:
∆ = (Сб*А) — С
∆1 = (0 *1 + 0*1) — 9 = — 9; ∆2 = (0 *1 + 0*2)- 14 = — 14; ∆3 = (0 *1 + 0*3) — 15 = — 15; ∆4 = (0 *2 + 0*1) — 10 =- 10; ∆5 = (0 *1 + 0*0) — 0 = 0; ∆6 = (0 *0 + 0*1) — 0 = 0
Критерием оптимальности является условие, что все ∆ ≥0, т.к. это не так, решение не оптимально.
Выберем вектор, который будем включать в базис:
min1 = (3/1; 7/1)= 3; min2 = (3/1; 7/2) =3; min3 = (3/1; 7/3) = 2 1/3;min4= (3/2; 7/1) = 1 1/2,
теперь посмотрим соотношение min c ∆:
∆f = — ∆*min
∆f 1 = — (-9)*3 = 27; ∆f 2 = — (-14)*3 = 42; ∆f 3 = — (-15)*2 1/3 = 34.95; ∆f 4 = — (-10)*1 1/2 = 15,
Отсюда следует, что менять будем Р5 на Р2.
5. Составим 2 симплексную таблицу: Базис Сб Р0 Р1 Р2 Р3 Р4 Р5 Р6 9 14 15 10 Р2 14 3 1 1 1 2 1 Р6 1 -1 1 -1 -1 1 5 -1 4 14
7- (3*2) /1 = 1; 1 — (1*2) /1 = — 1; 3 — (2*1) /1 = 1; 1- (2*1)/1 = — 1; 0- (1*1) /1 = — 1; 1- (0*1) /1 = 1
∆1 = 14*1+0* (-1) — 9 = 5; ∆3 = 14*1+0*1-15= — 1; ∆4 = 14*2+0* (-1) — 10 = 4;
∆5 = 14*1+0* (-1)- 0 = 14; ∆6 = 14*0+0*1-0 = 0;
Х1 (0,3,0,0,0,1); F1 = 9*0+14*3+15*0+10*0+0*0+0*1 = 42
Приняв этот план видим, что выпуск 2го вида продукции являетсянаиболее выгодным, остаток сырья 2го вида продукции составит 1 единица.
Т.к. не все ∆ ≥ 0, план не является оптимальным,поэтому продолжим…..
Вектором Р3 заменим Р6 min = (3/1, 1/1) = (3,1)
6. Составим 3 симплекснуютаблицуБазис Сб Р0 Р1 Р2 Р3 Р4 Р5 Р6 9 14 15 10 Р2 14 2 2 1 3 2 -1 Р3 15 1 -1 1 -1 -1 1 4 17 13 1
3-1*1/1=2; 1- (-1) *1/1=2; 1-0*1/1=1; 2-1* (-1) /1=3; 1-1*(-1) /1=2; 0-1*1/1=-1
∆1 = 14*2+15* (-1) — 9 = 4; ∆2 = 14*1+15*0-14= 0; ∆4 = 14*3+15* (-1) — 10 = 17;
∆5 = 14*2+15* (-1)- 0 = 13; ∆6 = 14* (-1) +15*1-0 = 1;
Х2 = (0,2,1,0,0,0); F2 = 9*0+14*2+15*1+0 = 43
План является оптимальным, говорим о том, что наиболее выгоднымявляется производство 2единиц 2 вида продукции и 1единицы 3 вида продукции, причемсырье расходуется полностью.
6. Теоремы двойственностии их использование в задачах ЛП
Каждойзадаче линейного программирования можно определенным образом сопоставить некоторуюдругую задачу (линейного программирования), называемую двойственной или сопряженнойпо отношению к исходной или прямой задаче. Дадим определение двойственной задачипо отношению к общей задаче линейного программирования, состоящей, как мыуже знаем, в нахождении максимального значения функции
/> (42)
при условиях
/> (43)
/> (44)
Определение.
Задача,состоящая в нахождении минимального значения функции
/> (45)
при условиях
/> (46)
/> (47)
называетсядвойственной по отношению к задаче (42) — (44). Задачи (42) — (44) и (45)- (47) образуют пару задач, называемую в линейном программировании двойственнойпарой. Сравнивая две сформулированные задачи, видим, что двойственная задачасоставляется согласно следующим правилам:
1. Целеваяфункция исходной задачи (42) — (44) задается на максимум, а целевая функция двойственной(45) — (47) — на минимум.
2. Матрица
/> (48)
составленнаяиз коэффициентов при неизвестных в системе ограничений (43) исходной задачи (42)- (44), и аналогичная матрица
/> (49)
в двойственнойзадаче (45) — (47) получаются друг из друга транспонированием (т.е. заменой строкстолбцами, а столбцов — строками).
3. Числопеременных в двойственной задаче (45) — (47) равно числу ограничений в системе(43) исходной задачи (42) — (44), а число ограничений в системе (46) двойственнойзадачи — числу переменных в исходной задаче.
4. Коэффициентамипри неизвестных в целевой функции (45) двойственной задачи (45) — (47) являютсясвободные члены в системе (43) исходной задачи (42) — (44), а правыми частями всоотношениях системы (46) двойственной задачи — коэффициенты при неизвестных в целевойфункции (42) исходной задачи.
5. Еслипеременная xj исходной задачи (42) — (44) может принимать тольколишь положительные значения, то j-е условие в системе (46) двойственной задачи(45) — (47) является неравенством вида “". Если же переменная xjможет принимать как положительные, так и отрицательные значения, то 1 — соотношениев системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями(43) исходной задачи (42) — (44) и переменными двойственной задачи (45) — (47).Если i — соотношение в системе (43) исходной задачи является неравенством,то i-я переменная двойственной задачи />. В противномслучае переменная уj может принимать как положительные, так иотрицательные значения.
Двойственныепары задач обычно подразделяют на симметричные и несимметричные. В симметричнойпаре двойственных задач ограничения (43) прямой задачи и соотношения (46) двойственнойзадачи являются неравенствами вида “/>". Таким образом, переменные обеихзадач могут принимать только лишь неотрицательные значения.
Теорема двойственности.
Существующиезависимости между решениями прямой и двойственной задач характеризуются сформулированныминиже леммами и теоремами двойственности.
Лемма1.
ЕслиХ — некоторый план исходной задачи, a Y — произвольный план двойственной задачи, то значениецелевой функции исходной задачи при плане Х всегда не превосходит значения целевойфункции двойственной задачи при плане Y, т.е. />
Лемма2.
Если/>для некоторыхпланов X* и Y* задач,то X* — оптимальный план исходной задачи, а Y* — оптимальныйплан двойственной задачи.
Теорема8
(первая теорема двойственности). Если одна из задач двойственнойпары или, имеет оптимальный план, то и другая имеет оптимальный план и значенияцелевых функций задач при их оптимальных планах равны между собой, т.е. />
Еслиже целевая функция одной задачи из двойственной пары неограничена (для исходной — сверху, для двойственной — снизу), то другая задачавообще не имеет планов.
Теорема9
(вторая теорема двойственности).
План/>задачи и план />задачи, являются оптимальнымипланами этих задач тогда и только тогда, когда для любого />выполняется равенство
/>
Геометрическаяинтерпретация двойственных задач. Если числопеременных в прямой и двойственной задачах, образующих данную пару, равно двум,то, используя геометрическую интерпретацию задачи линейногопрограммирования, можно легко найти решение данной пары задач. При этом имеет местоодин из следующих трех взаимно исключающих друг друга случаев:
1) обезадачи имеют планы;
2) планыимеет только одна задача;
3) длякаждой задачи двойственной пары множество планов пусто.
а) Составить задачу двойственную к примеру 2.
б) Найти её решение любым методом.
в) Найти решение задачи 2, используя теорему двойственности.
а) Задача имеет вид: 1 1 1 2 1 3 2 1
f = 9X1 + 14X2 + 15 X3 + 10X4 → max 1 1 1 2 1 2 3 1
X1 + X2 + X3 + 2X4 ≤ 3
X1 + 2X2 + 3X3 + X4 ≤ 7
X1, X2, X3, X4 ≥ 0
Составим двойственную задачу по следующей схеме:
число переменных в дв. задаче равно числу ограничений в исходной,а число ограничений в дв. равно числу переменных в исходной;
в дв. задаче меняется вид экстремума (min→max);
векторы правой части и коэффициентов целевой функции в дв. задачеменяются местами: первый становится вектором коэффициентов целевой функции, а второй- вектором правой части в системе ограничений;
левая часть системы ограничений строится по транспонированнойматрице (строки меняются со столбцами), которая умножается на вектор переменныхдвойственной задачи
знаки в системе ограничений двойственной задачи определяютсязнаками ограничений неотрицательности в исходной задаче.
/>g = 3Y1+7Y2 → min
Y1 + Y2 ≥ 9
Y1 + 2Y2 ≥ 14
Y1 + 3Y2 ≥ 15
2Y1 + Y2 ≥ 10
Y1, Y2 ≥ 0
б) Решим задачу графическим методом
/>
в) Оптимальным планом задачи 2, решенной симплексным методомявляется:
Х2 = (0,2,1,0,0,0); F2 = 9*0+14*2+15*1+0 = 43
Используя 3 симплексную таблицу найдем оптимальный план двойственнойзадачи.
Из 1 теоремы двойственности следует что: Y=Cб*А — 1
Составим матрицу А из компонентов векторов входящих в оптимальныйбазис 1 1 2 3
А = Р2; Р3 =
Определим обратную матрицу А-1: 2 -1 -1 1
А-1 =Р5; Р6= = (12;
1)
Оптимальный план двойственности равен:
Y = (12, 1, 0, 0, 0, 0); G = 3*12+7*1 = 43
Подставим оптимальный план прямой задачи в систему ограничений
/>
12+1 > 9
12+2*1 = 14
12+3*1 = 15
2*12+1 > 10
Первоеограничение двойственной задачи выполняется как строгое неравенство. Это означает,что двойственная оценка сырья, используемого на производство одного изделия 1 и4 вида, выше цены этого изделия и, следовательно, выпускать изделия этихвидов невыгодно. Его производство и не предусмотрено оптимальным планом прямой задачи.Второе и третье ограничения двойственной задачи выполняются как строгие равенства.Это означает, что двойственные оценки сырья, используемого для производства единицысоответственно изделий 2 и 3 вида, равны в точности их ценам. Поэтомувыпускать эти два вида продукции по двойственным оценкам экономически целесообразно.Их производство и предусмотрено оптимальным планом прямой задачи.
Таким образом,двойственные оценки тесным образом связаны с оптимальным планом прямой задачи. Всякоеизменение исходных данных прямой задачи может оказать влияние как на ее оптимальныйплан, так и на систему оптимальных двойственных оценок. Поэтому, чтобы проводитьэкономический анализ с использованием двойственных оценок, нужно знать их интервалустойчивости. К рассмотрению этого мы сейчас и перейдем.
Таким образом, получим тот же результат, который приведен всимплекс-таблице для оптимального решения прямой задачи.
Анализ сопоставления результатов, полученных при решении прямойи двойственной задачи, позволяет сформулировать интересный вывод.
На итерации, приводящей к оптимуму, /> Это равенство справедливовсегда и фактически соответствует оптимальным значениям переменных обеих задач.
Основная и двойственная к ней задачи образуют пару взаимно двойственныхзадач: двойственная задача к двойственной оказывается основной задачей. Т.е. еслимы возьмем двойственную задачу и по теоремам двойственности перейдем ко второй двойственнойзадаче она окажется прямой задачей.
используявторую теорему двойственности, найти решение исходной.
Значениелинейной функции двойственной задачи от Y численно равно минимальному значению линейнойфункции исходной задачи
Пропустимпроцесс решения двойственной ЗЛП, записав только результаты:
Y1=12 Y2=1Y3=0 min (φ) =43
Т.к max(f) =min (φ), решение исходной задачи уже известно. Остаётся только найти значенияX1, X2, X3, при которых это значение достигается. Здесь мы применим вторую теоремудвойственности, которая устанавливает следующее соответствие:
/>
В нашемпримере получается следующая система линейных уравнений:
/>Y1 + Y2 = 9
Y1 + 2Y2 = 14
Y1 + 3Y2 = 15
2Y1 + Y2 = 10
С= (3,7) y1=12 y2=1 т.к. у1>0 и y2>0, то
/>X1 + X2 + X3 + 2X4 =3
X1 + 2X2 + 3X3 + X4 =7
12+1≠ 9, х1=0
12+2*1=14 → х2≠ 0
12+3*1=15→ х3≠ 0
2*12+1≠10, х4=0
х2+х3=3 Х2*=2
2х2+3х3=7 Х3*=1
F = 9*0+14*2+15*1+0 = 436. Транспортная задачаи её решение методом потенциалов
Исходные данные приведены в таблице 3, найти оптимальный план.
Таблица 3.Мощность поставщиков Мощность потребителей
18
90
24 6 24 - 18 - 24 - 48 6
5 _
4 _
3 18
4 24
0 6 42
18
12
3 6
2 24
5 _
5 _
0 12 18 -
1 18 6
6 _
3 _
2 _
0 _
↓
→ 108
Число занятых клеток должно быть m+n-1; 3+5-1=7, следовательноопорный план является невырожденным
F = 5X11+4X12+3X13+4X14+3X21+2X22+5X23+5X24+X31+6X32+3X33+2X34 → min
/>X11+X12+X13+X14+X15=48
X21+X22+X23+X24+X25=42
X31+X32+X33+X34+X35=18
X11+X21+X31=24
X12+X22+X32=24
X13+X23+X33=18
X14+X24+X34=24
Xij ≥ 0, i = 1,2,3,4, j = 1,2,3, X15+X25+X35≤ 18
Определим значение целевой функции
F (X1) = 3*6+18+24*2+3*18+4*24+6*0+12*0= 234
Проверим оптимальность опорного плана
/>ά1=0 ά1=0ά1=0
ά1+β3=3 β3=3β3=3
ά1+β4=4 β4=4β4=4
ά1+β5=0 β5=0β5=0
ά2+β1=3 → β1=3 →β1=3
ά2+β2=2 β2=2β2=2
ά2+β5=0 ά2+0=0ά2=0
ά3+β1=1 ά3+3=1ά3=-2
Занесем найденные значения потенциалов в таблицу 4 вычеслимоценки свободных клеток
∆ ij = (βj+ άi) — Cij
Таблица 4 β1=3 β2=2 β3=3 β4=4 β5=0 ά1=0 5 4 3 18 4 24 0 6 ά2=0 3 6 2 24 5 5 0 12 ά3=-2 1 18 6 3 2
∆11 (0+3) — 5=-2; ∆12 (0+2) — 4=-2; ∆23 (0+3)- 5=-2; ∆24 (0+4) — 4=0; ∆32 (-2+2) — 2=-2; ∆33 (-2+3) — 3=-2;∆34 (-2+4) — 2=0; ∆35 (-2+0) — 0=-2,
т.к. среди оценок нет значений больше 0, то план является оптимальным.
Суммарные затраты:
F (X1) = 3*6+18+24*2+3*18+4*24+6*0+12*0= 234
1. Решение задач ЛП с использованием программы "Excel"
MS Excelсодержит модуль «Поиск решения» позволяющийосуществлять поиск оптимальных решений, в том числе решение задач линейного программирования.
Постановка задачи осуществляется посредством задания ячеек дляпеременных и записи формул с использованием этих ячеек для целевой функции и системыограничений.
Решим задачу 1:
X1 + 2X2 ≥ 14
X1 + 3X2 ≥ 15
2X1 + X2 ≥ 10
X1, X2 ≥ 0
3X1 + 7 X2 → min
/>
Что соответствует найденному ранее решению.
Решим вторую задачу:
9X1 + 14X2 + 15 X3 + 10X4 → max
X1 + X2 + X3 + 2X4 ≤ 3
X1 + 2X2 + 3X3 + X4 ≤ 7
X1, X2, X3, X4 ≥ 0
/>
/>
Что соответствует найденному ранее решению.
Решим двойственную задачу:
g = 3Y1+7Y2 → min
Y1 + Y2 ≥ 9
Y1 + 2Y2 ≥ 14
Y1 + 3Y2 ≥ 15
2Y1 + Y2 ≥ 10
Y1, Y2 ≥ 0
/>
Решим транспортную задачу:
/>
Что соответствует найденному ранее решению.
Заключение
В курсовойработе рассмотрены варианты решений оптимизационных экономических задач методамилинейного программирования.
В настоящеевремя линейное программирование является одним из наиболее употребительных аппаратовматематической теории оптимального принятия решения. Для решения задач линейногопрограммирования разработано сложное программное обеспечение, дающее возможностьэффективно и надежно решать практические задачи больших объемов. Эти программы исистемы снабжены развитыми системами подготовки исходных данных, средствами их анализаи представления полученных результатов.
Современныеметоды линейного программирования достаточно надежно решают задачи общего вида снесколькими тысячами ограничений и десятками тысяч переменных. Для решения сверхбольшихзадач используются уже, как правило, специализированные методы.
Литература
1. Акулич И.Л. Математическое программирование в примерах и задачах.М.: Высшая школа, 1986 — 319 с.
2. Бодров В.И., Лазарева Т.Я., Мартемьянов Ю.Ф., «Математическиеметоды принятия решений» Учебное пособие. Тамбов, 2004.124 с
3. Гельман В.Я. Решение математических задач средствами Excel: Практикум.В.Я. Гельман. — СПб.: Питер, 2003. — 237 с.
4. Коршунова Н.И., Пласунов В.С. Математика в экономике. Учебное пособие.М.: Вита-Пресс, 1996.,368 с.
5. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическоманализе. Учебник-3-е изд., исп. -М. Дело, 2002. -688с.
6. Фомин Г.П. Методы и модели линейного программирования в коммерческойдеятельности. Учебное пособие. — М.: Финансы и статистика, 2000 — 128 с.
7. Фомин Г.П. Математические методы и модели. Учебник. — М.: Финансыи статистика, 2001 — 544 с.