Решение задач с помощью линейного программирования

Автор работы: Пользователь скрыл имя, 29 Апреля 2013 в 21:45, курсовая работа

Описание работы

Целью данной курсовой работы является изучение методов решения задач математического моделирования на примере задач планирования производства и транспортной задачи.
Задачи работы:
изучить литературу по данной теме
для заданного варианта получить решение задачи линейного программирования:
- графическим методом;

Содержание работы

ВВЕДЕНИЕ 4
1 ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ К РЕШЕНИЮ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 5
1.1 Определение и характеристика линейного программирования 5
1.2 Характеристика геометрического метода решения задач 7
1.3 Характеристика симплекс-метода как основного аппарата решения задач линейного программирования 10
1.4 Характеристика метода решения задач с помощью теории двойственности 14
1.5 Основные этапы, особенности и методы решения транспортной задачи 16
2 РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 20
2.1 Решение задачи планирования производства геометрическим способом 20
2.2 Решение задачи планирования производства симплекс-методом 25
2.3. Решение задачи планирования производства с помощью теории двойственности 30
2.4 Составление математической модели транспортной задачи 31
2.5 Нахождение опорного плана транспортной задачи методом наименьшего элемента 32
2.6 Решение транспортной задачи методом потенциалов 36
ЗАКЛЮЧЕНИЕ 38
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 39

Скачать архив (189.04 Кб) Сколько стоит заказать работу?

Файлы: 1 файл

Dokument_Microsoft_Office_Word.doc

— 728.00 Кб (Скачать файл)

Искомый элемент равен 8. Для этого элемента запасы равны 180, потребности 280. Поскольку минимальным является 180, то вычитаем его.

X₂₃ = min(180,280) = 180.

Таблица 2.5.6

x	х	14	3	х	0
х	х	10	х	12	430
4	8	16	х	х	180-180
0	280-180	330	0	0	0

Искомый элемент равен 11. Для этого элемента запасы равны 430, потребности 100. Поскольку минимальным является 100, то вычитаем его.

X₂₃ = min(430,100) = 100.

Таблица 2.5.7

x	х	14	3	х	0
х	11	10	х	12	430-100
4	х	16	х	х	0
0	100-100	330	0	0	0

Искомый элемент равен 10. Для этого элемента запасы равны 330, потребности 330. Поскольку минимальным является 330, то вычитаем его.

X₂₃ = min(330,330) = 330.

Таблица 2.5.8

x	х	14	3	х	0
х	11	10	х	12	330-330=0
4	х	16	х	х	0
0	0	330-330=0	0	0	0

Таблица 2.5.9

	1	2	3	4	5	Запасы
1	21	18	14	3 [290]	6 [80]	370
2	7	11 [100]	10 [330]	5	12 [20]	450
3	4 [300]	8 [180]	16	9	13	480
Потребности	300	280	330	290	100

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

Подсчитаем число занятых клеток таблицы, их 7, а должно быть

m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 3 290 + 6 80 + 11 100 + 10 330 + 12 20 + 4 300 + 8 180 = 8630

Ответ: Минимальные затраты перевозок составят 8630 ден. ед.

2.6 Решение транспортной задачи методом потенциалов

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₄ = 3; 0 + v₄ = 3; v₄ = 3

u₁ + v₅ = 6; 0 + v₅ = 6; v₅= 6

u₂ + v₅ = 12; u₂+ 6 = 12; u₂ = 6

u₂ + v₂ = 11; 6+ v₂ = 11; v₂ = 5

u₃ + v₂ = 8; u3 + 5 = 8; u₃ = 3

u₂+ v₃ = 10; 6 + v₃ = 10; v₃ = 4

u₃ + v₁ = 4; 3 + v₁ = 4; v₁ = 1

Таблица 2.6.1

	v₁=1	v₂=5	v₃=4	v₄=3	v₅=6	Запасы
u₁=0	21	18	14	3 [290]	6 [80]	370
u₂=6	7	11 [100]	10 [330]	5	12 [20]	450
u₃=3	4 [300]	8 [180]	16	9	13	480
Потребности	300	280	330	290	100

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij (см. таблицу 2.6.1).

(2;4): 6 + 3 > 5; ∆₂₄ = 6 + 3 - 5 = 4

Выбираем максимальную оценку свободной клетки (2;4): 5

Для этого в перспективную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-»

Таблица 2.6.2

	1	2	3	4	5	Запасы
1	21	18	14	3 [290][-]	6 [80][+]	370
2	7	11 [100]	10 [330]	5[+]	12 [20][-]	450
3	4 [300]	8 [180]	16	9	13	480
Потребности	300	280	330	290	100

Цикл приведен в таблице 2.6.2 (2,4; 2,5; 1,5; 1,4).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 5) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 2.6.3

	1	2	3	4	5	Запасы
1	21	18	14	3 [270]	6 [100]	370
2	7	11 [100]	10 [330]	5[20]	12	450
3	4 [300]	8 [180]	16	9	13	480
Потребности	300	280	330	290	100

u₁ + v₄ = 3; 0 + v₄ = 3; v₄ = 3

u₂ + v₄ = 5; u₂ + 3 = 5; u₂= 2

u₁ + v₅ = 6; 0+ v₅ = 6; v₅ = 6

u₂ + v₂ = 11; 2 + v₂ = 11; v₂ = 9

u₃+ v₂ = 8; u₃ + 9 = 8; u₃ = -1

u₂+ v₃ = 10; 2 + v₃ = 10; v₃ = 8

u₃ + v₁ = 4; -1 + v₁ = 4; v₁ = 5

Таблица 2.6.4

	v₁=5	v₂=9	v₃=8	v₄=3	v₅=6	Запасы
u₁=0	21	18	14	3 [270]	6 [100]	370
u₂=2	7	11 [100]	10 [330]	5[20]	12	450
u₃=-1	4 [300]	8 [180]	16	9	13	480
Потребности	300	280	330	290	100

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij (см. таблицу 2.6.4).

Минимальные затраты составят:

F(x) = 3 270 + 6 100 + 11 100 + 10 330 + 5 20 + 4 300 + 8 180 = 8550

Ответ: минимальные затраты перевозок составят 8550 ден. ед.

ЗАКЛЮЧЕНИЕ

Необходимость решения задач линейного программирования на современных предприятиях очевидна. Построение и решение экономико-математических, а также транспортных задач позволяет, в свою очередь, решать различные технико-экономические и экономические производственные задачи, которые позволяют найти наиболее рациональные пути и способы транспортировки товаров и минимизировать сумму транспортных расходов.

Целью моей курсовой работы было изучение методов решения задач математического моделирования.

Для достижения поставленной цели были использованы различные источники литературы. На практике рассмотрено решение задачи заданными методами и решена транспортная задача. При сравнении ответов выяснилось, что данные способы дали одинаковые результаты, что доказывает правильность полученного оптимального плана.

Данная работа, может послужить примером материалов для самостоятельного изучения методов решения задач математического моделирования.

Мы считаем, что цель, поставленная, в курсовой работе полностью достигнута, задачи выполнены, актуальность доказана.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Акулич, И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов / И.Л. Акулич.- М.: Высш.шк., 1986. – 319с.

2. Ашманов, С.А. Линейное программирование / С.А. Ашманов. – М.: Наука, 1981. – 278с.

3. Кузнецов, Ю.Н. Математическое программирование / Ю.Н. Кузнецов, В.И Козубов, А.Б. Волощенко. – М.: Высшая школа, 1980. – 364с.

4. Калихман, И.Л. Линейная алгебра и программирование / И.Л. Калихман. – М.: Высшая школа, 1967. – 256с.

5. Красс, М.С. Основы математики и ее приложения в экономическом образовании / М.С. Красс, Б.П. Чупрынов. – М: Издательство «Дело», 2001г.

6. Лященко, И.Н. Линейное и нелинейное программирование. / И.Н. Лященко, Е.А. Карагодова, Н.В. Черникова, Шор Н.З.. – К.: «Высшая школа», 1975. - 372с.

7. Матвеев В.И. Курс линейного программирования для экономистов: Учеб. Пособие / В.И. Матвеев, Р.В. Сагитов, В.Г. Шершнев. — М.: Менеджер, 1998. – 380с.

8. Общий курс высшей математики для экономистов: Учебник / Под ред. В.И. Ермакова. ― М.: ИНФА-М, 2002. – 304с.

9. Тарасенко, Н.В. Линейное программирование: курс лекций / Н.В. Тарасенко. – Иркутск: изд-во БГУЭП, 2003. – 151с.

10. Юдин, Д.Б. Линейное программирование. Теория и конечные методы / Д.Б. Юдин, Е.Г. Гольштейн. – М.: Физматиз, 1963. – 365с.

Информация о работе Решение задач с помощью линейного программирования