Автор работы: Пользователь скрыл имя, 29 Октября 2011 в 21:10, курсовая работа
Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества возможных вариантов в условиях рыночных отношений приходится отыскивать наилучшие, в некотором смысле при ограничениях, налагаемых на природные, экономические и технологические возможности. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику? Такие методы объединяются под общим названием — математическое программирование.
ВВЕДЕНИЕ…………………………………………………………………...3
1. Понятие линейного программирования……………………….…………4
2.Симплекс метод…………………………………………………………….4
3.Экономическая постановка задачи.…………………………….…….…...5
4. Понятие математической модели………….………………………….......5
5.Двойственная задача линейного программирования.…………..…….….6
6. Решение исходной задачи двойственным симплекс методом………….7
Список использованной литературы………………………………………..10
Транспонированной называется матрица, у которой строки и столбцы меняются местами. Поэтому коэффициенты при переменных yi в задаче II это, соответственно, коэффициенты i-ого неравенства в задаче I. Неравенства, находящиеся напротив друг друга, называются сопряженными.
Двойственность является фундаментальным понятием в теории линейного программирования. Основные результаты теории двойственности заключены в двух теоремах, называемых теоремами двойственности.
Теорема 1
Если одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных планах совпадают, F(x*)=G(y*), где х*, у* – оптимальные решения задачи I и II
Теорема 2
Планы х* и у* оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задачи I и II соответственно, хотя бы одно из любой пары сопряженных неравенств обращается в равенство.
6. Решение исходной задачи двойственным симплекс методом
Двойственный симплекс–метод основан на очень простой идее. Поскольку, решая исходную задачу, мы автоматически получаем решение двойственной, то иногда удобно выбирать, какую из задач решать, естественно, более простую по форме, а затем, решив, находим оптимальное решение другой. Этот метод удобно применять при решении задачи о рационе, задачи о раскрое и некоторых других ЗЛП
Имеем задачу (I) построим ей двойственную (II).
I.
F=2X1+X2®min G=24Y1 + 18Y2 + 20Y3 + 6Y 4®max
Приведем ее к каноническому виду.
Введем базисные переменные ,
G=- G = -24Y1 - 18Y2 - 20Y3 - 6Y 4® min
Решаем симплекс–методом задачу .
1.Найдем разрешающий элемент.
1.1. Из отрицательных элементов индексной F– строки выберем наибольший по модулю, назовем соответствующий ему столбец – разрешающим.
1.2. Чтобы выбрать разрешающую строку, необходимо вычислить отношения элементов столбца свободных членов к только положительным элементам разрешающего столбца. Выбрать из полученных отношений минимальное. Соответствующий элемент, на котором достигается минимум, называется разрешающим.
В нашем примере, , элемент 3 – разрешающий. Строка, соответствующая этому элементу тоже называется разрешающей.
2.
Выбрав разрешающий элемент,
2.1. В новой таблице, таких же размеров, что и ранее, переменные разрешающей строки и столбца меняются местами, что соответствует переходу к новому базису. В данной задаче: Y 1 входит в базис, вместо Y 5, которая выходит из базиса, и теперь свободная.
2.2. На месте разрешающего элемента записываем обратное ему число .
2.3. Элементы разрешающей строки делятся на разрешающий элемент.
2.4. Элементы разрешающего столбца делятся на разрешающий элемент и записываются с противоположным знаком.
2.5. Чтобы заполнить оставшиеся элементы, осуществляем пересчет по правилу прямоугольника.
Пусть мы хотим посчитать элемент, стоящий на месте 2(Y2;Y6 )
Соединяем этот элемент мысленно с разрешающим элементом, находим произведение, вычитаем произведение элементов, находящихся на другой диагонали получившегося прямоугольника. Разность делим на разрешающий элемент.
Итак, . Записываем на место, где было 3.
Проверим целевую функцию, согласно условиям.
В индексной строке есть отрицательный элемент, в столбце которого есть хотя бы один положительный. Тогда переходим к следующему шагу, пересчитываем дальше, улучшая опорный план.
В индексной F– строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу, взятым с противоположным знаком.
Выписываем решение:
Y1= 0; Y4=-3;
Y2= 2; Y5= 0;
Y3 = 0; Y6= 0;
Подставляем полученные решения в условия задачи:
I. II.
Два условия в II системе не совпадают, выписываем из в I системы эти условия и решаем как систему уравнений.
F=2X1+X2®min = 2*6+6 = 18
Ответ к задаче:
Для эффективного откорма крупно рогатого скота необходимо 6 кг зерна и 6 кг отрубей. При этом затраты минимальны и составят 18 руб.
Список используемой литературы