Автор работы: Пользователь скрыл имя, 31 Марта 2014 в 19:32, курсовая работа
Задача целочисленного программирования может быть сформулирована на языке математики, если множество доступных вариантов удается описать с помощью математических соотношений (равенств, неравенств, уравнений), а каждое решение - оценить количественно с помощью некоторого показателя, называемого целевой функцией. Тогда наилучшим решением будет то, которое доставляет целевой функции наибольшее или наименьшее значение, в зависимости от содержательного смысла задачи. Так, например, при инвестировании ограниченной суммы средств в несколько проектов естественной является задача выбора тех проектов, которые могут принести в будущем наибольшую прибыль. При доставке в магазины продукции от различных поставщиков возникает задача минимизации транспортных затрат.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (60 : 1/2 , 1200 : 20 , 1800 : 25 ) = 60
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (20) и находится на пересечении ведущего столбца и ведущей строки.
Сi |
Xi |
Bj |
4 |
3 |
0 |
0 |
0 |
||
х1 |
х2 |
х3 |
х4 |
х5 | |||||
II |
4 |
Х1 |
60 |
1 |
1/2 |
1/40 |
0 |
0 |
120 |
0 |
Х4 |
1200 |
0 |
20 |
-1/2 |
1 |
0 |
60 | |
0 |
Х5 |
1800 |
0 |
25 |
-1/4 |
0 |
1 |
72 | |
f |
240 |
0 |
-1 |
1/10 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 2 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=20
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Получаем симплекс таблицу:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x1 |
30 |
1 |
0 |
3/80 |
-1/40 |
0 |
x2 |
60 |
0 |
1 |
-1/40 |
1/20 |
0 |
x5 |
300 |
0 |
0 |
3/8 |
-5/4 |
1 |
F(X2) |
300 |
0 |
0 |
3/40 |
1/20 |
0 |
Таблица 3. Шаг III
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Сi |
Xi |
Bj |
4 |
3 |
0 |
0 |
0 | |
х1 |
х2 |
х3 |
х4 |
х5 | ||||
III |
4 |
Х1 |
30 |
1 |
0 |
3/80 |
-1/40 |
0 |
3 |
Х2 |
60 |
0 |
1 |
-1/40 |
1/20 |
0 | |
0 |
Х5 |
300 |
0 |
0 |
3/8 |
-5/4 |
1 | |
f |
300 |
0 |
0 |
3/40 |
1/20 |
0 |
В итоговой строке отсутствуют отрицательные числа, следовательно, это будет оптимальным решением по критерию оптимальности.
4 АНАЛИЗ РЕШЕНИЯ
В курсовой работе рассмотрен вариант решений оптимизационных экономических задач методами линейного программирования.
Поскольку все f положительно/равны нулю – задача имеет оптимальное решение:
Игрушка А 4руб. (х1=30шт)
Игрушка В 3руб. (х2=60шт)
F(X) = 4•30 + 3•60 = 300
В оптимальный план вошла дополнительная переменная x5. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 300
Значение 0 в столбце x1 означает, что использование x1 - выгодно.
Значение 0 в столбце x2 означает, что использование x2 - выгодно.
Значение 3/40 в столбце x3 означает, что теневая цена (двойственная оценка) равна 3/40.
Значение 1/20 в столбце x4 означает, что теневая цена (двойственная оценка) равна 1/20.
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ А
Базис |
4 |
3 |
0 |
0 |
0 |
|||
Ci |
Xi |
Bj |
X1 |
X2 |
X3 |
X4 |
X5 |
|
0 |
X3 |
2400 |
40 |
20 |
1 |
0 |
0 |
60 |
0 |
X4 |
2400 |
20 |
30 |
0 |
1 |
0 |
120 |
0 |
X5 |
2400 |
10 |
30 |
0 |
0 |
1 |
240 |
f |
0 |
-4 |
-3 |
0 |
0 |
0 |
||
4 |
X1 |
60 |
1 |
1/2 |
1/40 |
0 |
0 |
120 |
0 |
X4 |
1200 |
0 |
20 |
-1/2 |
1 |
0 |
60 |
0 |
X5 |
1800 |
0 |
25 |
-1/4 |
0 |
1 |
72 |
f |
240 |
0 |
-1 |
1/10 |
0 |
0 |
||
4 |
X1 |
30 |
1 |
0 |
3/80 |
-1/40 |
0 |
|
3 |
X2 |
60 |
0 |
1 |
-1/40 |
1/20 |
0 |
|
0 |
X5 |
300 |
0 |
0 |
3/8 |
-5/4 |
1 |
|
f |
300 |
0 |
0 |
3/40 |
1/20 |
0 |
||