Линейное программирование как метод оптимизации (стр. 4 из 4)

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
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.

Мощность поставщиков		Мощность потребителей				1890
		24 6	24 -	18 -	24 -
48	6	5_	4_	318	424	0 6
42	1812	36	224	5_	5_	0 12
18	-	118 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

1.Решение задач ЛП с использованием программы "Excel"

MSExcelсодержит модуль "Поиск решения" позволяющий осуществлять поиск оптимальных решений, в том числе решение задач линейного программирования.

Постановка задачи осуществляется посредством задания ячеек для переменных и записи формул с использованием этих ячеек для целевой функции и системы ограничений.

Решим задачу 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 с.