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

Федеральное агентство по образованию Российской Федерации

Государственное образовательное учреждение высшего профессионального образования

Северо-Западный Государственный Заочный Технический Университет

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

Курсовая работа

Выполнил студент: Завьялова Н.С.

Факультет:  ФРЭ

Курс: V

Специальность: 1908

Шифр: 25-0138

Проверил:

Санкт-Петербург

2007г.

Задание №1

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

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

Р₁₁=13 ед.

Р₁₂=9 ед.

Р₁₃=8 ед.

Р₂₁=7 ед.

Р₂₂=10 ед.

Р₂₃=11 ед.

β₁= 120 ед.

β₂= 110 ед.

β₃= 100 ед.

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

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

Решение:

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

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

F=6х₁+8х₂

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

Х₁, Х₂≥0

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

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

Таблица 1

		Х1	Х2	Х3	Х4	Х5
Y	0	6	8	0	0	0
Х3	120	13	7	1	0	0
Х4	110	9	10	0	1	0
Х5	100	8	11*	0	0	1

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

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

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

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

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

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

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

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

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

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

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

		Х1	Х2	Х3	Х4	Х5
Y	-800/11	2/11*	0	0	0	-8/11
Х3	620/11	87/11	0	1	0	-7/11
Х4	210/11	19/11	0	0	1	-10/11
Х2	100/11	8/11	1	0	0	1/11

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

Шаг 1.

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

Шаг 2.

В качестве ведущей строки сравнивая отношения коэффициентов  выбираем минимальное. Таким образом, а ведущий элемент – а₁₁=7,13.

Шаг 3

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

		Х1	Х2	Х3	Х4	Х5
Y	-68360/957	0	0	-2/87	0	-682/957
Х1	620/87	1	0	11/87	0	-7/87
Х4	6490/957	0	0	-19/87	1	-737/957
Х2	3740/957	0	1	-8/87	0	143/957

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

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

           

Задание №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,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а₁ , (т.к. максимум линейной функции 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).