Оптимизация показателей качества

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

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

Оптимизация показателей качества

Задание №1

Из трех видов сырья производится два вида продукции. Прибыль от реализации одной единицы продукции первого типа составляет б₁ тыс. руб., а второго - б₂ тыс. руб. Запас сырья каждого вида составляет в₁, в₂, в₃ единиц соответственно. Потребность в сырье для изготовления продукции первого типа составляет Р₁₁ единиц сырья первого вида, Р₁₂ единиц сырья второго вида, Р₁₃ единиц сырья третьего вида, а для изготовления продукции второго типа - Р₂₁ единиц сырья первого вида, Р₂₂ единиц сырья второго вида, Р₂₃ единиц сырья третьего вида. Для каждого типа изделий определить такой объем производства Х₁ и Х₂, который обеспечивает максимальную прибыль от реализации изготовленной продукции при условии не превышения запасов имеющегося сырья. Задачу решить симплексным методом путем преобразования симплекс - таблиц.

Исходные данные:

Р₁₁=13 ед.

Р₁₂=9 ед.

Р₁₃=8 ед.

Р₂₁=7 ед.

Р₂₂=10 ед.

Р₂₃=11 ед.

в₁= 120 ед.

в₂= 110 ед.

в₃= 100 ед.

б₁=6 тыс. руб.

б₂=8 тыс. руб.

Решение:

Составим математическую модель задачи. Искомый выпуск продукции 1-го вида обозначим через Х₁, выпуск продукции 2-го вида - Х₂. Т.к. на выделенный предприятию фонд сырья каждого вида имеются ограничения переменные Х₁ и Х₂ должны удовлетворять следующей системе неравенств:

Общая стоимость произведенной предприятием продукции:

F=6х₁+8х₂

По своему экономическому содержанию переменные Х₁ и Х₂ могут принимать только неотрицательные значения:

Х₁, Х₂?0

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

Составим симплекс - таблицу для I итерации (табл. 1).

Таблица 1

Первая итерация.

Шаг 1 (выбор ведущего столбца)

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

Х₁=0, Х₂=0, Х₃=120, Х₄=110, Х₅=100

Не является оптимальным. Из двух положительных элементов нулевой строки выбираем максимальный а₀₂=8 и таким образом второй столбец является ведущим.

Шаг 2 (выбор ведущей строки)

В ведущем столбце имеется три положительных элемента а₁₂=9, а₂₂=10, а₃₂=11.

Сравнивая отношения

выбираем минимальное. Таким образом, третья строка - ведущая, а ведущий элемент - а₃₂.

Шаг 3 (преобразование системы к диагональному виду относительно нового набора базисных переменных)

Ведущий элемент - а₃₂, поэтому переменную Х₅ следует вывести из базиса, а вместо нее ввести переменную Х₂.

Третью строку умножаем последовательно на -8/11, -7/11, -10/11 и получившиеся строки складываем соответственно с нулевой, первой и второй. Все элементы ведущего столбца (кроме ведущего элемента) станут нулевыми и симплекс - таблица во второй итерации примет вид:

Вторая итерация.

Шаг 1.

В нулевой строке имеется единственный положительный элемент а₀₁=2/11 и следовательно ведущий столбец определяется однозначно.

Шаг 2.

В качестве ведущей строки сравнивая отношения коэффициентов

выбираем минимальное. Таким образом, а ведущий элемент - а₁₁=7,13.

Шаг 3

Переменную Х₃ вывести из базиса и ввести переменную Х₁. Для этого первую строку умножаем последовательно на (-2/87), (-19/87), (-8/87) и складывая получившиеся строки соответственно с нулевой, второй и третьей строками придем к оптимальной таблице:

В этой таблице в нулевой строке нет положительных элементов, текущее базовое решение

является оптимальным и соответственно максимальное значение прибыли:

Задание №2

Дана задача нелинейного программирования. Найти максимум и минимум целевой функции графоаналитическим методом. Составить функцию Лагранжа и показать, что в точках экстремума выполняются достаточные условия минимума (максимума).

Исходные данные:

А=1

В=3

Таким образом:

Решение:

Областью допустимых решений задачи является четырехугольник ABCD (рис. 1). Полагая значение целевой функции равным некоторому числу h получаем линии уровня, а именно окружности с центром Е (2; 5) и радиусом . С увеличением (уменьшением) числа h соответственно увеличиваются (уменьшаются) значения функции F.

Минимальное и максимальное значения определим, проводя из точки Е окружности разных радиусов. На рис. 1 видно, что максимальное значение функция принимает в точке D, а минимальное - в т. К.

Определим координаты точки максимума целевой функции как координаты точки пересечения прямых:

Определим координаты точки минимума целевой функции. Для нахождения координаты т. К приравняем угловые коэффициенты прямой и касательной к окружности в т. К.

Из уравнения найдем, что , а угловой коэффициент равен . Угловой коэффициент касательной к окружности в т.К можно получить как значение производной функции Х₂ по переменной Х₁ в этой точке.

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

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

,,,,

,,,.

Таким образом, , .

Задание №3

прибыль лагранж динамический программирование

Двум предприятиям выделяют средства в количестве d единиц. При выделении первому предприятию на год x единиц средств оно обеспечивает доход k₁x единиц, а при выделении второму предприятию у единиц средств, оно обеспечивает доход k₁у единиц. Остаток средств к концу года для первого предприятия равен nx, а для второго my. Как распределить все средства в течение 4-х лет, чтобы общий доход был наибольшим. Задачу решить методом динамического программирования.

Исходные данные:

А=2200

k₁=2

k₂=1

n=0,3

m=0,5

Решение:

Весь период длительностью 4 года разбиваем на 4 этапа, каждый из которых равен одному году. Пронумеруем этапы начиная с первого года. Пусть Х_k и Y_k - средства, выделенные соответственно предприятиям А и В на k - том этапе. Тогда сумма Х_k + Y_k =а_k является общим количеством средств, используемых на k - том этапе и оставшиеся от предыдущего этапа k - 1. на первом этапе используются все выделенные средства и а₁ =2200 ед. доход, который будет получен на k - том этапе, при выделении Х_k и Y_k единиц составит 2Х_k + 1Y_k. пусть максимальный доход, полученный на последних этапах начиная с k - того этапа составляет f_k (а_k) ед. запишем функциональное уравнение Беллмана, выражающее принцип оптимальности: каково бы не было начальное состояние и начальное решение последующее решение должно быть оптимальным по отношению к состоянию, получаемому в результате начального состояния:

f_k (а_k)=max [2х+y + f_k+1 (а_k+1)]

для каждого этапа нужно выбрать значение Х_k, а значение Y_k =а_k - х_k. С учетом этого найдем доход на k - том этапе:

2х_k+y_k=2х_k+ а_k - х_k=х_k+ а_{k n m}

а_k=0,3х_k-1+0,5 y_k-1=0,3х_k-1+0,5 (а_k-1 - х_k-1)= 0,3х_k-1+0,5а_k-1 -0,5 х_k-1=0,5а_k-1-0,2х_k-1

Функциональное уравнение Беллмана будет иметь вид:

f_k (а_k)=max [а_k+х_k+f_k+1(а_k+1)]

Рассмотрим все этапы, начиная с последнего.

При k=4.

F₄ (а₄)=max [а₄+х₄+0]=2а₄, (т.к. максимум линейной функции а₄ + х₄ достигается в конце отрезка [0; а₄] при х₄ = а₄) y₄=х₄-а₄=0.

а₄=0,5а₃-0,2х₃

При k=3.

F₃ (а₃)=max [а₃+х₃+2 (0,5а₃-0,2х₃)]= max (а₃+х₃+а₃-0,4х₃)]= max [2а₃+0,6х₃]=2,6а₃, (т.к. максимум линейной функции 2а₃ +0,6 х₃ достигается в конце отрезка [0; а₃] при х₃ = а₃) y₃=х₃-а₃=0.

а₃=0,5а₂-0,2х₂

При k=2.

F₂(а₂)=max[а₂+х₂+2,6 (0,5а₂-0,2х₂)]=max(а₂+х₂+1,3а₂-0,52х₂)]=

=max [2,3а₂+0,48х₂]=2,78а_2, (т.к. максимум линейной функции 2,3а₂ +0,48 х₂ достигается в конце отрезка [0; а₂] при х₂ = а₂) y₂=х₂-а₂=0.

а₂=0,5а₁-0,2х₁

При k=1.

F₁(а₁)=max[а₁+х₁+2,78 (0,5а₁-0,2х₁)]=max(а₁+х₁+1,39а₁-0,556х₁)]=

=max [2,39а₁+0,444х₁]=2,834а_1, (т.к. максимум линейной функции 2,39а₁ + 0,444 х₁ достигается в конце отрезка [0; а₁] при х₁ = а₁). y₁= а₁ - х₁=0.

Таким образом, максимальный доход за 4-е года составит

F₁(а₁)=2,834*2200=6324,80 ед.

Для получения этого дохода нужно во все четыре года все средства вложить в предприятие А (а₁= х_1, y₁= 0; а₂= х_2, y₂= 0; а₃= х_3, y₃= 0; а₄= х_4, y₄= 0).

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