Реферат: Курсовая работа по ЭММ
4. На пересечении разрешающего столбца и разрешающей строки стоит разрешающий элемент аqp. Индексы q и p обозначают, что из базиса выводится `Аq, а вместо него вводится `Аp. Разрешающий элемент обычно обводят в таблице.
5. На месте разрешающего элемента в новой симплекс-таблице ставят 1, остальные элементы разрешающего столбца 0.
6. Все элементы разрешающей строки делят на разрешающий элемент.
7. Остальные элементы симплекс-таблицы пересчитывают по формулам Жордана-Гаусса.
Замечание: Если по индексной строке определили разрешающий столбец, но в нем все элементы не положительные, то задача не имеет решений.
Следующий этап - это определение оптимального плана из симплекс-таблицы Х* = (х1*, х2*, ..., хn*). Оптимальное решение выписывают из столбцов Хб и план. Столбец Хб - показывает, какие неизвестные отличны от 0. Столбец план - показывает, чему они равны.
D0 - в последней симплекс-таблицы равно max значению целевой функции.
Алгоритм работы по симплекс-методу:
1. Выделяем исходный допустимый базис и заполняем первую таблицу.
2. Если в последней строке полученной таблицы, кроме, быть может, первого числа, нет положительных чисел, то базисное решение является оптимальным - задача решена.
3. Пусть среди указанных в пункте 2 чисел имеется положительное число( скажем, в столбце хj). Отмечаем столбец Хj вертикальной стрелкой. Просматриваем остальные числа этого столбца. Если среди них нет положительных чисел, то min f = -¥ - задача решений не имеет.
4. Пусть среди просмотренных в п.3 чисел
имеются положительные числа. Для каждого из таких чисел a составляем отношение
, где b - первое число в той же строке (свободный член). Из всех
таких отношений выбираем наименьшее. Пусть оно соответствует строке базисного
неизвестного хi . Отмечаем эту строку горизонтальной
стрелкой. Число a, стоящее в отмеченной строке и
отмеченном столбце, называется разрешающим элементом таблицы.
5. Переходим к новой таблице. Для этого
отмеченную строку умножаем на 
( чтобы
на месте разрешающего элемента появилась единица) и пишем ее на месте прежней.
К каждой из остальных строк таблицы прибавляем строку, полученную на месте
отмеченной строки, умноженную на такое число, чтобы элемент, стоящий в
отмеченном столбце, обратился в 0.
6. С новой таблицей возвращаемся к п.2
1.3 М-метод.
Для решения М-задачи можно воспользоваться симплекс-методом, поскольку указан допустимый базис.
При решении М-задачи могут представиться две возможности:
1. М-задача имеет решение, т.е. min F существует.
2. М-задача не имеет решения, min F =¥.
Решая М-задачу, мы стремимся получить оптимальное решение, в котором значения искусственных неизвестных равны нулю. Для того чтобы этого достичь, необходимо выбрать последовательность шагов таким образом, чтобы все искусственные неизвестные вышли из базиса, т.е. стали свободными. Тогда в базисном решении значения этих неизвестных и будут как раз нулями.
Таким образом, переходя при решении М - задачи от одного базиса к другому, мы стараемся в первую очередь выводить из базиса одно искусственное неизвестное за другим. Возможны, впрочем, и такие (досадные) случаи, когда в процессе решения приходится заменять одно искусственное неизвестное на другое (выбор разрешающего элемента по-другому не получается). Но общим направлением вычислительного процесса во всех случаях остается постепенный вывод искусственных неизвестных из базиса.
1.4 Двойственные задачи .
С каждой задачей линейного программирования связана другая задача, называемая двойственной по отношению к исходной. Совместное изучение данной задачи и двойственности к ней дает, как правило, значительно больше информации.
Задачи I и I’ называются двойственными друг другу. Смысл, который вкладывается в это название, состоит в следующем.
1. Если первая задача имеет размеры m x n ( m ‑ ограничений с n неизвестными), то вторая - размеры n x m.
2. Матрицы из коэффициентов при неизвестных в левых частях ограничений обеих задач являются взаимно транспонированными .
3. В правых частях ограничений в каждой задаче стоят коэффициенты при неизвестных в целевой функции другой задачи.
4. В задаче I все ограничения представляют собой неравенства типа £, причем в этой задаче требуется достичь max f. Напротив, в задаче I’ все ограничения суть неравенства типа ³, причем требуется достичь min j.
Двойственная задача заключается в минимизации общей оценки всего имеющегося количества ресурсов.
Взаимозависимость оптимальных решений пары двойственных задач определена следующими теоремами:
Теорема (основное неравенство). Пусть Х - какое-нибудь допустимое решение задачи I, т.е. любое решение системы, а Y - какое-нибудь допустимое решение задачи I’ - любое решение системы. Тогда справедливо неравенство
f(Х) £ j(Y).
Следствие1 (достаточный признак оптимальности). Если для каких-то
допустимых решений 
и 
задач I и I’ выполняется равенство
f(
)=j(
),
то 
есть
оптимальное решение задачи I, а 
-
оптимальное решение задачи I’.
Следствие2. Если в одной из задач I и I’ целевая функция не ограничена с соответствующей стороны (т.е. max f = ¥ в задаче I или min j = -¥ в задаче I’), то другая задача не имеет допустимых решений.
Основная теорема. Если разрешима одна из двойственных задач I или I’, то разрешима и другая задача, причем max f = min j.
Теорема равновесия. Пусть Х и Y- допустимые решения задач I и I’. Для оптимальности (одновременной) этих решений необходимо и достаточно выполнение равенств
Решение двойственной задачи находится в строке Dj симплекс-таблицы в последних столбцах дополнительных переменных. Переменные yi обозначают оценки одной единицы ресурса.
Величина двойственной оценки того или иного ресурса показывает, насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на одну единицу.
Двойственные оценки измеряют эффективность малых приращений объемов ресурсов в конкретных условиях данной задачи. Если целью является расширение производства и повышение эффективности плана путем привлечения дополнительных ресурсов, то анализ оценок поможет выбрать правильное решение. Прирост различных ресурсов будет давать неодинаковый эффект, т.е. оценки позволяют с большей точностью выявить узкие места, сдерживающие рост эффективности производства. С учетом всех конкретных условий задачи оценки показываю, какие ресурсы более дефицитны, какие менее дефицитны и какие избыточны. Дефицитные ресурсы имеют самые высокие оценки.
2. Задача планирования производства.2.1 Определение оптимального варианта строительств скважин в УБР на планируемый год.
1. Постановка задачи.
В УБР запланировано строительство скважин нескольких категорий:
I категории - не более H1;
II категории - не более Н2;
III категории - не менее (не более) Н3.
При строительстве скважин используются разные материально-технические ресурсы, наличие которых в УБР ограниченно следующим количеством (в тоннах):
обсадные трубы - В1;
химреагенты - В2;
глина и глинопорошок - В3;
талевый канат - В4;
ГСМ - В5.
При строительстве скважин разной категории потребляется различное количество ресурсов каждого вида. Расход материально-технических ресурсов в расчете на одну скважину каждой категории задан таблицей 1.
Таблица 1
|
категории скважин |
виды ресурсов | ||||
| Обсадные трубы | Х/реагенты | глина и глинопорошок | Талевый канат | ГСМ | |
| I | 450 | 45 | 130 | 20 | 46 |
| II | 300 | 40 | 110 | 16 | 36 |
| III | 200 | 30 | 70 | 15 | 30 |
Экономический эффект при строительстве скважины j категории определен Эj тыс. руб.
Требуется:
1. Определить оптимальный план строительства скважин, при котором в пределах ограниченного объема ресурсов (табл.1) достигается максимальный экономический эффект.
2. Определить двойственные оценки ресурсов и их устойчивость.
3. Провести всесторонний анализ полученных оптимальных решений.
Таблица 2
| Н1 | Н2 | Н3 | Э1 | Э2 | Э3 | В1 | В2 | В3 | В4 | В5 |
| 15 | 9 | не менее 9 | 186 | 125 | 90 | 4800 | 600 | 1610 | 280 | 580 |
Предприятие имеет 5 видов ресурсов, необходимые для строительства любой из трех категорий скважин. Известны затраты ресурсов на строительство единицы каждой категории скважины, а также экономический эффект при строительстве единицы скважины каждой категории.
Для удобства работы все данные занесем в одну таблицу (табл.3)
Таблица 3. Исходная информация задачи.
| Вид | Категории скважин | Объем | ||
| ресурсов | I | II | III | Ресурсов |
| обсадные трубы | 450 | 300 | 200 | 4800 |
| хим/реагенты | 45 | 40 | 30 | 600 |
| глина и глинопорошок | 130 | 110 | 70 | 1610 |
| Талевый канат | 20 | 16 | 15 | 280 |
| ГСМ | 46 | 36 | 30 | 580 |
| Экономический эффект на единицу скважины, тыс.руб. | 186 | 125 | 90 | |
Введем переменные:
хj ³ 0, j=1,2,3 - количество скважин каждой категории соответственно.
2. Математическая модель задачи.
f = 186х1 + 125х2 +90х3 ® max
х1 £ 15; х2 £ 9; х3 ³ 9 хj ³ 0, j=1,2,3
3.Экономическое содержание основных и дополнительных переменных.
Основные переменные:
х1 - количество скважин I категории
х2 - количество скважин II категории
х3 - количество скважин III категории
Вводим дополнительные переменные:
х4 - неиспользованные обсадные трубы
х5 - остаток неиспользованных хим/реагентов
х6 - остаток неиспользованных глины и глинопорошка
х7 - остаток талевого каната
х8 - остаток ГСМ
х9 - кол-во скважин I-категории, недостающих до max числа 15;
х10 -кол-во скважин II-категории, недостающих до max числа 9;
х11 –кол-во скважин III-категории, превышающих min число 9;
х12 - количество недостроенных скважин по категориям.
4. Канонический вид.
f = 186х1 + 125х2 + 90х3 -М*х12® max
хj ³ 0, j=`1;12
5. Решение симплекс-методом.
| Сб | Хб | план | 186 | 125 | 90 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | Х7 | Х8 | Х9 | Х10 | Х11 | Х12 | ||||
| 0 | Х4 | 4800 | 450 | 300 | 200 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 24 |
| 0 | Х5 | 600 | 45 | 40 | 30 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 20 |
| 0 | Х6 | 1610 | 130 | 110 | 70 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 23 |
| 0 | Х7 | 280 | 20 | 16 | 15 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 18,7 |
| 0 | Х8 | 580 | 46 | 36 | 30 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 19,3 |
| 0 | Х9 | 15 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
| 0 | Х10 | 9 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | |
| M | Х12 | 9 | 0 | 0 |
1 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | Min 9 |
| Z | 0 | -186 | -125 | -90 | 0 | 0 | |||||||||
| M | -9 | 0 | 0 | -1 | 1 | -1 | |||||||||
| 0 | Х4 | 3000 |
450 |
300 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 200 | 0 | 6,7 |
| 0 | Х5 | 330 | 45 | 40 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 30 | 0 | 7,3 |
| 0 | Х6 | 980 | 130 | 110 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 70 | 0 | 7,5 |
| 0 | Х7 | 145 | 20 | 16 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 15 | 0 | 7,2 |
| 0 | Х8 | 310 | 46 | 36 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 30 | 0 | 6,74 |
| 0 | Х9 | 15 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 15 |
| 0 | Х10 | 9 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | |
| 90 | X3 | 9 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | |
| Z | 810 | -186 | -125 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -90 | 90 | ||
| M | 0 | 0 | 0 | 0 | 0 | ||||||||||
| 186 | x1 | 6,67 | 1 | 0,67 | 0 | 0,00 | 0 | 0 | 0 | 0 | 0 | 0 | 0,44 | -0,44 | 15 |
| 0 | Х5 | 30,00 | 0 | 10,00 | 0 | -0 | 1 | 0 | 0 | 0 | 0 | 0 | 10 | -10,00 | 3 |
| 0 | Х6 | 113,33 | 0 | 23,33 | 0 | -0,29 | 0 | 1 | 0 | 0 | 0 | 0 | 12,22 | -12,22 | 9,3 |
| 0 | Х7 | 11,67 | 0 | 2,67 | 0 | -0 | 0 | 0 | 1 | 0 | 0 | 0 | 6,11 | -6,11 | -1,9 |
| 0 | Х8 | 3,33 | 0 | 5,33 | 0 | -0,10 | 0 | 0 | 0 | 1 | 0 | 0 | 9,56 | -9,56 | 0,3 |
| 0 | Х9 | 8,33 | 0 | -0,67 | 0 | -0 | 0 | 0 | 0 | 0 | 1 | 0 | -0,44 | 0,44 | |
| 0 | Х10 | 9 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | |
| 90 | X3 | 9 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | |
| Z | 2050 | 0 | -1 | 0 | 0,41 | 0 | 0 | 0 | 0 | 0 | 0 | -7,33 | 7,33 | ||
| 186 | X1 | 6,51 | 1 | 0,42 | 0 | 0,035 | 0 | 0 | 0 | -0,047 | 0 | 0 | 0 | 0 | |
| Х5 | 26,51 | 0 | 4,42 | 0 | 0,035 | 1 | 0 | 0 | -1,047 | 0 | 0 | 0 | 0 | ||
| 0 | Х6 | 109,07 | 0 | 16,51 | 0 | -0,79 | 0 | 1 | 0 | -1,279 | 0 | 0 | 0 | 0 | |
| 0 | Х7 | 9,53 | 0 | -0,74 | 0 | 0,10 | 0 | 0 | 1 | -0,64 | 0 | 0 | 0 | 0 | |
| 0 | Х11 | 0,35 | 0 | 0,56 | 0 | -0,92 | 0 | 0 | 0 | 0,10 | 0 | 0 | 1 | -1 | |
| 0 | Х9 | 8,49 | 0 | -0,42 | 0 | -0,03 | 0 | 0 | 0 | 0,05 | 1 | 0 | 0 | 0 | |
| 0 | Х10 | 9 | 1 | 0,00 | 0 | 0,00 | 0 | 0 | 0 | 0,00 | 0 | 1 | 0 | 0 | |
| 90 | X3 | 9,35 | 0 | 0,56 | 1 | 0,00 | 0 | 0 | 0 | 0,10 | 0 | 0 | 0 | 0 | |
| Z | 2052,56 | 0 | 3,09 | 0 | 0,33 | 0 | 0 | 0 | 0,77 | 0 | 0 | 0 | 0 | ||
| M | 0 | 0 | 0 | 0 | 0 |
Оптимальное решение.
Х* = (6,5; 0; 9,35; 0,26,5; 109,1; 9,5; 0,8,5; 9; ), по которому достигается максимальный экономический эффект
Эmax (Х*)=2052,56тыс.руб.
Ответ: Максимальный экономический эффект может достигнуть 2052,56 тыс.руб. если построить скважины так:
I - категории – 6,5
II - категории – 0
III - категории – 9,3
Остатки сырья составят:
1. обсадные трубы -0
2. Химреагенты– 26,51
3. Глина и глинопорошок– 109,1
4. Талевый канат –9,5
5. Гсм - 0
При округлении количества скважин по категориям получаем:
I категория - 6 скважины
II категория - 0 скважины
III категория – 9 скважин
f = 186*6+125*0+90*9 = 1926
Максимальный экономический эффект может достигнуть 1926 тыс.руб. следовательно изменятся остатки:
4800-450*6-300*0-200*9=300 Обсадные трубы - 300
600- 45*6-40*0-30*9= 60 хим/ реагенты - 60
1610-130*6-110*0-70*9=200 глина и глинопорошок - 200
280-20*60-16*0-15*9=25 талевый канат - 25
580-46*6+36*0+30*9=34 ГСМ - 34
2.2 Двойственная задача.
Решая двойственную задачу, мы решаем вопрос минимизации общей оценки всего имеющегося количества ресурсов.
6. Математическая модель двойственной задачи.
Пусть уi - стоимость единицы i-го ресурса
Z= 4800у1+600у2+1610у3+280у4+580у5+15у6+9у7-9у8® min
7. Экономическое содержание двойственной задачи.
При каких значениях уI стоимости единицы каждого из ресурсов в пределах ограниченного объема ресурсов и заданном Экономическом эффекте Эj j-ой скважины общая стоимость затрат Z будет минимальной ?
8. Оптимальное решение двойственной задачи.
Оптимальное решение двойственной задачи найдем из последней строки симплекс-таблицы
Y*=(0,33;0 ,0 ;0 ;0,77 )
Z min(Y*)= 4800*0,33+0+*0+*0+580*0,77=2052,56
Величина двойственной оценки того или оного ресурса показывает, насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на одну единицу.
Вывод: можно построить новый оптимальный план, в котором экономический эффект возрастет на 0,33 тыс.руб , если ввести единицу обсадных труб. А если увеличить расход гсм на единицу, то экономический эффект возрастет на 0,77 тыс.руб.
9. Оценка степени дефицитности ресурсов.
В нашей задаче целью является повышение экономической эффективности плана путем привлечения дополнительных ресурсов, то наш анализ оценок позволит выбрать правильное решение.
Прирост различных ресурсов будет давать неодинаковый эффект, т.е. в избытке у нас такие ресурсы как : глина и глинопорошок, талевый канат и химреагенты. (Остатки даны в пункте 5)
Дефицитными ресурсами в нашей задаче являются обсадные трубы у1= 0,314 и гсм у2= 0,77.
10. Оценить рентабельность производства.
450*0,33+46*0,77=184
200*0,33+30*0,77=89
так как цена не превышает затраты значит предприятие рентабельно.
1. Замков О.О., Толстопятенко А.В., Черемных Ю.Н., Математические методы в экономике. Учебник. - М.: МГУ им. М.В. Ломоносова, Изд. «ДИС», 1997г.
2. Коршунов Н.И., Плясунов В.С., Математика в экономике. - М.: Изд. «Вита-Пресс», 1996г.
3. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б., Математическое программирование. - М.: Высшая школа, 1976г.
4. Солодовников А.С., Бабайцев В.А., Брайлов А.В., Математика в экономике. Учебник: В 3-х ч. Ч.1. - М.: Финансы и статистика, 1998г.
5. Юдин Д.Б., Гольштейн Е.Г., Задачи и методы линейного программирования. - М.: Сов. Радио, 1964г.
6.Корманов В.Г. Математическое программирование.Учеб.пособие
3-е издание –М: наука 1986 г.
