Автор работы: Пользователь скрыл имя, 19 Октября 2014 в 21:03, контрольная работа
1. Дана задача линейного программирования при ограничениях:
Графическим методом найти оптимальные решения при стремлении целевой функции к максимальному и минимальному значениям.
Значения коэффициентов целевой функции и системы ограничений.
2. Фирма изготовляет два вида красок для внутренних (В) и наружных (Н) работ. Для их производства используют исходные продукты: пигмент и олифу. Расходы исходных продуктов и максимальные суточные запасы указаны в таблице.
Расходы и суточные запасы исходных продуктов
Исходный продукт Расход исходных продуктов на 1 т краски Суточный запас, т
Краска Н Краска В
Пигмент
Олифа
Изучение рынка сбыта показало, что суточный спрос на краску для наружных (внутренних) работ никогда не превышает т в сутки. Цена продажи 1 т краски для наружных работ ден. ед.
Какое количество краски каждого вида должна производить фирма, чтобы доход от реализации продукции был максимален?
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (256 : 7 , 283 : 16 , - ) = 1711/16
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (16) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
min |
x3 |
256 |
5 |
7 |
1 |
0 |
0 |
364/7 |
x4 |
283 |
6 |
16 |
0 |
1 |
0 |
1711/16 |
x5 |
363 |
7 |
0 |
0 |
0 |
1 |
- |
F(X1) |
0 |
-9 |
-9 |
0 |
0 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 1 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=16
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x2 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (16), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
256-(283 • 7):16 |
5-(6 • 7):16 |
7-(16 • 7):16 |
1-(0 • 7):16 |
0-(1 • 7):16 |
0-(0 • 7):16 |
283 : 16 |
6 : 16 |
16 : 16 |
0 : 16 |
1 : 16 |
0 : 16 |
363-(283 • 0):16 |
7-(6 • 0):16 |
0-(16 • 0):16 |
0-(0 • 0):16 |
0-(1 • 0):16 |
1-(0 • 0):16 |
0-(283 • -9):16 |
-9-(6 • -9):16 |
-9-(16 • -9):16 |
0-(0 • -9):16 |
0-(1 • -9):16 |
0-(0 • -9):16 |
Получаем новую симплекс-таблицу:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x3 |
2115/16 |
19/8 |
0 |
1 |
-7/16 |
0 |
x2 |
283/16 |
3/8 |
1 |
0 |
1/16 |
0 |
x5 |
363 |
7 |
0 |
0 |
0 |
1 |
F(X1) |
2547/16 |
-45/8 |
0 |
0 |
9/16 |
0 |
Итерация №1.
1. Проверка критерия
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (1323/16 : 23/8 , 1711/16 : 3/8 , 363 : 7 ) = 471/6
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (3/8) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
min |
x3 |
1323/16 |
23/8 |
0 |
1 |
-7/16 |
0 |
5525/38 |
x2 |
1711/16 |
3/8 |
1 |
0 |
1/16 |
0 |
471/6 |
x5 |
363 |
7 |
0 |
0 |
0 |
1 |
516/7 |
F(X2) |
1593/16 |
-55/8 |
0 |
0 |
9/16 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x2 в план 2 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x2 плана 1 на разрешающий элемент РЭ=3/8
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x1 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
1323/16-(1711/16 • 23/8):3/8 |
23/8-(3/8 • 23/8):3/8 |
0-(1 • 23/8):3/8 |
1-(0 • 23/8):3/8 |
-7/16-(1/16 • 23/8):3/8 |
0-(0 • 23/8):3/8 |
1711/16 : 3/8 |
3/8 : 3/8 |
1 : 3/8 |
0 : 3/8 |
1/16 : 3/8 |
0 : 3/8 |
363-(1711/16 • 7):3/8 |
7-(3/8 • 7):3/8 |
0-(1 • 7):3/8 |
0-(0 • 7):3/8 |
0-(1/16 • 7):3/8 |
1-(0 • 7):3/8 |
1593/16-(1711/16 • -55/8):3/8 |
-55/8-(3/8 • -55/8):3/8 |
0-(1 • -55/8):3/8 |
0-(0 • -55/8):3/8 |
9/16-(1/16 • -55/8):3/8 |
0-(0 • -55/8):3/8 |
Получаем новую симплекс-таблицу:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x3 |
121/6 |
0 |
-19/3 |
1 |
-5/6 |
0 |
x1 |
283/6 |
1 |
8/3 |
0 |
1/6 |
0 |
x5 |
197/6 |
0 |
-56/3 |
0 |
-7/6 |
1 |
F(X2) |
849/2 |
0 |
15 |
0 |
3/2 |
0 |
1. Проверка критерия
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x3 |
121/6 |
0 |
-19/3 |
1 |
-5/6 |
0 |
x1 |
283/6 |
1 |
8/3 |
0 |
1/6 |
0 |
x5 |
197/6 |
0 |
-56/3 |
0 |
-7/6 |
1 |
F(X3) |
849/2 |
0 |
15 |
0 |
3/2 |
0 |
Оптимальный план можно записать так:
x1 = 471/6
F(X) = 9•471/6 = 4241/2
Анализ оптимального плана.
В оптимальный план вошла дополнительная переменная x3. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 1-го вида в количестве 201/6
В оптимальный план вошла дополнительная переменная x5. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 325/6
Значение 0 в столбце x1 означает, что использование x1 - выгодно.
Значение 15> 0 в столбце x2 означает, что использование x2 - не выгодно.
Значение 11/2 в столбце x4 означает, что теневая цена (двойственная оценка) равна 11/2.
4. Решить транспортную задачу, заданную распределительной таблицей.
40 |
20 |
40 | |
30 |
|||
25 |
|||
15 |
|||
30 |