Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Алгоритм решения задачи о назначениях




 

Алгоритм состоит из трех этапов.

Этап 1:

1. Формализация проблемы в виде транспортной таблицы по аналогии с решением транспортной задачи.

2. В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки.

3. Повторить ту же самую процедуру для столбцов.

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

Этап 2.

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

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

2. Зачеркнуть оставшиеся нулевые значения данного столбца.

3. Пункты 1 и 2 повторять до тех пор, пока продолжение описанной процедуры окажется невозможным. Если на данном этапе окажется, что есть несколько нулей, которым не соответствуют назначения и которые являются незачеркнутыми, то необходимо:

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

5. Зачеркнуть оставшиеся нули в данной строке.

6. Повторять пункты 4 и 5 до тех пор, пока дальнейшая их реализация окажется невозможной.

Если окажется, что таблица содержит неучтенные нули, повторить операции 1-6. Если решение является допустимым, т.е. все элементы распределены в клетки, которым соответствует нулевая стоимость, то полученное решение одновременно является оптимальным. Если решение является недопустимым, осуществляется переход к этапу 3.

Этап 3.

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

2. Найти наименьший среди элементов, через которые не проходит ни одна из проведенных прямых.

3. Вычесть его из всех элементов, через которые не проходят прямые.

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

5. Все элементы матрицы, через которые проходит только одна прямая, оставить без изменения.

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


Задание 2

 

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

В течение месяца предприятие располагает ограниченными ресурсами сырья и времени обработки изделий в производственных цехах. Прибыль от реализации изделия А составляет 100 руб./шт., изделия В – 150 руб./шт.

Продукция/ресурсы Сырье, кг Обработка, станко-час Прибыль, руб.
Цветные металлы Сталь Токарные работы Фрезерные работы
Изделие А          
Изделие В          
Ресурсы          

 

1. Найдите оптимальный план производства (количество изделий А и В), дающий наибольшую прибыль.

2. Проведите анализ решения с использованием двойственных оценок.

Решение:

I. Экономико-математическая модель задачи:

Переменные: -изделие А; - изделие В.

Целевая функция: f () = 100 +150 max

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

, 0


 

1. Строим область допустимых значений (ОДР) ЗЛП:

:      
332,5  
:      
   
    204,4
262,9  
    222,2
   

 

ОДР представлена на рисунке ниже.

Рис. 2.1 – Область допустимых решений

 

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

2. Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными произведениями целевой функции:

=

Чтобы построить такой вектор, нужно соединить точку (100;150) с началом координат.

3. Строим линию уровня, которая является перпендикуляром вектора градиента – см. пунктирную линию.

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

Получаем и . При этих значениях max f () = 100 +150

Вывод: для получения max прибыли (29500) необходимо производить 70 шт изделия А ( =70) и 150 шт изделия В ( =150).

II. Сформулируем двойственную задачу и найдем двойственные оценки.

Целевая функция: g () = 6650 +28000 min

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

, 0

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

Воспользуемся первым соотношением второй теоремы двойственности:

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

Получим:

, так 16900<28000, то

, так 19100<20000, то

Воспользуемся вторым соотношением второй теоремы двойственности:

Если , то

В нашей задаче Х1=70 > 0 и Х2=150 >0, поэтому первое и четвертое ограничения двойственной задачи обращаются в равенства:

Решив систему уравнений, получим:

Проверим выполнение первой теоремы двойственности:

g () = 6650 +28000

f () = 100 +150

Оптимальный план двойственной задачи определен, верно.

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

Если , то

Если , то

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

Сталь используется не полностью 16900<28000, поэтому имеет нулевую двойственную оценку . Этот ресурс не влияет на план получения прибыли.

Необходимый фонд рабочего времени фрезерных работ используется не полностью 19100<20000, поэтому имеет нулевую двойственную оценку . Этот ресурс не влияет на план получения прибыли

Общая прибыль изготовления изделия А 70 и В 150составит 29500 руб

Проверим правильность найденного решения с помощью Microsoft Excel с помощью Пакета Анализа. Представим задачу в файле Excel.

 

В ячейках B8:B9 находятся искомые переменные x1, x2. Целевая функция прибыли определяется формулой "=СУММПРОИЗВ(B8:B9;F3:F4)". Затраты на ресурсы "цветные металлы" занесены в ячейку B14 и определяются формулой "=СУММПРОИЗВ($B$8:$B$9;B3:B4)", протянув эту формулу на ячейки C14, D14, D14 получим расчетные значения затрат на остальные виды ресурсов.

Заполним форму Поиска решений:

Найденное решение примет вид:

Так следует производить 70 ед. изделий А и 150 единиц изделий B. Суммарная прибыль составит 29500 руб. При этом цветные металлы и токарные работы будут использованы в полном объеме, стали останется 11100 кг, а фрезерных работ – 900 станко-часов. Что видно, также из отчета по результатам:

Как видно, решения найденные графически и с помощью средств Microsoft Excel совпадают.


Задание 3

 

Зафиксирован объем продаж Y(t) (тыс. шт.) одного из продуктов фирмы за одиннадцать месяцев. Временной ряд данного показателя представлен в таблице 3.1.

Таблица 3.1. Исходные данные

Номер наблюдения t                      
Объем продаж Y(t) (тыс. шт.)                      

 

1.Постройте график временного ряда, сделайте вывод о наличии тренда.

2. Постройте линейную модель Y(t) = a0 + а1t, оцените ее параметры с помощью метода наименьших квадратов (МНК).

3. Оцените адекватность построенной модели, используя свойства остаточной компоненты e(t).

4. Оцените точность модели на основе средней относительной ошибки аппроксимации.

5. Осуществите прогноз спроса на следующие два месяца (доверительный интервал прогноза рассчитайте при доверительной вероятности P = 75%).

6. Фактические значения показателя, результаты моделирования и прогнозирования представьте графически.

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

Решение:

1. Постройте график временного ряда, сделайте вывод о наличии тренда.

Рис. 3.1 – График временного ряда

 

Тренд – это долговременная компонента ряда динамики. Она характеризует основную тенденцию его развития, при этом остальные компоненты рассматриваются только как мешающие процедуре его определения.

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

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

-делим исходный временной ряд на 2 примерно равные по числу уровней части: N1 = 5, N2 = 6.

-для каждой из этих частей вычисляем средние значения и дисперсии – используем встроенные возможности Microsoft Excel - Пакет Анализа, Двухвыборочный F-тест для диспрсии:

-проверяем гипотезу о равенстве дисперсий обеих частей ряда с помощью F-критерия Фишера. Так нулевая гипотеза будет иметь вид: H0: , альтернативная гипотеза H1: . F-статистика определяется формулой:

Критическое значение статистики составит Fкрит = 6,26. Так как Fрасч = 2,10 <Fкрит = 6.26, то нет оснований отвергать нулевую гипотезу H0.

- тогда проверяем основную гипотезу о равенстве сред значение с использованием t-критерия Стьюдента. Так нулевая гипотеза будет иметь вид: H0: , альтернативная гипотеза H1: . t-статистика определяется формулой:

Критическое значение статистики составит tкрит = 2.26. Так как tрасч = 3,927 > tкрит = 2.26, нулевую гипотезу H0 отклоняется и принимается альтернативная гипотеза о том, равенства средних у двух выборок нет. То есть расхождения между вычисленными данными средними статистически значимо. Отсюда вывод, что тренд присутствует.

При проведении теста использовали Двухвыборочный t-тест с одинаковыми дисперсиями:

2. Построим линейную модель Y(t) = a0 + а1t, оценим ее параметры с помощью метода наименьших квадратов (МНК).

В таблице 3.2 приведены промежуточные расчеты параметров линейной модели по следующим формулам:

Подставляем значения и в Y (t) = + t: . Расчеты приведены в таблице 3.2.

Таблица 3.2. Вспомогательная таблица

  t y
      -5   -13,73 188,44 68,64 32,6
      -4   -11,73 137,53 46,91 35,4
      -3   -6,73 45,26 20,18 38,2
      -2   -5,73 32,80 11,45 41,1
      -1   -1,73 2,98 1,73 43,9
          0,27 0,07 0,00 46,7
          -1,73 2,98 -1,73 49,6
          4,27 18,26 8,55 52,4
          8,27 68,44 24,82 55,2
          12,27 150,62 49,09 58,0
          16,27 264,80 81,36 60,9
Сумма         0,00 912,18 311,00 514,00
Среднее значение   46,73     0,00 82,93 28,27 46,73

 

Продолжение таблицы 3.2

  Точки поворота
  0,41   0,167 -   0,01240
  -0,42 * 0,175 -0,827 0,684 0,01195
  1,75 * 3,078 2,173 4,721 0,04386
  -0,07   0,005 -1,827 3,339 0,00177
  1,10 * 1,210 1,173 1,375 0,02444
  0,27   0,074 -0,827 0,684 0,00580
  -4,55 * 20,744 -4,827 23,303 0,10121
  -1,38   1,909 3,173 10,066 0,02709
  -0,21   0,044 1,173 1,375 0,00380
  0,96   0,929 1,173 1,375 0,01633
  2,14   4,564 1,173 1,375 0,03391
Сумма 0,00   32,90 1,727 48,30 0,2826
Среднее значение - - - - - -
               

 

3. Оценим адекватность построенной модели, используя свойства остаточной компоненты e(t). Промежуточные вычисления представлены в таблице 3.2

· Свойства независимости остаточной компоненты, или наличия (отсутствия) автокорреляции в отклонениях от моделей роста, осуществляется с помощью критерия Дарбина-Уотсона по формуле:

,

где

Результаты расчетов приведены в таблице 3. 2. Таким образом:

; =1,36; dw ’=4- dw =4-1,47=2,53.

Так как dw ’=1,53 попало в интервал от до 2, то по данному критерию можно сделать вывод о выполнении свойства независимости остатков. Это означает, что в ряде динамики отсутствует автокорреляция, следовательно, модель по этому критерию адекватна.

· Проверка условия случайности возникновения от тренда с помощью критерия поворотных точек. Значение случайной переменной считается поворотной точкой, если оно одновременно больше соседних с ним элементов, или, наоборот меньше значений предыдущего и последующего за ним члена. Количество поворотных точек p при n=11 равно 4. Количество поворотных точек сравнивается с величиной, заключенной в квадратные скобки.

.

Неравенство выполняется (4>3). Следовательно, свойство случайности выполняется. Модель по этому критерию адекватна.

· Соответствие ряда остатков нормальному закону распределения определим с помощью RS-критерия:

, где а среднее квадратичное отклонение = =1,91

Получаем

Расчетное значение попадает в интервал (2,7; 3,7), следовательно, выполняется свойство нормальности распределения. Модель по этому критерию адекватна.

Данные анализа ряда остатков приведены в таблице 3.3.

 

Таблица 3.3. Проверка адекватности модели

Проверяемой свойство Используемая статистика Граница Вывод
наименование значение нижняя верхняя
Независимость dw- критерий Дарбина-Уотсона   1,08 1,36 адекватна
Случайность Критерий пиков(поворотных точек) 5>3   адекватна
Нормальность 3,50 2,7 3,7 адекватна
Вывод: модель статистически адекватна

 

4. Оценим точность модели на основе средней относительной ошибки аппроксимации. Результаты вспомогательных вычислений представлены в таблице 3.2.

Получаем

Вывод: % - уровень точности модели приемлемый.

5. Осуществим прогноз спроса на следующие два месяца (доверительный интервал прогноза рассчитайте при доверительной вероятности P = 75%).

· для вычисления точечного прогноза в построенную модель подставляем соответствующее значение фактора t=n+k

(n+k)

;

· Для построения интервального прогноза рассчитаем доверительный интервал. При уровне значимости, а=0,25, доверительная вероятность равна 75%, а критерий Стьюдента при ν=n-2=9 равен tкрит = 1,23. Ширину доверительного интервала вычислим по формуле:

,

где ,

,

,

.

Получаем

Далее вычисляем верхнюю и нижнюю границы прогноза - см. таблицу 3.3:

+ – верхняя граница

- – нижняя граница

 

Таблица 3.3. Точечный и интервальный прогнозы

t= прогноз верхняя граница нижняя граница
  63,69 60,89 66,49
  66,52 63,60 69,43

 

6. Фактические значения показателя, результаты моделирования и прогнозирования представьте графически - см. рис. 3.2.

Рис. 3.2 – Фактические уровни ряда и результат моделирования

 

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

· Щёлкните правой кнопкой мыши на ряде динамики

· Выберите команду Добавить линию тренда из контекстного меню

· Выберите тип регрессии. При выборе типа Полиноминальная введите значение степени в поле Степень

· В параметрах отметить:

-показывать уравнение на диаграмме

-поместить на диаграмму величину достоверности аппроксимации

· Щелкните Ок.

Экспоненциальная линия тренда

Рис. 3.3 – Экспоненциальная линия тренда

Логарифмическая линия тренда

Рис. 3.4 – Логарифмическая линия тренда

 

Полиномиальная линия тренда

 

Рис. 3.5 – Полиномиалная линия тренда

 

Степенная линия тренда

 

Рис. 3.6 – Степенная линия тренда

 

Наилучшей трендовой моделью считается полиномиальная, так как у нее большее значение коэффициента детерминации (0,9715). Поэтому полиномиальную модель выбрать в качестве лучшей для построения прогноза. То есть y = 0,0897t2 + 1,7503t + 32,097.

В параметрах при построении линии тренда введем прогнозируемое количество периодов, равное два интервала вперед:

 

Рис. 3.7 – Исходные данные, полиномиальная линия тренда и прогноз на два периода вперед

 


Задание 4

 

На склад компании пиломатериалы доставляются партиями по 1500 т. Потребители забирают со склада 100 т пиломатериалов в сутки. Накладные расходы по доставке партии пиломатериалов равны 3000 руб. Издержки хранения 1 т пиломатериалов в течение суток составляют 0,2 руб.

Определите оптимальный размер заказываемой партии. Постройте график общих годовых затрат при оптимальном размере партии. Рассчитайте, на сколько дороже обходится доставка пило­материалов партиями по 1500 т?

Дано:

М = 100 т;

h = 0,2 руб./сутки;

K = 3000 руб./зак.;

Определить: Q опт, потери в связи с установленным размером заказа в 1500 т.

Решение.

1. Оптимальный объем заказа составит:

2. Совокупные издержки за сутки:

3. Определим, какую сумму теряет компания в связи с установленным объемом заказа:

4. Частота поставок (количество поставок за год – в месяце 30 рабочих дней):

5. Периодичность поставок (интервал между поставками):

Tp =

то есть одна поставка происходит каждые 17,32 дня.

6. Так как заказ выполняется в течение дня, то точка заказа:

Каждый раз, когда остается 33,3 тонны делается новый заказ на 1732 тонны.

В таблице 4.1 представлен расчет затрат на содержание запасов продукции на складе и заказ новой партии. На рисунке 4.1 представлен график затрат на содержание запасов продукции на складе и заказ новой партии.

Таблица 4.1. Затраты на содержание запасов на складе и затраты на заказ новой партии

Номер дня Остаток продукции на складе Расходы (хранение + заказ), руб.
    3346,4
    326,4
    306,4
    286,4
    266,4
    246,4
    226,4
    206,4
    186,4
    166,4
    146,4
    126,4
    106,4
    86,4
    66,4
    46,4
    26,4
    3352,8
    332,8
    312,8
    292,8
    272,8
    252,8
--- --- ---

 

 

Рис. 4.1 –

Стеклянные сосуды
График общих затрат при оптимальном размере заказа

 

Таким образом, оптимальный размер заказа составляет 1732 т. Совокупные издержи за сутки составляют 346,4 руб. Компания в связи с установленным объемом заказа 1500 т. теряет 53,6 руб./сутки.

 

 


Задание 5

 

Девять экспертов оценили спрос на малолитражные автомобили в городе N (тыс. шт.) - см. таблицу 5.1.

Таблица 5.1. Исходные данные

Эксперт                  
Прогноз 2,8 5,6 3,2 4,8     2,5 3,7 3,9

 

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

Решение:

Применим метод статистической обработки результатов экспертизы. Алгоритм данного метода включает расчет следующих показателей:

1. Рассчитывается точечная оценка результатов экспертных оценок Bi, полученных при опросе экспертов на основе средней арифметической

3,9 тыс. шт.,

где xi – значение прогнозируемой величины, данное i-м экспертом;

n – число экспертов в группе.

2. Определяется дисперсия:

8.60/9=0.956

Также можно воспользоваться функцией Microsoft Excel ДИСПР().

3. Рассчитывается приближенное значение доверительного интервала по формуле:

j =

где t – коэффициент Стьюдента для заданного уровня значимости и числа степеней свободы k = n – 2.

4. Определяются доверительные границы для прогнозируемого показателя:

– для верхней границы Ав= + j,

– для нижней границы Ан= – j.

Так в нашем случае значение t-статистики Стьюдента составит t = 2.36. Использовали функцию "=СТЬЮДРАСПОБР(0,05;7)". Число степеней свободы равно 7, а уровень доверительной вероятности выбран 0,95.

Тогда приближенное значение полудлины доверительного интервала составит:

j = =2.31 тыс. шт.

Тогда нижняя граница доверительного интервала составит 1,63 (3,94 - 2,31 = 1,63), а верхняя граница составит 6,25 (3,94 + 2,31 = 6,25).

Таким образом, точечный прогноз спроса на малолитражные автомобили составит 3,94 тыс. шт., а интервальный от 1,63 до 6,25 тыс. шт.


Список использованной литературы

 

1. Гармаш А.Н., Орлова И.В. Математические методы в управлении: учебное пособие/ под ред А.Н.Гармаш.-М.: Вузовский учебник: ИНФРА-М, 2012.

2. Орлова И.В., половников В.А. Экономико-математическое методы: Компьютерное моделирование: учебное пособие/ под ред. И.В.Орловой-3-е изд., перераб. и доп..-М.: Вузовский учебник: ИНФРА-М, 2012.

3. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач: учебное пособие/ под ред И.В.Орловой-2-е изд., исп. и доп..-М.: Вузовский учебник: ИНФРА-М, 2012.

4. Федосеев В.В. Гармаш А.Н., Орлова И.В. Экономико-математические методы и прикладные модели: учебник для бакалавров/под ред. В.В.Федосеева.-3-е изд., перераб. и доп.-М.: Юрайт,2012

5. Федосеев, В. В. Экономико-математические методы и прикладные модели [Электронный ресурс]: Учеб. пособие для вузов / В. В. Федосеев, А. Н. Гармаш, И.В. Орлова и др.; Под ред. В. В. Федосеева. - 2-е изд., перераб. и доп. - М.: ЮНИТИ-ДАНА, 2012. - 304 с.

6. Федосеев, В. В. Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / В. В. Федосеев, А. Н. Гармаш, Д.М.Дайитбегов и др.; Под ред. В. В. Федосеева. - М.: ЮНИТИ-ДАНА, 2001. - 391 с

7. Хуснутдинов Р.Ш. Экономико-математические методы и модели: Учебное пособие / Р.Ш. Хуснутдинов. - М.: НИЦ Инфра-М, 2013. - 224 с.

8. http://emm.ostu.ru/lect/lect2_3.html#vopros5

9. http://nashaucheba.ru/v55495

 

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...