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

Размещено на http://www.allbest.ru/

13

Размещено на http://www.allbest.ru/

Введение

математический линейный программирование

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

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

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

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

С помощью математического моделирования в экономике производится качественный экономический анализ, что позволяет раскрыть область экономической информации. Целью работы является чёткое последовательное изложение математического метода, решение и исследование задачи в средах: Microsoft Excel и MSimplex.

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

2. Общая постановка исследуемой задачи

Сервис-центр выполняет n компьютерных услуг.

Известны:

-расходы на одну единицу оказанной услуги выражены в виде матрицы А;

-цена одной единицы каждой услуги соответственно равна С=(С,С,…,С);

-расходы производственных ресурсов (материалы, рабочее время, оборудование, электроэнергия)соответственно в объёме В=(b,b,…b).

В процессе использования производственных ресурсов следует учитывать: экономию ресурсов (<= ), полный расход (= ), перерасход ( >=).

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

n=5; C=(3;2;6;4;-1); B=(5;6;10;8); A=

Ограничения: <= ; = ; <= ; >=

Таблица 1

3. Создание математической модели

Математическая модель

(1) F|(x)=3x1+2x2+6x3+4x4-1x5 ->max

(2) Система ограничений

2x1-3x2+x3+4x4+3x5<5

x1+2x2+4x-3x4+x5=6

x1+4x2-3x3+2x4+6x5<10

4x1+2x2+x4-2x5>8

(3) x_j>=0 (i=1,2,3,4)

4.Краткое изложение математического метода решения общей задачи

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

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

Любая задача линейного программирования решается симплекс методом

Любая ЗЛП -решается ЕМ :-линейная задача

С-М - универсальный метод. Используется для линейных задач (оптимизационных)

Алгоритм симплекс метод различий (ЖАРДАНОВЫ ИСКЛЮЧЕНИЯ)

- модифицированные Жордановы Исключения (МЖИ)

С-М находят опорное и оптимальное решение задач линейного программирования

Алгоритмы для этих решений едины

Все расчеты С-М выполняются с помощью симплекс таблицы

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

Симплекс метод - это характерный пример итерационных вычислений, используемых при решении большинства оптимизационных задач. В вычислительной схеме симплекс-метода реализуется упорядоченный процесс, при котором, начиная с некоторой исходной допустимой угловой точки (обычно начало координат), осуществляются последовательные переходы от одной допустимой экстремальной точки к другой до тех пор, пока не будет найдена точка, соответствующая оптимальному решению.

Симплекс-метод выполняется по двум этапам:

Первый этап-поиск опорного решения

Второй этап-поиск оптимального решения

Все этапы выполняются с помощью МЖИ

5. Аналитическое решение поставленной задачи

Шаг 1 Исключение 0-ур

Таблица 2

Шаг 2 Поиск опорного решения

Таблица 3

Шаг 3 Поиск оптимального решения

Таблица 4

С-М находят опорное и оптимальное решение задач линейного программирования. Алгоритм повторяется до тех пор пока достигнем неотрицательного элемента целевой строки

6.Решение задачи с помощью программы msimplex

Описание программы msimplex

Написана на языке программирования (яп) Delphi. Delphi - среда для написания программ с использованием яп pascal и графического интерфейса. С помощью Delphi, пользователь может написать программу в рамках приложения ms windows. Msimplex предназначена для решения злп. К ним относятся:

1) Основная задача линейного программирования, содержащая в системе ограничения - неравенства

2) Каноническая задача линейного программирования, содержащая в системе ограничения - равенства - уравнения

3) Общая задача линейного программирования, в которой имеются ограничения - равенства и ограничения - неравенства.

При правильном вводе данных программа мгновенно выдает оптимальное решение задачи.

Задача линейного программирования может иметь несколько оптимальных решений.

Это зависит от формулы целевой функции и от алгоритма симплекс-метода. Результаты целевой функции и значения переменных программа выдает шестизначными числами, которые необходимо округлить до трех знаков.

Этапы решения задачи с помощью программы msimplex

1) Установить программу msimplex

2) Выполнить команду <ввод исходных данных>. Ответить на запросы: количество переменных, количество ограничений, коэффициенты целевой функции. Нажать ок

3) Появится окно <результат>.

7.Решение задачи в среде Excel

Рассмотрим решение задачи линейного программирования в ms excel

В ms excel для решения задачи линейного программирования используется надстройка поиск решения

Сначала надстройку поиск решения необходимо подключить (до первого использования)

В ms excel 2013: сервис/настройки/поиск решения/ок

1) Кнопка «office»

2) Кнопка «параметры системы»

3) Настройки

4) Кнопка «перейти»

5) В окне настройки установить флажок и нажать «ок»

6) Далее кнопка «поиск решения» появится во вкладке данные

Решим в ms excel задачу линейного программирования:

1) Создадим область переменных

2) Введем формулу вычисления значений целевой функции

3) Создадим область ограничений

4) Вызовем окно диалога поиск решения

5) Устанавливаем целевую ячейку W1 (там где вычисляется значение целевой функции)

6) Указываем направление оптимизации - минимизация (по условию)

7) В поле Изменяя ячейки указываем ячейки переменных С1:V1

8) Укажем ограничения Нажимаем кнопку Добавить

9) Появится окно Добавление ограничения

10) Укажем ограничения неотрицательность переменных:

11) Нажать кнопку Добавить Остальные ограничения; Нажать OK

Заключение

математический линейный программирование

В компьютерных программах реализуются математические модели и методы.

В курсовой работе проведено исследование задачи линейного программирования и решена в различных компьютерных программах(Microsoft Excel, MSimplex).

В начале дано краткое описание математического метода: “Транспортной задачи”, затем проведено аналитическое решение поставленной задачи о транспортных издержках.

Для быстрого решения в работе была исследована двойственная задача.

Правильность аналитического решения подтверждает компьютерная реализация задачи.

Изменив входные параметры задачи, проведя вычислительный эксперимент, основанный на базе компьютерных программ, пришли к выводу об изменениях основного покупателя-критерий эффективности в сторону роста (если целевая функция на max) и уменьшается (если целевая функция поставлена на min). Решение оптимизационных задач на конкретном примере позволяет обобщить компьютерную реализацию задач класса математического программирования. Строго последовательно, решая оптимизационную задачу, можно разработать методические рекомендации, по практическому применению математических методов и их реализацию на компьютере.

Также данные исследования можно использовать в учебно-методической работе учебных заведений.

Список используемых источников

1)Замков о.о. и др., «математические методы в экономике», учебник мгу, москва, 2004 год.

1) www.reshmat.ru - решение задач онлайн

2) Вентцель е.с., «исследование операций», москва, 1972 год

3) Гельман в.я., «решение математических задач средствами excel.практикум», москва, 2003 год.

4)Малик г.с. «основы экономики и математические методы в планировании», Ростов-на-дону, 2003 год.

Приложения

Приложение A

Решение транспортной задачи, программой Msimplex

Рисунок 2. Результаты вычислений.

Приложение Б

Решение транспортной задачи, программой Excel

Рисунок 3.Расчёт общей задачи

Размещено на Allbest.ru