Государственное образовательное  учреждение

профессионального образования

«ТЮМЕНСКИЙ  ГОСУДАРСТВЕННЫЙ  НЕФТЕГАЗОВЫЙ УНИВЕРСИТЕТ»

КАФЕДРА ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

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

по курсу  «Теория принятия решений»

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

Вариант №29 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Тюмень 2010

Содержание 
 

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

    На  производство поступила партия стержней длиной 250 и 190 см, причем количество стержней длиной 250 см ограничено и равно 200 шт. Из этих стержней необходимо получить 470 заготовок длиной 120 см и 450 заготовок длиной 80 см. Как следует разрезать стержни, чтобы количество отходов было минимальным? 

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

Математическая  формулировка

j —индекс вида стержня, j = 1,..., n;

k —индекс вида заготовки, k = 1, ..., q;

i — индекс способа раскроя стержня, i = 1,..., p;

а_ijk — количество (целое число) заготовок вида k, полученных при раскрое j-го типа стержня i-м способом;

b_k — число заготовок вида k которое требуется получить;

d_j — количество стержней j-го вида;

x_ij — количество стержней j-го типа, раскраиваемых по i-му способу (интенсивность использования способа раскроя);

c_ij — величина отхода, полученного при раскрое стержня j-го типа по i-му способу; 

    Целевая  функция.  Необходимо минимизировать отходы, полученые при раскрое стержней.

    min F = x_ji c_ji, j=1...n, k=1...q 

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

    Ограничение на расход исходных стержней можно записать в следующем виде:

     Это приводит к следующему ограничению:

    (x11_i) ≤ 200; 

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

    (а_ij1 x_ij) = 470;

    (а_ij2 x_ij) = 450; 

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

    x_ij ≥ 0, а_ijk ≥ 0; 

    Итак, математическую модель можно записать следующим образом.

    Определить  интенсивности использования для каждого метода раскроя, при которых достигается минимальное количество отходов:

    min F =         x_ji c_ji, j=1...n, k=1...q  (целевая функция) 

    и которые удовлетворяют условиям 

    (x_i1) ≤ d₁;

    (а_ij1 x_ij) = b₁;

    (а_ij2 x_ij) = b₂; 

    x_ij ≥ 0, а_ijk ≥ 0; 
 

Выбор и обоснование  метода решений поставленной задачи.

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

Решение задачи

Заполним  таблицу методов раскроя 

a для стержней типа j = 1 (250 см)

a для стержней типа j = 2 (190 см)

развернем целевую функцию в соответствии с таблицей раскроя: 

min F = 10x₁₁ + 50x₂₁ + 10x₃₁ + 70x₁₂ + 30x₂₂ 

развернем ограничения  в соответствии с таблицей раскроя: 

x₁₁ + x₂₁ + x₃₁ ≤ 200; 

2x₁₁ + x₂₁ + x₁₂ = 470 

x₂₁ + 3x₃₁ + 2x₂₂ = 450 

x_ji ≥ 0, а_ijk ≥ 0; 

    Решим сформулированную задачу с помощью  симплекс-метода. Для этого запишем  целевую функцию в виде: Z - 10x₁₁ - 50x₂₁ - 10x₃₁ - 70x₁₂ - 30x₂₂ = 0 и запишем исходные данные в симплекс-таблицу. Процесс нахождения оптимального решения приведен в таблице 2.

Таблица 2

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

Возможно улучшение  плана.

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

В пересечении колонок  Х0-Х8(выбирается максимальное положительное  число).

Сначала просматривается  строка помеченная знаком "M-->"

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

Если разрешающий  столбец не нашли, то в таблице представлен оптимальный план.

Разрешающая строка определяется по минимальному не отрицательному отношению

коэффициентов столбца  Х0 и разрешающего столбца(что представлено в столбце Alfa). 

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

    x₁₁ = 200, x₁₂ = 70, x₂₂ = 225_.

Анализ  модели на чувствительность.

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

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

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

    Используя данные, содержащиеся в симплекс-таблице  для оптимального решения, основные результаты можно представить так:

    Таблица 3 

    Статус  ресурсов

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

    Применительно к рассматриваемой задаче можно  привести следующую сводку результатов.

    Таблица 4

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

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

    Ценность  ресурсов

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

    Максимальное  изменение запаса ресурса

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

    Максимальное  изменение коэффициентов  стоимости

    Наряду  с определением допустимых изменений  запасов ресурсов представляет интерес и установление интервала допустимых изменений коэффициентов прибыли или стоимости.

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

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

Список литературы

- Курс  лекций по Теории Принятия Решений //Гапанович И.В. 2010

- Основы теории принятия решений //Орлов А.И.  2002 - 51 с