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

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

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

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

 
 
 
 
 
 
 
 
 
 
 
 

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

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

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

Вариант №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).