Симплекс-метод решения задач линейного программирования.





Калининградский Государственный Технический Университет

Кафедра СУиВТ

 

 

Рекомендована к защите: Защищена с оценкой:

____________________ ___________________

Дата, подпись дата, подпись

 

Пояснительная записка

К курсовой работе по Математическому Моделированию Экономических Процессов (ММЭП)

 

 

Вариант 17: «Поставить и формализовать задачу минимизации суммарных затрат на перевозку грузов автотранспортной компании в форме задачи математического программирования по заданным условиям»

 

 

Работу выполнил:

Студент группы 12-ИЭ

Кутепова М.Д._______________

Работу проверил:

Арунянц Г.Г. _______________

 

Г. Калининград, 2016 г.


 

Содержание:

 

Введение. 3

1. Описание и построение модели. 7

1.1. Математическое программирование. 7

1.2. Обоснование выбранного подхода к моделированию.. 9

1.3. Описание концептуальной модели. 10

1.4. Описание элементов и ограничений решаемой задачи. 11

2. Решение задачи. 12

2.1.Блок-схема алгоритма решения задачи. 12

3. Анализ полученных данных. 18

Заключение. 19

Список используемой литературы.. 20

ПРИЛОЖЕНИЕ 1. 21

 


 

Введение

В данной курсовой работе мы рассматриваем пример решения задачи математического программирования «Минимизация суммарных затрат на перевозку грузов автотранспортной компании» с использованием метода целочисленного линейного программирования (ЦЛП в дальнейшем),базовой технологии и встроенных функций EXCEL 2000. В курсовой работе также рассмотрены этапы построения модели.

Задачи такого типа направлены, как правило, на максимальную прибыль от реализации товаров, работ, услуг (ТУР) или же, как в “транспортной задаче“– минимизации издержек. В любом случае нужно найти max или min, или так называемый экстремум. Задачи такого рода называют задачами линейного программирования, которые весьма широко применяются в экономических расчетах, а также в принятии управленческих решений.

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

Если же все ограничения и целевая функция содержат лишь линейные функции, то это — задача линейного программирования.

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

Действительно, пуcть необходимо исследовать на экстремум линейную функцию Z = С1х12х2+... +СNxN

при линейных ограничениях(рис.1)

 

a11x1 + a22x2 + ... + a1NХN = b1

a21x1 + a22x2 + ... + a2NХN = b2

. . . . . . . . . . . . . . .

aМ1x1 + aМ2x2 + ... + aМNХN = bМ

Рис.1. Линейные ограничения функции цели.

 

Так как Z - линейная функция, то = Сj (j = 1, 2, ..., n), то все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку частные производные являются константами.

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

 

Цели выполняемой работы:

1.) Получить практические знания, при применении методов решения задач линейного программирования;

2.) Построение модели;

3.) Решение задачи методом линейного программирования;

3.) Анализ модели.

Для решения задач линейного программирования используются следующие методы :

 

Графический метод решения задачи линейного программирования.

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

 

Симплекс-метод решения задач линейного программирования.

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

2.1.) Отыскание базисного решения – некой точки А(рис.2) лежащей на функции;

2.2.)Отыскание опорного решения – некой точки B (рис. 2) принадлежащей области, образованной ограничениями;

2.3.) Отыскание оптимального решения – некой точки С (рис. 2) принадлежащей той – же области, и в которой целевая функция достигает своего экстремума.

 
 


Рис. 2. Геометрический вид модели в виде многогранника.

C

 
 


a b

 





Рекомендуемые страницы:


©2015-2019 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-27 Нарушение авторских прав и Нарушение персональных данных

Обратная связь

ТОП 5 активных страниц!