Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Интересное:
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Дисциплины:
2021-02-05 | 43 |
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 с. |
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!