Задачи линейного программирования

Автор: Пользователь скрыл имя, 25 Октября 2013 в 18:25, курсовая работа

Краткое описание

Задача оптимизации может быть сформулирована на языке математики, если множество доступных вариантов удается описать с помощью математических соотношений (равенств, неравенств, уравнений), а каждое решение – оценить количественно с помощью некоторого показателя, называемого критерием оптимальности или целевой функцией. Тогда наилучшим решением будет то, которое доставляет целевой функции наибольшее или наименьшее значение, в зависимости от содержательного смысла задачи.

Оглавление

Введение 3
1 Линейное программирование 4
1.1 Задачи линейного программирования 4
1.2 Решение задач линейного программирования симплекс – методом 5
1.3 Решение задач линейного программирования графическим методом 10
2 Реализация методов линейного программирования на практическом применении 11
2.1 Пример решения задачи линейного программирования симплекс-методом 11
2.2 Пример решения задачи линейного программирования графическим способом 14
2.3 Пример решения задачи линейного программирования с помощью MS EXCEL 16
3 Решение задач линейного программирования 20
3.1 Решение задачи линейного программирования графическим методом 20
3.2 Решение задачи линейного программирования симплекс-методом 27
3.3 Решение транспортной задачи 31
Заключение 36
Список использованной литературы 37

Скачать в ZIP (211.70 Кб) Сколько стоит заказать работу?
Файлы: 1 файл

КУРСОВАЯ РАБОТА.doc

— 570.00 Кб (Скачать)

 

Конец итераций: индексная  строка не содержит отрицательных элементов - найден оптимальный план

Окончательный вариант  симплекс-таблицы:

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x1

4

1

0

-3

-3

-1

0

3

1

x2

3

0

1

-2

-2

-1

0

2

1

x6

10

0

0

-9

-7

-2

1

7

2

F(X3)

-7

0

0

7

5

2

0

-5+M

-2+M


 
Оптимальный план можно записать так: 
x1 = 4 
x2 = 3 
x6 = 10 
F(X) = -1•4 + -1•3 = -7

 

 

 

3.3 Решение транспортной  задачи

 

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

 

200

200

400

200

200

1

3

4

2

200

1

2

4

1

300

3

4

5

9

300

6

3

7

6


 

Проверим необходимое  и достаточное условие разрешимости задачи.

∑a = 200 + 200 + 300 + 300 = 1000

∑b = 200 + 200 + 400 + 200 = 1000 
Этап I. Поиск первого опорного плана. 
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

 

200

200

400

200

200

1[200]

3

4

2

200

1

2

4

1[200]

300

3

4

5[300]

9

300

6

3[200]

7[100]

6


 
2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 7.

Следовательно, опорный план является вырожденным. Строим новый план. 
Значение целевой функции для этого опорного плана равно:

 

200

200

400

200

200

1

3

4

2[200]

200

1[200]

2

4

1

300

3

4

5[300]

9

300

6

3[200]

7[100]

6


3. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.  
Строим новый план. 
Значение целевой функции для этого опорного плана равно:

 

200

200

400

200

200

1[200]

3

4

2

200

1

2

4

1[200]

300

3

4

5[300]

9

300

6

3[200]

7[100]

6


 
4. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.  
Строим новый план. 
Значение целевой функции для этого опорного плана равно:

 

200

200

400

200

200

1

3

4

2[200]

200

1[200]

2

4

1

300

3

4

5[300]

9

300

6

3[200]

7[100]

6


 
5. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.  
Строим новый план. 
Значение целевой функции для этого опорного плана равно:

 

200

200

400

200

200

1[200]

3

4

2

200

1

2[200]

4

1

300

3

4

5[300]

9

300

6

3

7[100]

6[200]


 
6. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.  
Строим новый план. 
Значение целевой функции для этого опорного плана равно:

 

200

200

400

200

200

1

3[200]

4

2

200

1[200]

2

4

1

300

3

4

5[300]

9

300

6

3

7[100]

6[200]


 
7. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.  
Строим новый план. 
Значение целевой функции для этого опорного плана равно:

 

200

200

400

200

200

1

3[200]

4

2

200

1

2

4

1[200]

300

3[200]

4

5[100]

9

300

6

3

7[300]

6


 
8. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.  
Строим новый план. 
Значение целевой функции для этого опорного плана равно:

 

200

200

400

200

200

1[200]

3

4

2

200

1

2

4

1[200]

300

3

4

5[300]

9

300

6

3[200]

7[100]

6


 
9. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.  
Строим новый план. 
Значение целевой функции для этого опорного плана равно:

 

200

200

400

200

200

1

3

4[200]

2

200

1[200]

2

4

1

300

3

4

5[200]

9[100]

300

6

3[200]

7

6[100]


 
10. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.  
Строим новый план. 
Значение целевой функции для этого опорного плана равно:

 

200

200

400

200

200

1

3

4[200]

2

200

1[200]

2

4

1

300

3

4

5[200]

9[100]

300

6

3[200]

7

6[100]


 
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным. 
Значение целевой функции для этого опорного плана равно:: 
На протяжении многих итераций так и не удалось получить невырожденный план. 
Для получения невырожденного плана принудительно добавляем нуль [0] в клетку (1;2). 
Этап II. Улучшение опорного плана. 
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

 

v1=1

v2=3

v3=7

v4=-

u1=0

1[200]

3[0]

4

2

u2=-

1

2

4

1[200]

u3=-2

3

4

5[300]

9

u4=0

6

3[200]

7[100]

6


 
Опорный план не является оптимальным, так как существуют оценки свободных  клеток, для которых ui + vi > cij 
Выбираем максимальную оценку свободной клетки (1;3): 4 
Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Информация о работе Задачи линейного программирования