Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Интересное:
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2021-02-05 | 47 |
5.00
из
|
Заказать работу |
Решение задачи: x 1 = 2.5, x 2 = 0, x 3 = 1, z = 53.
Условие целочисленности не выполнено для переменной х1.
Итерация 5. Рассматриваем исходную ЗЛП с дополнительными ограничениями:
х1 £ 3, х3 £ 0 и х2 £ 0.
max z = 18x1 + 9x2 + 8x3
2x1 + 21x2 + 4x3 £ 15
6x1 + 20x2 + 5x3 £ 20
х1 £ 3
х3 £ 0
х2 £ 0
xi ³ 0
Стандартная форма:
max z = 18x1 + 9x2 + 8x3
2x1 + 21x2 + 4x3 + x4 = 15
6x1 + 20x2 + 5x3 + x5 = 20
х1 + х6 = 3
х3 + х7 = 0
х2 + х8 = 0
xi ³ 0
Решение ЗЛП с помощью программы:
Исходные данные
1 | Число переменных | 8 |
2 | Число ограничений | 5 |
3 | Признак оптимизации | 1 |
4 | Число этапов моделирования | 1 |
Коэффициенты целевой функции
х1 | х2 | х3 | х4 | х5 | х6 | х7 | х8 | |
c | 18 | 9 | 8 | 0 | 0 | 0 | 0 | 0 |
Фиктивные слагаемые коэффициентов целевой функции
х1 | х2 | х3 | х4 | х5 | х6 | х7 | х8 | |
cm | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Номера базисных переменных
огр.1 | огр.2 | огр.3 | огр.4 | огр.5 | |
x | 4 | 5 | 6 | 7 | 8 |
Матрица коэффициентов
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | правые части | |
огр. 1 | 2 | 21 | 4 | 1 | 0 | 0 | 0 | 0 | 15 |
огр. 2 | 6 | 20 | 5 | 0 | 1 | 0 | 0 | 0 | 20 |
огр. 3 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 3 |
огр. 4 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
огр. 5 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
Результирующая симплекс-таблица
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | правые части | |
z | 0 | 0 | 0 | 0 | 0 | 18 | 8 | 9 | 54 |
zm | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
x4 | 0 | 0 | 0 | 1 | 0 | -2 | -4 | -21 | 9 |
x5 | 0 | 0 | 0 | 0 | 1 | -6 | -5 | -20 | 2 |
х1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 3 |
х3 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
х2 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
Условие оптимальности выполняется
Решение задачи: x1 = 3, x2 = 0, x3 = 0, z = 54.
Условие целочисленности выполнено. Значение z = 54 принимается в качестве текущей границы. Данная ветвь – прозондирована. Кроме того, считается прозондированной ветвь с дополнительными ограничениями х1 £ 3 и х3 ³ 1 (итерация 4), так как значение целевой функции на этой ветви z = 53 меньше текущей границы.
Итерация 6. Рассматриваем исходную ЗЛП с дополнительными ограничениями:
х1 £ 3, х3 £ 0 и х2 ³ 1.
max z = 18x1 + 9x2 + 8x3
2x1 + 21x2 + 4x3 £ 15
6x1 + 20x2 + 5x3 £ 20
х1 £ 3
х3 £ 0
х2 ³ 1
xi ³ 0
Стандартная форма:
max z = 18x1 + 9x2 + 8x3 – Мх 9
2x1 + 21x2 + 4x3 + x5 = 15
6x1 + 20x2 + 5x3 + x6 = 20
х1 + х7 = 3
х3 + х8 = 0
х2 – х4 + х9 = 1
xi ³ 0
Решение ЗЛП с помощью программы:
Исходные данные
1 | Число переменных | 9 |
2 | Число ограничений | 5 |
3 | Признак оптимизации | 1 |
4 | Число этапов моделирования | 1 |
Коэффициенты целевой функции
х1 | х2 | х3 | х4 | х5 | х6 | х7 | х8 | х9 | |
c | 18 | 9 | 8 | 0 | 0 | 0 | 0 | 0 | 0 |
Фиктивные слагаемые коэффициентов целевой функции
х1 | х2 | х3 | х4 | х5 | х6 | х7 | х8 | х9 | |
cm | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 |
Номера базисных переменных
огр.1 | огр.2 | огр.3 | огр.4 | огр.5 | |
x | 5 | 6 | 7 | 8 | 9 |
Матрица коэффициентов
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | правые части | |
огр. 1 | 2 | 21 | 4 | 0 | 1 | 0 | 0 | 0 | 0 | 15 |
огр. 2 | 6 | 20 | 5 | 0 | 0 | 1 | 0 | 0 | 0 | 20 |
огр. 3 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 3 |
огр. 4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
огр. 5 | 0 | 1 | 0 | -1 | 0 | 0 | 0 | 0 | 1 | 1 |
Результирующая симплекс-таблица
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | правые части | |
z | -17.14 | 0 | -6.286 | 0 | 0.429 | 0 | 0 | 0 | 0 | 6.429 |
zm | 0.095 | 0 | 0.19 | 1 | 0.048 | 0 | 0 | 0 | 0 | -0.286 |
x2 | 0.095 | 1 | 0.19 | 0 | 0.048 | 0 | 0 | 0 | 0 | 0.714 |
x6 | 4.095 | 0 | 1.19 | 9 | -0.952 | 1 | 0 | 0 | 0 | 5.714 |
х7 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 3 |
х8 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
х9 | -0.095 | 0 | -0.19 | -1 | -0.048 | 0 | 0 | 0 | 1 | 0.286 |
Условие оптимальности выполняется
Решение задачи: x1 = 3, x2 = 0, x3 = 0, z = 54.
В оптимальном базисе осталась искусственная переменная, поэтому задача не имеет допустимых решений. Данная ветвь – прозондирована.
Все ветви прозондированы, поэтому оптимальное значение целевой функции совпадает с текущей границей, а соответствующей ей набор переменных является решением задачи (итерация 5): x1 = 3, x2 = 0, x3 = 0, z = 54.
Схема решения задачи.
Аналогично оформляется отчет по частично целочисленной задаче линейного программирования.
Литература
1. | Трушков А. С. Решение и моделирование задач линейного программирования. Отчет и программная документация. - КФ МГОУ, г. Коломна, 1998 г., 76 с. |
2. | Трушков А. С. Симплексный метод решения задач линейного программирования. Алгоритмы и приложения.// Учебное пособие. Изд-во КФ МГОУ, г. Коломна, 1996 г., 107 с. |
3. | Трушков А.С. Методы решения задач математического программирования.// Учебное пособие. Изд-во КФ МГОУ, г. Коломна, 1997 г., 102 с. |
4. | Трушков А.С. Контрольная работа “Динамическое программирование”. Контрольная работа “Целочисленное программирование”.// Сборник вариантов контрольной работы. Изд-во КФ МГОУ, г. Коломна, 1997 г., 100 с. |
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!