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

↓

→ 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

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

 Скачать реферат