Вход

Методы оптимальных решений

Рекомендуемая категория для самостоятельной подготовки:
Контрольная работа*
Код 294102
Дата создания 23 мая 2014
Страниц 49
Мы сможем обработать ваш заказ (!) 1 апреля в 12:00 [мск]
Файлы будут доступны для скачивания только после обработки заказа.
1 330руб.
КУПИТЬ

Описание

Решение задач.
Была сдана на 2-м курсе СПбУТД ...

Содержание

Найдем наибольшее значение линейной функции графическим методом.
L = 12 x1 -14 x2
при следующих ограничениях
x1 14
32 x1 -7 x2 420
4 x1 + 14 x2 168
-4 x1 + 7 x2 84


Найдем наименьшее значение линейной функции графическим методом.
L = 4 x1 + 7 x2
при следующих ограничениях
4 x1 + 7 x2 112
8 x1 + 7 x2 140
4 x1 -14 x2 28



3. - 4. Примеры 3.20 и 4.20 решите симплексным методом,
используя метод искусственного базиса и симплексные таблицы.
Во всех примерах этого раздела к системе линейных ограничений следует
добавить условие неотрицательности всех переменных: .



Введение

1. - 2. Примеры 1.20 и 2.20 решите графическим методом.

Во всех примерах этого раздела к системе линейных ограничений следует добавить условие неотрицательности всех переменных: .



Фрагмент работы для ознакомления

ONВектор    нарисован не в масштабе,ONисключительно для большей наглядности.Причем очевидно, что значение функции будет возрастатьпри перемещении прямой в направлении вектора  .ONДиапазон перемещения прямой НЕ от точки O до точки N, а именно, в направлении от точки O к точке N.Будем перемещать прямую, перпендикулярную вектору  ,ONдо тех пор пока, она не коснется области допустимых решений.В нашем случае, первое касание прямой области допустимых решений произойдет в отрезке DE , где D (7 , 12) E (21 , 4). В любой точке отрезка DE значение нашей функции будет наименьшим.Ответ :Наименьшее значение функция достигает при x1 = t1 * 7 + t2 * 21x2 = t1 * 12 + t2 * 4где t1 + t2 = 1 t1 0 , t2 0.Значение функции : L = 112 3. - 4. Примеры 3.20 и 4.20 решите симплексным методом,используя метод искусственного базиса и симплексные таблицы. Во всех примерах этого раздела к системе линейных ограничений следует добавить условие неотрицательности всех переменных: . Решение.Шаг:1Избавимся от неравенств в ограничениях, введя в ограничения 1, 2, 3 неотрицательные балансовые переменные s1, s2, s3.4x1+7x2-s1= 56   (1)-8x1+35x2+s2= 420   (2)20x1-14x2+s3= 420   (3)x1, x2, s1, s2, s3 ≥ 0Шаг:2Ищем в системе ограничений базисные переменные.Из последней системы ограничений можно выделить базисные переменные s2,s3.Не все уравнения содержат базисные переменные, это значит, что исходная задача не содержит в себе допустимого базисного решения. Для его нахождения вначале составим и решим вспомогательную задачу. Такое решение еще называют решением с искусственным базисом.Введем в уравнение 1 искусственную неотрицательную переменную r1 .Получим следующую систему ограничений,4x1+7x2-s1+r1= 56   (1)-8x1+35x2+s2= 420   (2)20x1-14x2+s3= 420   (3)x1, x2, s1, s2, s3, r1 ≥ 0с базисными переменными r1,s2,s3.Целью решения вспомогательной задачи является получение допустимого базисного решения не содержащего искусственных переменных (r1). Для этого сформируем вспомогательную целевую функцию :G = r1и проведем ее минимизацию в заданной системе ограничений. Если после минимизации функции G ее оптимальное значение будет равно нулю и все искусственные переменные окажутся выведенными из базиса, то полученное базисное решение есть допустимое базисное решение исходной задачи. Если же после минимизации функции G ее оптимальное значение окажется отличным от нуля, значит исходная система ограничений противоречива (область допустимых решений пуста) и исходная задача решения не имеет.Для решения вспомогательной задачи симплекс-методом выразим функцию G через свободные переменные, для этого:   - вычтем из функции G уравнение 1 Функция G примет вид : G = -4x1-7x2+s1+56Теперь мы можем сформировать начальную симплекс-таблицу.Шаг:3Начальная симплекс-таблицаБПx1x2s1s2s3r1РешениеОтношениеr14 7 -1 0 0 1 56 56/7=8s2-8 35 0 1 0 0 420 420/35=12s320 -14 0 0 1 0 420 --Q8 7 0 0 0 0 0 --G-4 -7 1 0 0 0 -56 --Итерация 0-aБПx1x2s1s2s3РешениеОтношениеx2471 -170 0 8 --s2-28 0 5 1 0 140 --s328 0 -2 0 1 532 --Q4 0 1 0 0 -56 --G0 0 0 0 0 0 --Получено оптимальное решение вспомогательной задачи (найден минимум функции G т.к. в строке целевой функции нет отрицательных коэффициентов). Все искусственные переменные вышли из базиса и поэтому мы можем приступить к решению исходной задачи, приняв полученное базисное решение в качестве опорного. Сторка "G" нам больше не нужна, принятие решения о направляющем столбце, во всех последующих итерациях, будем принимать по строке "Q"Итерация 1БПx1x2s1s2s3РешениеОтношениеx2471 -170 0 8 --s2-28 0 5 1 0 140 --s328 0 -2 0 1 532 --Q4 0 1 0 0 -56 --Достигнуто оптимальное решение, т.к. в строке целевой функции нет отрицательных коэффициентов.Ответ:Оптимальное значение функции Q(x)=56достигается в точке с координатами:x1=0x2=8s1=0s2=140s3=532Решение.Шаг:1Избавимся от отрицательных свободных членов, умножив на -1 ограничения 2.16x1+7x2≥ 252   (1)8x1-7x2≥ 84   (2)4x1+7x2≤ 168   (3)x1, x2 ≥ 0Шаг:2Избавимся от неравенств в ограничениях, введя в ограничения 1, 2, 3 неотрицательные балансовые переменные s1, s2, s3.16x1+7x2-s1= 252   (1)8x1-7x2-s2= 84   (2)4x1+7x2+s3= 168   (3)x1, x2, s1, s2, s3 ≥ 0Шаг:3Ищем в системе ограничений базисные переменные.Из последней системы ограничений можно выделить базисную переменную s3.Не все уравнения содержат базисные переменные, это значит, что исходная задача не содержит в себе допустимого базисного решения. Для его нахождения вначале составим и решим вспомогательную задачу. Такое решение еще называют решением с искусственным базисом.Введем в уравнения 1, 2 искусственные неотрицательные переменные r1, r2 .Получим следующую систему ограничений,16x1+7x2-s1+r1= 252   (1)8x1-7x2-s2+r2= 84   (2)4x1+7x2+s3= 168   (3)x1, x2, s1, s2, s3, r1, r2 ≥ 0с базисными переменными r1,r2,s3.Целью решения вспомогательной задачи является получение допустимого базисного решения не содержащего искусственных переменных (r1,r2). Для этого сформируем вспомогательную целевую функцию :G = r1+r2и проведем ее минимизацию в заданной системе ограничений. Если после минимизации функции G ее оптимальное значение будет равно нулю и все искусственные переменные окажутся выведенными из базиса, то полученное базисное решение есть допустимое базисное решение исходной задачи. Если же после минимизации функции G ее оптимальное значение окажется отличным от нуля, значит исходная система ограничений противоречива (область допустимых решений пуста) и исходная задача решения не имеет.Для решения вспомогательной задачи симплекс-методом выразим функцию G через свободные переменные, для этого:   - вычтем из функции G уравнение 1   - вычтем из функции G уравнение 2 Функция G примет вид : G = -24x1+s1+s2+336Теперь мы можем сформировать начальную симплекс-таблицу.Шаг:4Начальная симплекс-таблицаБПx1x2s1s2s3r1r2РешениеОтношениеr116 7 -1 0 0 1 0 252 252/16=63 4 r28 -7 0 -1 0 0 1 84 84/8=21 2 s34 7 0 0 1 0 0 168 168/4=42Q4 14 0 0 0 0 0 0 --G-24 0 1 1 0 0 0 -336 --Итерация 1БПx1x2s1s2s3r1РешениеОтношениеr10 21 -1 2 0 1 84 84/21=4x11 -780 -180 0 212--s30 2120 121 0 126 126/21 2 =12Q0 3520 120 0 -42 --G0 -21 1 -2 0 0 -84 --Итерация 1-aБПx1x2s1s2s3РешениеОтношениеx20 1 -1212210 4 4/2=42x11 0 -124-1240 14 --s30 0 12-121 84 --Q0 0 56-760 -112 --G0 0 0 0 0 0 --Получено оптимальное решение вспомогательной задачи (найден минимум функции G т.к. в строке целевой функции нет отрицательных коэффициентов). Все искусственные переменные вышли из базиса и поэтому мы можем приступить к решению исходной задачи, приняв полученное базисное решение в качестве опорного. Сторка "G" нам больше не нужна, принятие решения о направляющем столбце, во всех последующих итерациях, будем принимать по строке "Q"Итерация 2БПx1x2s1s2s3РешениеОтношениеx20 1 -1212210 4 4/2 21 =42x11 0 -124-1240 14 --s30 0 12-121 84 --Q0 0 56-760 -112 --Итерация 3БПx1x2s1s2s3РешениеОтношениеs20 212-121 0 42 --x11 716-1160 0 634--s30 214140 1 105 --Q0 494140 0 -63 --Достигнуто оптимальное решение, т.к. в строке целевой функции нет отрицательных коэффициентов.Ответ:Оптимальное значение функции Q(x)=63достигается в точке с координатами:x1=63 4 x2=0s1=0s2=42s3=1055. Задача Прядильно-ниточное предприятие выпускает нитки с лавсаном (н/л) и нитки с капроном (н/к), для изготовления которых использует хлопок I сорта (х/1), а также и хлопок II сорта (х/2). На изготовление 1 тонны (н/л) требуется A =119кг (х/1) и B =14 кг (х/2), на изготовление 1 т (н/к) требуется C =8 кг (х/1) и D =92 кг (х/2). Запасы хлопка на предприятии составляют соответственно: P 532кг - (х/1) и Q =700 кг - (х/2). Прибыль от реализации 1 т (н/л) составляет R=2037 у. е., а от реализации 1 т (н/к) - S 1776 у. е. Какой должен быть план производства, чтобы суммарная прибыль оказалась максимальной?В условие задачи 5.20 вместо буквенных данных подставьте соответствующие числовые, взятые из нужной Вам строки нижеследующей таблицы.Составьте математическую модель этой задачи.Составьте двойственную к ней задачу, приняв за неизвестные условные цены на хлопок.Решив обе задачи графическим методом, проверьте выполнение основного принципа двойственности.Таблица числовых данных к задачам 5.20.Решение.Составим математическую модель задачиДля удобства занесем данные задачи в таблицуВид хлопкаНормы расхода хлопка на изготовления 1 тонны изделий, кгЗапасы хлопка, кгн/лн/кI1198532II1492700Прибыль от реализации 1 тонны изделий, у. е.20371776  Пусть х1-количество н/л, тонн, х2 - количество н/к, тонн запланированных к производству. Для их изготовления потребуется (119 х1 +8х2) единиц хлопка вида I, (14х1 +92х2) хлопка вида II. Так как, потребление ресурсов I, II, не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:119x1+8х2≤53214x1+92х2≤700По смыслу задачи переменные х1 ≥ 0, х2 ≥0.Конечную цель решаемой задачи – получение максимальной прибыли при реализации продукции – выразим как функцию двух переменных х1 и х2.Суммарная прибыль составит 2037х1 от реализации продукции н/л и 1776х 2 от реализации продукции н/к, то есть : F = 2037х1 +1776х 2. →max.Решим прямую задачу графическим методомВ первую очередь, найдем область допустимых значений, т.е. точки x1 и x2 , которые удовлетворяют системе ограничений. По условию задачи x1 0, x2 0 ,т.е. мы рассматриваем только те точки , которые принадлежат первой четверти.Шаг 1Рассмотрим неравенство 1 системы ограничений.119 x1 + 8 x2 532   Построим прямую.Заменим знак неравенства на знак равенства .119 x1 + 8 x2 = 532  Преобразуем уравнение следующим образом .x1+ x2= 5321/1191/8Каждый член уравнения разделим на 532 .x1+ x2= 176/17133/2Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую.На оси X1 рисуем точку с координатой 76/17 . На оси X2 рисуем точку с координатой 133/2 .Соединяем полученные точки и получаем необходимую прямую.  Какие точки нас интересуют?119 x1 + 8 x2 532  8 x2-119 x1+ 532 x2-119/8 x1+ 133/2 Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой. Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный справа.Область допустимых значений выделена штриховкой.Точки принадлежащие области допустимых значений: A (0 , 0) B (76/17 , 0) C (0 , 133/2) Шаг 2Рассмотрим неравенство 2 системы ограничений.14 x1 + 92 x2 700   Построим прямую.Заменим знак неравенства на знак равенства .14 x1 + 92 x2 = 700  Преобразуем уравнение следующим образом .x1+ x2= 7001/141/92Каждый член уравнения разделим на 700 .x1+ x2= 150175/23Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую.На оси X1 рисуем точку с координатой 50 . На оси X2 рисуем точку с координатой 175/23 .Соединяем полученные точки и получаем необходимую прямую.  Какие точки нас интересуют?14 x1 + 92 x2 700  92 x2-14 x1+ 700 x2-7/46 x1+ 175/23 Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой. Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный справа.Область допустимых значений выделена штриховкой.Точки принадлежащие области допустимых значений: A (0 , 0) B (76/17 , 0) D (0 , 175/23) E (4 , 7) Шаг 3Вернемся к нашей исходной функции L . L =  2037 x1 + 1776 x2 Допустим значение функции L равно 1 (абсолютно произвольно выбранное число), тогда 1 =  2037 x1 + 1776 x2 Данное уравнение является уравнением прямой на плоскости. Из курса аналитической геометрии известно, что данная прямая перпендикулярна вектору , координатами которого являются коэффициенты функции, а именно вектору = (2037 ,1776).ON Следовательно, с геометрической точки зрения, наша исходная функция L изображается как множество прямых перпендикулярных вектору= (2037 ,1776). ON Построим вектор= (2037 , 1776)ON На рисунке правее, вектор    изображен красным цветом.ONВектор    нарисован не в масштабе,ONисключительно для большей наглядности.Причем очевидно, что значение функции будет возрастатьпри перемещении прямой в направлении вектора  .ONДиапазон перемещения прямой НЕ от точки O до точки N, а именно, в направлении от точки O к точке N.Будем перемещать прямую, перпендикулярную вектору  ,ONдо тех пор, пока она полностью не пройдет область допустимых решений.В нашем случае, касание прямой, перед выходом из области допустимых решений, произойдет в точке E (4 , 7) . В данной точке значение функции будет наибольшим.Ответ :Наибольшее значение функция достигает при x1 = 4x2 = 7.Значение функции : L = 20580Составим двойственную задачу к прямой задаче.119y1 + 14y2 >= 20378y1 + 92y2 >= 1776532y1 + 700y2 → miny1 >= 0y2 >= 0 Решим двойственную задачу тоже графическим методом для удобстав переобозначим x на yВ первую очередь, найдем область допустимых значений, т.е. точки x1 и x2 , которые удовлетворяют системе ограничений. По условию задачи x1 0, x2 0 ,т.е. мы рассматриваем только те точки , которые принадлежат первой четверти.Шаг 1Рассмотрим неравенство 1 системы ограничений.119 x1 + 14 x2 2037   Построим прямую.Заменим знак неравенства на знак равенства .119 x1 + 14 x2 = 2037  Преобразуем уравнение следующим образом .x1+ x2= 20371/1191/14Каждый член уравнения разделим на 2037 .x1+ x2= 1291/17291/2Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую.На оси X1 рисуем точку с координатой 291/17 . На оси X2 рисуем точку с координатой 291/2 .Соединяем полученные точки и получаем необходимую прямую.  Какие точки нас интересуют?119 x1 + 14 x2 2037  14 x2-119 x1+ 2037 x2-17/2 x1+ 291/2 Знак неравенства больше или равно нуля, следовательно, нас интересуют точки лежащие выше построенной нами прямой. Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный справа.Область допустимых значений выделена штриховкой.Точки принадлежащие области допустимых значений: A (291/17 , 0) B (0 , 291/2) Шаг 2Рассмотрим неравенство 2 системы ограничений.8 x1 + 92 x2 1776   Построим прямую.Заменим знак неравенства на знак равенства .8 x1 + 92 x2 = 1776  Преобразуем уравнение следующим образом .x1+ x2= 17761/81/92Каждый член уравнения разделим на 1776 .x1+ x2= 1222444/23Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую.На оси X1 рисуем точку с координатой 222 . На оси X2 рисуем точку с координатой 444/23 .Соединяем полученные точки и получаем необходимую прямую.  Какие точки нас интересуют?8 x1 + 92 x2 1776  92 x2-8 x1+ 1776 x2-2/23 x1+ 444/23 Знак неравенства больше или равно нуля, следовательно, нас интересуют точки лежащие выше построенной нами прямой. Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный справа.Область допустимых значений выделена штриховкой.Точки принадлежащие области допустимых значений: C (222 , 0) B (0 , 291/2) D (15 , 18) Шаг 3Вернемся к нашей исходной функции L . L =  532 x1 + 700 x2 Допустим значение функции L равно 1 (абсолютно произвольно выбранное число), тогда 1 =  532 x1 + 700 x2 Данное уравнение является уравнением прямой на плоскости. Из курса аналитической геометрии известно, что данная прямая перпендикулярна вектору , координатами которого являются коэффициенты функции, а именно вектору = (532 ,700).ON Следовательно, с геометрической точки зрения, наша исходная функция L изображается как множество прямых перпендикулярных вектору= (532 ,700). ON Построим вектор= (532 , 700)ON На рисунке правее, вектор    изображен красным цветом.ONВектор    нарисован не в масштабе,ONисключительно для большей наглядности.Причем очевидно, что значение функции будет возрастатьпри перемещении прямой в направлении вектора  .ONДиапазон перемещения прямой НЕ от точки O до точки N, а именно, в направлении от точки O к точке N.Будем перемещать прямую, перпендикулярную вектору  ,ONдо тех пор пока, она не коснется области допустимых решений.В нашем случае, первое касание прямой области допустимых решений произойдет в точке D (15 , 18). В данной точке значение функции будет наименьшим.Ответ :Наименьшее значение функция достигает при x1 = 15x2 = 18.Значение функции : L = 20580На данном примере видим выполнение первой теоремы двойственности: Если одна из двойственных задач имеет оптимальное решение, то и двойственная ей задача имеет оптимальное решение, причем - эти задачи совпадают.Так же .

Список литературы

5. Задача
Прядильно-ниточное предприятие выпускает нитки с лавсаном (н/л) и нитки с капроном (н/к), для изготовления которых использует хлопок I сорта (х/1), а также и хлопок II сорта (х/2). На изготовление 1 тонны (н/л) требуется A =119кг (х/1) и B =14 кг (х/2), на изготовление
1 т (н/к) требуется C =8 кг (х/1) и D =92 кг (х/2). Запасы хлопка на предприятии составляют соответственно: P 532кг - (х/1) и Q =700 кг - (х/2).
Прибыль от реализации 1 т (н/л) составляет R=2037 у. е., а от реализации 1 т (н/к) - S 1776 у. е.
Какой должен быть план производства, чтобы суммарная прибыль оказалась максимальной?

1) В условие задачи 5.20 вместо буквенных данных подставьте соответствующие числовые, взятые из нужной Вам строкинижеследующей таблицы.
2) Составьте математическую модель этой задачи.
3) Составьте двойственную к ней задачу, приняв за неизвестные условные цены на хлопок.
4) Решив обе задачи графическим методом, проверьте выполнение основного принципа двойственности.
Таблица числовых данных к задачам 5.20.
Решение.
6. В задачах №№ 6.20 нужно методом потенциалов решить транспортную задачу. Первоначальный опорный план составьте методом северо-западного угла.
Имеется четыре ткацких фабрики , которые поставляют ткань на пять швейных фабрик в пределах России . Известны запасы ткани на каждой ткацкой фабрике (в рулонах) и потребности в ней на каждой швейной фабрике. Известна также стоимость перевозки одного рулона ткани (у. е.) от каждого поставщика к каждому потребителю.
Найти такой план перевозок, при котором суммарные затраты оказались бы минимальными.
Условия (запасы, потребности и цена перевозки каждого рулона ткани) для каждого номера задачи приведены в таблицах.

№ 6.20
"з" ЗАПАС B1 B2 B3 B4 B5
A1 60 7 4 5 4 3
A2 70 3 5 4 2 4
A3 50 1 2 3 1 2
A4 60 5 3 2 4 2
"п" ПОТР 40 60 50 40 50
Очень похожие работы
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
bmt: 0.00514
© Рефератбанк, 2002 - 2024