183697 (629908), страница 4
Текст из файла (страница 4)
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, при которых это значение достигается. Здесь мы применим вторую теорему двойственности, которая устанавливает следующее соответствие:
В нашем примере получается следующая система линейных уравнений:
Y
1 + Y2 = 9
Y1 + 2Y2 = 14
Y1 + 3Y2 = 15
2Y1 + Y2 = 10
С= (3,7) y1=12 y2=1 т.к. у1>0 и y2>0, то
X 1 + 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
X
11+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 с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
