Автор работы: Пользователь скрыл имя, 03 Июня 2012 в 23:32, курсовая работа
Завод шампанских вин «Новый свет» производят виноградное сусло из трех сортов винограда – мускатное, столовое и изабелла.
Смешивают их согласно рецептам, устанавливающим максимум или минимум процентного содержания сусла мускатного и изабелла для каждого вида шампанского.
Компания стремится к получению максимальной прибыли ежедневно.
Инструкция по составлению смесей
Введение……………………………………………………………….
Задание…………………………………………………………………
Метод решения………………………………………………………...
Выполнение……………………………………………………………
Вывод…………………………………………………………………..
Использованная литература………………………………………….
Из отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине, что и определяет ведущий столбец, который показывает, какая переменная на следующей итерации перейдет из свободных в базисные. Затем элементы столбца свободных членов симплексной таблицы делим на элементы того же знака (+/+; —/_) ведущего столбца. Результаты заносим в отдельный столбец δi, которые будут всегда положительные. Строка симплексной таблицы, соответствующая минимальному значению δi является ведущей. Она определяет переменную xi которая выйдет из базиса и станет свободной. Элемент симплексной таблицы, находящийся на пересечении ведущих столбца и строки, называют разрешающим и выделяют кружком.
Переход к новому плану осуществляется пересчетом симплексной таблицы методом Жордана — Гаусса. Сначала заменим переменные в базисе, т.е. вместо xi в базис войдет переменная хj соответствующая ведущему столбцу. Разделим все элементы ведущей строки предыдущей симплексной таблицы на разрешающий элемент и результаты деления занесем в строку следующей симплексной таблицы, соответствующую введенной в базис переменной xj.
В результате этого на месте разрешающего элемента в следующей симплексной таблице будем иметь 1, а в остальных клетках j столбца, включая клетку столбца индексной строки, записываем нули. Далее возвращаемся ко второму этапу - проверке плана на оптимальность.
При решении задачи линейного программирования на минимум целевой функции признаком оптимальности плана являются отрицательные значения всех коэффициентов индексной строки симплексной таблицы. Если в ведущем столбце все коэффициенты aij≤0, то функция цели F( ) не ограничена на множестве допустимых планов, т.е. F( ) → ¥ и задача не имеет решения. Если в столбце δi симплексной таблицы содержатся два или несколько одинаковых наименьших значения, то новый опорный план будет вырожденным (одна или несколько базисных переменных станут равными нулю). Для выбора ведущей строки в этом случае используют метод Креко, который заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения δi делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам.
Например, таблица, содержащая три равных значения
δi = 2, имеет вид:
План |
Базисные переменные |
Значения базисных переменных |
x1 |
x2 |
x3 |
x4 |
x5 |
х6 |
х7 |
δi |
II |
х4 |
4 |
2 |
3 |
6 |
1 |
0 |
0 |
1 |
4/2=2 |
х5 |
8 |
4 |
8 |
1 |
0 |
1 |
0 |
4 |
8/4=2 | |
х6 |
10 |
5 |
12 |
—1 |
1 |
0 |
1 |
5 |
10/5=2 |
Допустим, разрешающим столбцом является x1, который вводится в новый план, тогда разрешающим элементом может быть: 2,4 или 5.
По указанному правилу, получится таблица:
Значения базисных переменных |
x1 |
x2 |
x3 |
x4 |
x5 |
х6 |
х7 |
|
2 |
1 |
1,5 |
3 |
0,5 |
0 |
0 |
1 |
2 |
1 |
2 |
0,25 |
0 |
0,25 |
0 |
1 |
2 |
1 |
2,4 |
-0,2 |
0,2 |
0 |
0,2 |
1 |
Сравниваем последовательно слева направо полученные частные по столбцам. В первом и втором столбцах все частные одинаковы, а в третьем столбце наименьшее частное 1,5 в первой строке. Следовательно, эта строка и будет разрешающей с разрешающим элементом 2. Если в оптимальный план вошла дополнительная переменная xn+1, то при реализации такого плана имеются недоиспользованные ресурсы i-го вида в количестве, полученном в столбце свободных членов таблицы. Если в индексной строке симплексной таблицы оптимального плана находится нуль, принадлежащий свободной переменной, не вошедшей в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов. Свободную переменную, соответствующую указанному столбцу, можно внести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных.
Выполнение .
Введем переменные
х1 – «Мускатное»,
х2- «Старый свет»,
х3 – «Крымское»
Запишем математическую модель задачи.
F(x)=68х1+57х2+45х3-70*(0,6х1+
=68х1+57х2+45х3-42х1-10,5х2-
=8х1+10х2+0х3
F(х)= 8х1+10х2+0х3
Запишем количество ограничения :
0,6х1+0,15х2+0х3 ≤ 2000
0,2х1+0,6х2+0,5х3 ≤ 1200
0,2х1+0,25х2+0,5х3 ≤ 2500
Информация о работе Курсовая работа по "Математическое моделирование"