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

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

Министерство образования Российской Федерации

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Пояснительная записка к курсовому проекту

по дисциплине «Программирование»

«Анализ решения задачи линейного программирования на чувствительность к параметрам модели»

Выполнил:

студент ТМЦДО

Студент гр. з-430-а

Ихиянов Наиль Фанузович

«___»________2014 г.

2014

Содержание

Введение

. Постановка задачи

. Построение математической модели

. Решение задачи симплекс-методом

. Графическое решение задачи

. Решение задачи с помощью надстройки SOLVER

. Основы анализа на чувствительность

.1 Анализ изменений запасов ресурсов

.2 Определение наиболее выгодного ресурса

.3 Определение пределов изменения коэффициентов целевой функции

Выводы

Литература

Введение

Исследование операций - научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами.

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

При решении конкретной задачи управления применение методов исследования операций предполагает:

·        построение экономических и математических моделей для задач принятия решения в сложных ситуациях или в условиях неопределенности;

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

Примерами задач исследования операций, отражающих его специфику, могут служить следующие задачи:

Ø  задачи об использовании ресурсов (планирование производства)

Ø  задачи о смесях

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

Ø  задачи о раскрое материалов

Ø  транспортные задачи и др.

Приведенные задачи относятся к разным областям практики, но в них есть общие черты: в каждом случае речь идет о каком-то управляемом мероприятии (операции), преследующем определенную цель.

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

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

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

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

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

Модель операции- это достаточно точное описание операции с помощью математического аппарата (различного рода функций, равнений, систем уравнений и неравенств и т.п.).

Эффективность операции - степень ее приспособленности к выполнению задачи - количественно выражается в виде критерия эффективности - целевой функции.

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

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

1. Постановка задачи

Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем первой линии -A=80 изделий, второй линии -B=45 изделий. На радиоприемник первой модели расходуется C=18 однотипных элементов электронных схем, на радиоприемник второй модели-D=14 таких же элементов. Максимальный суточный запас используемых элементов равен E=900 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны Q=30 и P=20 ед. соответственно. Определите оптимальные суточные объемы производства первой и второй моделей на основе графического решения задачи.

Необходимо рассмотреть три задачи анализа полученного решения на чувствительность к принятой модели и на основании полученных результатов:

·        Определите предел увеличения производительности первой линии, превышение которого уже не будет улучшать значения целевой функции;

·        Определите предел уменьшения производительности второй линии, при котором полученное оптимальное решение останется неизменным;

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

·        Определить дефицитный ресурс, который имеет наибольший приоритет при возможности увеличения запасов ресурсов;

·        Определите интервал изменения прибыли от продажи радиоприемника первой модели, в котором оптимальное решение остается неизменным;

·        Определите аналогичный интервал для приемника второй модели.

·        Переменные

·        Целевую функцию

·        ограничения

.        Переменные

Х1- суточное количество произведенных приемников модели №1

Х2- суточное количество произведенных приемников модели №2

.        Целевая функция (ЦФ)

Цель предприятия получение максимальной прибыли

3.      Ограничения:

·        На производство приемников двух моделей расходуются элементы электронных схем, суточный запас которых ограничен и составляет 900 ед., так как на производство 1 модели приемника первого типа необходимо затратить 18 ед. элементов электронных схем, а на производство одного радиоприемника второго типа необходимо 14 ед., то при производстве х1 и х2, расход элементов электронных схем составит:

·        Мощность первой линии позволяет производить не более 80 радиоприемников первой модели в сутки:

·        Мощность второй линии позволяет производить не более 45 радиоприемников второй модели в сутки:

·        Неотрицательность переменных:

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

3.Решение задачи симплекс-методом

От неравенств ограничений переходим к ограничениям равенствам.

Переменные х3,х4,х5 - базисные, а x1, x2 -свободные.

Заполним 1-ую симплекс таблицу

Находим базисное решение, для этого все свободные переменные приравниваем к 0, а базисные к bi:

Х0=(0; 0; 900; 80; 45)

L0=30*0+20*0=0

Находим оценки плана и помещаем в строку :

Так как 2 вектора А1, А2 имеют отрицательную оценку плана, то решение не оптимальное.

Решаем какой из двух векторов выгоднее ввести в базис.

Функция цели меняется по формуле:

Если вводим вектор А1:

Функция цели при вводе вектора А1 изменится на:

=50*(-30)=-1500

увеличится на 1500 единиц

Если вводим вектор А2:

Функция цели при вводе вектора А2 изменится на:

=45*(-20)=-900 увеличится на 900 единиц

Из рассмотренных случаев видно, что при вводе в базис вектора А1 значение ЦФ увеличится больше всего на 1500 единиц. Поэтому в качестве разрешающего столбца берем А1. Разрешающая строка будет та которая отвечает Θ для этого столбца

№ 1 и вектор А3

Меняем А1-А3 и переходим к новой таблице по правилу:

все элементы ведущей строки делим на разрешающий элемент

заполняем базисные столбцы

все остальные элементы симплекс таблицы находим по формуле:

Новое базисное решение

=( 50; 0; 0; 30; 45)

L2(x) = 30*50+20*0=1500

В строке оценок плана все коэффициенты не отрицательны, найденное решение является оптимальным.

Оптимальное решение:

.

Вывод: для получения оптимальной суточной прибыли необходимо производить 50 радиоприемников первой модели (х1=50) , а радиоприемники второй модели не производить (х2=0), так как это приведет к снижению максимальной прибыли. В случае оптимального производства, максимальная суточная прибыль составит 1500 усл.ед.

4. Графическое решение задачи

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

. (I)

 (II)

 (III)

Так как переменные неотрицательны, то рассматриваем только первую четверть.

Строим соответствующие прямые и определяем полуплоскости соответствующие неравенствам.

Для этого возьмем точку M(10;10).

Первое неравенство , таким образом точка удовлетворяет неравенству, значит принадлежит искомой полуплоскости (на графике полуплоскости удовлетворяющие неравенствам покажем стрелками).