Управление качеством в производственно-технологических системах

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

Контрольная работа

Методы принятия оптимальных решений

Управление качеством в производственно-технологических системах

Задача 1

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

Решить графически

min F = 2x₁ - 6x₂;

Решение: Построим в осях Х₁ОХ₂ граничные прямые, соответствующие исходным неравенствам. Каждая из этих прямых делит плоскость на две части, одна из которых удовлетворяет неравенству. Подставив в неравенство координаты любой точки, например (0;0), находим эту полуплоскость (отмечено стрелками). В результате получена область ОДР, ограничивающая часть плоскости, удовлетворяющую всем ограничениям - это область допустимых решений - ОДР (заштриховано). Следует отметить, что ОДР не ограничена в сторону бесконечно больших значений х₁ и х₂.

Целевая функция в виде нулевой линии уровня F₀ проходит через начало координат. Если перемещать эту линию в направлении вектора - вниз, скользя началом линии по оси х₁, то значения целевой функции будут возрастать от нуля до бесконечности при х₂ = 0. Если её перемещать в противоположном направлении, скользя началом линии по прямой -х₁ + х₂ = 1, то значения целевой функции будут уменьшаться от нуля до бесконечности при х₁ ? x₂ - 1.

Т.к. условием задано найти минимум, то получим решение задачи в виде:

Если бы ограничения в условии были записаны так:

то ОДР превратилась бы в четырёхугольник ОАВС, минимум функции был бы в точке В с координатами х₁ = 1; х₂ = 1,5 и целевая функция приобрела бы значение:

F_min = 2x₁ - 6x₂ = 2•1 - 6•1,5 = -7;

Соответственно максимум функции оказался бы в точке С (2; 0).

F_max = 2x₁ - 6x₂ = 2•2 - 6•0 = 4;

Задача 2

Для производства 4-х видов продукции используется 3 вида сырья. Нормы расхода сырья (кг) запасы (кг) его ценность от реализации единицы продукции заданы таблицей.

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

Решение: Обозначим х₁ - выпуск изделия 1; х₂ - выпуск изделия 2; х₃ - выпуск изделия 3; х₄ - выпуск изделия 4.

Т.к. затраты ресурсов не могут превосходить их запасы сi, то математическая модель задачи предстанет в виде:

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

Z = бх₁ + вх₂ + гх₃ + дх₄ = 6х₁ + 7х₂ + 9,5х₃ + 7х₄ > max;

Преобразуем систему неравенств в систему уравнений, введя дополнительные переменные х₅; х₆; х₇, которые дают начальный базис:

Для решения этой системы уравнений составим исходную симплекс-таблицу №1. Здесь по строкам записаны коэффициенты при неизвестных в уравнениях. В верхней строке записаны коэффициенты при целевой функции, а в нижней - оценочной - те же коэффициенты с обратным знаком. Базисные переменные х₄, х₅, х₆ имеют нулевые коэффициенты С_i в целевой функции. Столбец В - свободные члены уравнений.

Т.к. наиболее отрицательная оценка (-9,5) в столбце х₃, то этот столбец выберем в качестве разрешающего столбца.

Отношения свободных членов В к элементам разрешающего столбца В_i/x_i записаны в правом столбце - здесь минимум в строке х₇ - эта строка разрешающая.

На пересечении разрешающего столбца и разрешающей строки стоит разрешающий элемент 12 (выделен). Значение целевой функции Z₀ = 0, т.к. все базисные переменные фиктивны и коэффициенты при них в целевой функции равны нулю.

Вводим в базис переменную х₃ со своей оценкой вместо переменной х₅.

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

где а_ik; а?_ik - старое и новое значение в углу прямоугольника, диагонального разрешающему элементу, а_qp - разрешающий элемент; а_qk; a_ip - другие углы, смежные с разрешающим элементом. Получили таблицу №2.

Здесь значение целевой функции Z₁ = 79,167, но т.к. в строке Z есть отрицательные оценки, это решение не оптимально и значение Z может быть увеличено.

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

Т.о. х₁ = 15,625; х₂ = х₄ = 0; х₃ = 3,125; Zmax = 123,4375.

Значение х₆ = 18,125 указывает величину неиспользованного второго ресурса.

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

Т.о. для получения максимальной прибыли следует производить изделия 1 и 3, отказавшись от производства изделий 2 и 4.

Это же решение может быть получено в MS Excel применением инструмента "поиск решения". Лист Excel с результатами решения представлен ниже:

Здесь показано, что максимум целевой функции ЦФ_макс = 123,4375 при оптимальном решении Х(15,625; 0; 3,125; 0). Ресурс 1 и ресурс 3 использованы полностью (левая и правая части равны между собой), а из ресурса 3 использовано лишь 21,875 ед., т.е. остаток 40 - 21,875 = 18,125 ед.

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

Решение этой задачи получено в нижней строке последней симплекс-таблицы:

Wmin = 123,4375; y₁ = 1,0625; y₂ = 0; y₃ = 0,7031.

Проверка:

Wmin = 50•1,0625 + 40•0 + 100•0,70313 = 123,438 = Zmax.

Задача 3

Четыре предприятия данного экономического района для производства продукции использует три вида сырья. Потребности в сырье каждого из предприятий соответственно равны b₁, b₂, b₃ и b₄ ед. Сырье сосредоточено в трёх местах его получения, а запасы соответственно равны a₁, a₂, a₃ ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

;

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

Решение: Проверим задачу на соответствие ресурсов и потребностей:

A_i = 90 + 110 + 100 = 300; В_i = 120 + 50 + 80 + 50 = 300.

Т.к. А_i = В_i, то это транспортная задача закрытого типа.

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

Минимальная стоимость (2) в клетках А₁В₃ и А₃В₂ - закрываем потребности В₃ и В₂ поставкой из А₁ и А₃ и столбцы В₂ и В₃ исключаем из дальнейшего рассмотрения. Следующий минимум в не исключённых столбцах и строках (3) в клетке А₂В₁ - весь груз из А₂ отправляем потребителю В₁ и строку А₂ исключаем из дальнейшего рассмотрения. Следующий минимум (4) в клетке А₁В₄ - остаток груза из А₁ отправляем потребителю В₄ и строку А₁ исключаем из дальнейшего рассмотрения. Осталось лишь 50 единиц груза у поставщика А₃, которые распределяем между потребителями В₁ и В₄, закрывая их потребности.

Опорный план составлен. Число заполненных клеток должно быть:

m + n - 1 = 3 + 4 - 1 = 6,

Фактически число заполненных клеток 6, т.е. план не вырожден.

Цена этого плана:

Z₁ = 80•2 + 10•4 + 110•3 + 10•10 + 50•2 + 40•7 = 1010.

Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U₁ = 0. Потенциалы других строк и столбцов определяем по формулам:

U_i = C_ij - V_j; V_j = C_ij - U_i,

где C_ij - стоимость перевозок, записанная в правом верхнем углу клеток.

V₃ = C₁₃ - U₁ = 2 - 0 = 2; V₄ = C₁₄ - U₁ = 4 - 0 = 4; U₃ = C₃₄ - V₄ = 7 - 4 = 3;

V₁ = C₃₁ - U₃ = 10 - 3 = 7; V₂ = C₃₂ - U₃ = 2 - 3 = -1; U₂ = C₂₁ - V₁ = 3 - 7 = -4;

Определяем характеристики клеток, оставшихся свободными по формуле:

E_ij = C_ij - (V_j + U_i): (вписаны в левый нижний угол):

Е₁₁ = С₁₁ - (V₁ + U₁) = 6 - (7 + 0) = -1;Е₁₂ = С₁₂ - (V₂ + U₁) = 7 - (-1+ 0) = 8;

Е₂₂ = С₂₂ - (V₂ + U₂) = 5 - (-1 - 4) = 10; Е₂₃ = С₂₃ - (V₃ + U₂) = 9 - (2 - 4) = 11;

Е₂₄ = С₂₄ - (V₄ + U₂) = 8 - (4 - 4) = 8;Е₃₃ = С₃₃ - (V₃ + U₃) = 6 - (2 + 3) = 1;

Среди характеристик свободных клеток есть одна отрицательная в клетке Е₁₁ = -1, следовательно, полученный план не оптимален и затраты на его реализацию могут быть уменьшены.

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

Получаем новый план. Его цена:

Z₂ = 10•6 + 80•2 + 110•3 + 50•2 + 50•7 = 1000.

что лучше первоначального плана на 10 ден. единиц.

Т.к. теперь число заполненных клеток оказалось равно 5, что меньше m + n - 1 = 6, то план стал вырожденным. Для устранения вырожденности плана вписываем в клетку А₁В₄ значение 0.

Определив потенциалы строк и столбцов (U₁ = 0) и характеристики свободных клеток по тем же формулам, устанавливаем, что этот план оптимален, т.к. среди характеристик свободных клеток нет отрицательных.

Zопт = Z_min = Z₂ = 1000.

Т.о. оптимальный план перевозок:

Задача 4

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

Решение: Построим в осях Х₁ОХ₂ граничные прямые, соответствующие исходным неравенствам. Каждая из этих прямых делит плоскость на две части, одна из которых удовлетворяет неравенству. Подставив в неравенство координаты любой точки, например (0;0), находим эту полуплоскость (показано стрелками). В результате получен четырёхугольник ОАВС, ограничивающий часть плоскости, удовлетворяющую всем ограничениям - это область допустимых решений - ОДР (заштрихован). Точка В - точка пересечения прямых, заданных уравнениями системы ограничений.

Уточним границу области допустимых решений задачи целочисленного программирования. Для этого придадим переменной х₁ целочисленные значения от 0 до 6 (значение х₁ = 7 уже вне ОДР) и вычислим соответствующие значения х₂ из обеих уравнений.

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

Целевая функция в виде нулевой линии уровня проходит через начало координат. Перемещая эту линию параллельно самой себе в направлении вектора , увеличиваем значение F. Узел этой ступенчатой линии, через которую проходит последняя линия уровня, определит наибольшее значение целевой функции. Этой вершиной оказалась точка L, координаты которой Е(6; 0).

Т.о. значения х₁ = 6 и х₂ = 0 обеспечивают максимальное значение целевой функции в целых числах:

Задача 5

Целочисленное линейное программирование.

На предприятии производятся изделия четырёх наименований, обладающие различной ценностью. В производственном процессе используются три вида сырья. Информация о ресурсе сырья, о нормах их расхода на единичное изделие и ценности изделий приведена в табл. 1:

Решение: Обозначим х₁ - выпуск изделия 1; х₂ - выпуск изделия 2; х₃ - выпуск изделия 3; х₄ - выпуск изделия 4.

Т.к. затраты ресурсов не могут превосходить их запасы с_i, то математическая модель задачи предстанет в виде:

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

Z = бх₁ + вх₂ + гх₂ + дх₂ = 6х₁ + 7х₂ + 9,5х₃ + 7х₄ > max;

Преобразуем систему неравенств в систему уравнений, введя дополнительные переменные х₅; х₆; х₇, которые дают начальный базис:

Т.к. исходные данные те же, что и в задаче 3.6. то приведём сразу матрицу её решения:

Т.о. х₁ = 15,625; х₂ = х₄ = 0; х₃ = 3,125; Zmax = 123,4375.

Т.к. требуется целочисленное решение, то округлим полученные значения в меньшую сторону до х₁ = 15 и х₃ = 3, тогда:

Z = 15?6 + 9,5?3 = 118,5.

Максимально ли это решение в целочисленном исчислении?

Наибольшая дробная часть 0,625 имеется в значении переменной х₁, поэтому для строки х₁ последней симплекс-таблицы составляем дополнительное ограничение:

х₁ + 2,406х₂ + 1,118х₄ + 0,375х₅ - 0,031х₇ ? 15,625;

Берём только дробные части чисел. Для числа (-0,031) дробная часть [-0,031-(-1) = 0,969].

Т.о. получаем дополнительное ограничение:

0,406х₂ + 0,118х₄ + 0,375х₅ + 0,969х₇ - х₈ = 0,625;

При этом

Для решения можно применить метод Гомори с использованием двойственного симплекс-метода, но проще выполнить решение в MS Excel, с применением инструмента "поиск решения", задав дополнительное ограничение по целочисленности переменных.

Лист Excel с полученным решением представлен ниже.

Из этой таблицы следует, что в целочисленном решении переменные принимают значения:

При этом из ресурса 1 израсходовано 48 единиц из 50, из ресурса 2 израсходовано 21 единица из 40, а из ресурса 3 израсходовано 96 единиц из 100, т.е. остаток первого ресурса - 2 ед., второго - 19 единиц, третьего - 4 единицы.

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