Xreferat.com » Рефераты по экономико-математическому моделированию » Линейное программирование как метод оптимизации

Линейное программирование как метод оптимизации

width="89" height="22" align="BOTTOM" border="0" />для некоторых планов 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=1 Y3=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 = 43


6. Транспортная задача и её решение методом потенциалов


Исходные данные приведены в таблице 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 0

∆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


Решение задач ЛП с использованием программы "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 с.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: