Реферат Курсовая Конспект
Решим задачу графически. - раздел Информатика, Решение оптимизационных задач средствами EXCEL 1) X1 + 3X2 &poun...
|
1) | x1 + 3x2 £ 18 | ||
x1 + 3x2 = 18 (0; 6) (18; 0) | |||
к.т. (0; 0), 0 + 3*0 < 18 (в) – входит | |||
2) | 2x1 + x2 £ 16 | ||
2x1 + x2 = 16 (0; 16) (8; 0) | |||
к.т. (0; 0), 2*0 + 0 < 16 (в) – входит | |||
3) | x2 £ 5 | ||
x2 = 5, x2 < 5 - ниже прямой | |||
4) | x1 ³ 0 - правее ОX2 | ||
5) | x2 ³ 0 - выше ОX1 | ||
Линия уровня | F = 2x1 + 3 x2 F = 0 | ||
2x1 + 3x2 = 0 (0; 0) (3; -2) | |||
q = {2; 3} - указывает направление возрастания F. | |||
max F достигается в т. С
т.С | x1 + 3 x2 = 18 | Þ - | 2 x1 + 6 x2 = 36 | Þ | 5 x2 = 20 | Þ |
2x1 + x2 = 16 | 2 x1 + x2 = 16 | x1 + 3 x2 = 18 | ||||
Þ | x2 = 4 | |||||
x1 = 6 |
Таким образом, необходимо выпустить x1 = 6 шт. изделий А1, x2 = 4 шт. изделий А2, чтобы получить max F = 2*6 + 3*4 = 24 ден.ед.
Симплексный метод решения задачи линейного программирования
Для решения ЗЛП существует универсальный метод – метод последовательного улучшения плана или симплекс-метод, который состоит из двух вычислительных процедур: симплекс-метода с естественным базисом и симплекс-метода с искусственным базисом (М-метод).
Выбор конкретной вычислительной процедуры осуществляется после приведения исходной ЗЛП к каноническому виду (КЗЛП):
В теории линейного программирования (ЛП) показано, что оптимальное решение ЗЛП связано с угловыми (крайними) точками многогранника решений, которым отвечают опорные планы (неотрицательные базисные решения системы уравнений КЗЛП). Каждый из опорных планов определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов А1, А2,…, Аn. Верхняя граница количества опорных планов, содержащихся в данной задаче, определяется числом сочетаний Сnm.
Задача 3. Получить решение по модели задачи об оптимальном использовании ограниченных ресурсов (решить ЗЛП):
Приведем задачу к каноническому виду путем введения дополнительных переменных x 3 и x4:
Найдем все опорные планы КЗЛП. Используя метод Жордана-Гаусса выписываем все базисные решения системы уравнений:
Последовательно будем иметь:
Х1 = (0,0,300,150); Х2= (150,0,150,0); Х3= (0,150,-150,0); Х4= (75,75,0,0); Х5= (300,0,0,-150); Х6= (0,100,0,50).
Среди этих базисных решений четыре опорных:
Х1 = (0,0,300,150); Х2= (150,0,150,0); Х4= (75,75,0,0); Х6= (0,100,0,50).
Указанным опорным планам на рис.5 отвечают соответственно следующие угловые точки и значения ЦФ в них:
А(0,0) и f(0,0)=0; Д(150,0) и f(150,0)=300; С(75,75) и f(75,75)=375; В(0,100) и f(0,100)=300.
Согласно теории ЛП оптимальное решение содержится среди опорных планов.
Рис.5
Таким образом, максимальное значение, равное 375, целевая функция f (x1,x2) достигает на опорном плане Х4= (75,75,0,0), т.е. оптимальное решение рассматриваемой ЗЛП: x1 = 75, x2 = 75.
Понятно, что при больших m и n найти оптимальный план, перебирая указанным выше способом (прямым перебором) все опорные ЗЛП весьма трудно. Поэтому необходимо иметь схему, позволяющую осуществлять упорядоченный переход от одного опорного плана к другому. Такой схемой является симплексный метод.
– Конец работы –
Эта тема принадлежит разделу:
На сайте allrefs.net читайте: "Решение оптимизационных задач средствами EXCEL"
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Решим задачу графически.
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов