Линейное программирование как метод оптимизации
Курсовой проект - Экономика
Другие курсовые по предмету Экономика
ных обеих задач.
Основная и двойственная к ней задачи образуют пару взаимно двойственных задач: двойственная задача к двойственной оказывается основной задачей. Т.е. если мы возьмем двойственную задачу и по теоремам двойственности перейдем ко второй двойственной задаче она окажется прямой задачей.
используя вторую теорему двойственности, найти решение исходной.
Значение линейной функции двойственной задачи от 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
9024 624 - 18 - 24 - 4865 _4 _3 184 24 0 64218
123 62 245 _5 _ 0 1218-1 18 66 _3 _2 _0 _
v
> 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=05 43 184 240 6?2=03 62 24550 12?3=-21 186320
?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 с.