Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Топ:
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Дисциплины:
2021-02-05 | 49 |
5.00
из
|
Заказать работу |
|
|
"Решение задач целочисленного программирования"
Задание.
Решить полностью целочисленную задачу линейного программирования:
max z = 18x1 + 9x2 + 8x3
2x1 + 21x2 + 4x3 £ 15
6x1 + 20x2 + 5x3 £ 20
xi ³ 0
Для приведения задачи к стандартной форме вводим дополнительные переменные:
max z = 18x1 + 9x2 + 8x3
2x1 + 21x2 + 4x3 + x4 = 15
6x1 + 20x2 + 5x3 + x5 = 20
xi ³ 0
Результаты решения задачи с помощью метода отсечений Гомори по программе "Решение задач целочисленного программирования" представлены в следующих таблицах:
Исходные данные
1 | Число переменных | 5 |
2 | Число ограничений | 2 |
3 | Признак оптимизации | 1 |
4 | Число этапов моделирования | 1 |
Коэффициенты целевой функции
х1 | х2 | х3 | х4 | х5 | |
c | 18 | 9 | 8 | 0 | 0 |
Фиктивные слагаемые коэффициентов целевой функции
х1 | х2 | х3 | х4 | х5 | |
cm | 0 | 0 | 0 | 0 | 0 |
Номера базисных переменных
огр.1 | огр.2 | |
x | 4 | 5 |
Матрица коэффициентов
x1 | x2 | x3 | x4 | x5 | правые части | |
огр. 1 | 2 | 21 | 4 | 1 | 0 | 15 |
огр. 2 | 6 | 20 | 5 | 0 | 1 | 20 |
Номер отсечения Гомори | 2 |
Результирующая симплекс-таблица
x1 | x2 | x3 | x4 | x5 | x6 | x7 | правые части | |
z | 0 | 45 | 0 | 0 | 0 | 2 | 8 | 54 |
zm | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
x4 | 0 | 15 | 0 | 1 | 0 | 6 | -4 | 9 |
x1 | 1 | 3 | 0 | 0 | 0 | 1 | 0 | 3 |
х3 | 0 | 0 | 1 | 0 | 0 | -2 | 1 | 0 |
х5 | 0 | 2 | 0 | 0 | 1 | 4 | -5 | 2 |
Решение задачи: x1 = 3, x2 = 0, x3 = 0, z = 54, и целочисленность достигнута за две итерации метода отсечений Гомори.
Результаты решение ЗЛП с помощью метода ветвей и границ по программе /1/ представлены в следующих таблицах:
Исходные данные
1 | Число переменных | 5 |
2 | Число ограничений | 2 |
3 | Признак оптимизации | 1 |
4 | Число этапов моделирования | 1 |
Коэффициенты целевой функции
|
х1 | х2 | х3 | х4 | х5 | |
c | 18 | 9 | 8 | 0 | 0 |
Фиктивные слагаемые коэффициентов целевой функции
х1 | х2 | х3 | х4 | х5 | |
cm | 0 | 0 | 0 | 0 | 0 |
Номера базисных переменных
огр.1 | огр.2 | |
x | 4 | 5 |
Матрица коэффициентов
x1 | x2 | x3 | x4 | x5 | правые части | |
огр. 1 | 2 | 21 | 4 | 1 | 0 | 15 |
огр. 2 | 6 | 20 | 5 | 0 | 1 | 20 |
Результирующая симплекс-таблица
x1 | x2 | x3 | x4 | x5 | правые части | |
z | 0 | 51 | 7 | 0 | 3 | 60 |
zm | 0 | 0 | 0 | 0 | 0 | 0.000 |
x4 | 0 | 14.33 | 2.333 | 1 | -0.333 | 8.333 |
x1 | 1 | 3.333 | 0.833 | 0 | 0.167 | 3.333 |
Условие оптимальности выполняется
Таким образом, решение исходной задачи: x 1 = 3.333, x 2 = 0, x 3 = 0, z = 60.
Условие целочисленности не выполнено для переменной х1.
Итерация 1. Рассматриваем исходную ЗЛП с дополнительным ограничением х1 £ 3.
max z = 18x1 + 9x2 + 8x3
2x1 + 21x2 + 4x3 £ 15
6x1 + 20x2 + 5x3 £ 20
х1 £ 3
xi ³ 0
Стандартная форма:
max z = 18x1 + 9x2 + 8x3
2x1 + 21x2 + 4x3 + x4 = 15
6x1 + 20x2 + 5x3 + x5 = 20
х1 + х6 = 3
xi ³ 0
Решение ЗЛП с помощью программы:
Исходные данные
1 | Число переменных | 6 |
2 | Число ограничений | 3 |
3 | Признак оптимизации | 1 |
4 | Число этапов моделирования | 1 |
Коэффициенты целевой функции
х1 | х2 | х3 | х4 | х5 | х6 | |
c | 18 | 9 | 8 | 0 | 0 | 0 |
Фиктивные слагаемые коэффициентов целевой функции
х1 | х2 | х3 | х4 | х5 | х6 | |
cm | 0 | 0 | 0 | 0 | 0 | 0 |
Номера базисных переменных
огр.1 | огр.2 | огр.3 | |
x | 4 | 5 | 6 |
Матрица коэффициентов
x1 | x2 | x3 | x4 | x5 | x6 | правые части | |
огр. 1 | 2 | 21 | 4 | 1 | 0 | 0 | 15 |
огр. 2 | 6 | 20 | 5 | 0 | 1 | 0 | 20 |
огр. 3 | 1 | 0 | 0 | 0 | 0 | 1 | 3 |
Результирующая симплекс-таблица
x1 | x2 | x3 | x4 | x5 | x6 | правые части | |
z | 0 | 23 | 0 | 0 | 1.6 | 8.4 | 57.2 |
zm | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
x4 | 0 | 5 | 0 | 1 | -0.8 | 2.8 | 7.4 |
x3 | 0 | 4 | 1 | 0 | 0.2 | -1.2 | 0.4 |
х1 | 1 | 0 | 0 | 0 | 0 | 1 | 3 |
Условие оптимальности выполняется
Решение задачи: x 1 = 3, x 2 = 0, x 3 = 0.4, z = 57.2.
Условие целочисленности не выполнено для переменной х3.
Итерация 2. Рассматриваем исходную ЗЛП с дополнительным ограничением х1 ³ 4.
|
max z = 18x1 + 9x2 + 8x3
2x1 + 21x2 + 4x3 £ 15
6x1 + 20x2 + 5x3 £ 20
х1 ³ 4
xi ³ 0
Стандартная форма:
max z = 18x1 + 9x2 + 8x3 – Мх 7
2x1 + 21x2 + 4x3 + x5 = 15
6x1 + 20x2 + 5x3 + x6 = 20
х1 – х4 + х7 = 4
xi ³ 0
Решение ЗЛП с помощью программы:
Исходные данные
1 | Число переменных | 7 |
2 | Число ограничений | 3 |
3 | Признак оптимизации | 1 |
4 | Число этапов моделирования | 1 |
Коэффициенты целевой функции
х1 | х2 | х3 | х4 | х5 | х6 | х7 | |
c | 18 | 9 | 8 | 0 | 0 | 0 | 0 |
Фиктивные слагаемые коэффициентов целевой функции
х1 | х2 | х3 | х4 | х5 | х6 | х7 | |
cm | 0 | 0 | 0 | 0 | 0 | 0 | -1 |
Номера базисных переменных
огр.1 | огр.2 | огр.3 | |
x | 5 | 6 | 7 |
Матрица коэффициентов
x1 | x2 | x3 | x4 | x5 | x6 | x7 | правые части | |
огр. 1 | 2 | 21 | 4 | 0 | 1 | 0 | 0 | 15 |
огр. 2 | 6 | 20 | 5 | 0 | 0 | 1 | 0 | 20 |
огр. 3 | 1 | 0 | 0 | -1 | 0 | 0 | 1 | 4 |
Результирующая симплекс-таблица
x1 | x2 | x3 | x4 | x5 | x6 | x7 | правые части | |
z | 0 | 51 | 7 | 0 | 0 | 3 | 0 | 60 |
zm | 0 | 3.333 | 0.833 | 1 | 0 | 0.167 | 0 | -0.667 |
x5 | 0 | 14.333 | 2.333 | 0 | 1 | -0.333 | 0 | 8.333 |
x1 | 1 | 3.333 | 0.833 | 0 | 0 | 0.167 | 0 | 3.333 |
х7 | 0 | -3.333 | -0.833 | -1 | 0 | -0.167 | 1 | 0.667 |
Условие оптимальности выполняется
В оптимальном базисе осталась искусственная переменная, поэтому задача не имеет допустимых решений. Данная ветвь – прозондирована.
Итерация 3. Рассматриваем исходную ЗЛП с дополнительными ограничениями:
х1 £ 3 и х3 £ 0.
max z = 18x1 + 9x2 + 8x3
2x1 + 21x2 + 4x3 £ 15
6x1 + 20x2 + 5x3 £ 20
х1 £ 3
х3 £ 0
xi ³ 0
Стандартная форма:
max z = 18x1 + 9x2 + 8x3
2x1 + 21x2 + 4x3 + x 4 = 15
6x1 + 20x2 + 5x3 + x 5 = 20
х1 + х6 = 3
х3 + х7 = 0
xi ³ 0
Решение ЗЛП с помощью программы:
Исходные данные
1 | Число переменных | 7 |
2 | Число ограничений | 4 |
3 | Признак оптимизации | 1 |
4 | Число этапов моделирования | 1 |
Коэффициенты целевой функции
х1 | х2 | х3 | х4 | х5 | х6 | х7 | |
c | 18 | 9 | 8 | 0 | 0 | 0 | 0 |
Фиктивные слагаемые коэффициентов целевой функции
х1 | х2 | х3 | х4 | х5 | х6 | х7 | |
cm | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Номера базисных переменных
огр.1 | огр.2 | огр.3 | огр.4 | |
x | 4 | 5 | 6 | 7 |
Матрица коэффициентов
x1 | x2 | x3 | x4 | x5 | x6 | x7 | правые части | |
огр. 1 | 2 | 21 | 4 | 1 | 0 | 0 | 0 | 15 |
огр. 2 | 6 | 20 | 5 | 0 | 1 | 0 | 0 | 20 |
огр. 3 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 3 |
огр. 4 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
Результирующая симплекс-таблица
|
x1 | x2 | x3 | x4 | x5 | x6 | x7 | правые части | |
z | 0 | 0 | 0 | 0 | 0.45 | 15.3 | 5.75 | 54.9 |
zm | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
x4 | 0 | 0 | 0 | 1 | -1.05 | 4.3 | 1.25 | 6.9 |
x2 | 0 | 1 | 0 | 0 | 0.05 | -0.3 | -0.25 | 0.1 |
х1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 3 |
х3 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
Условие оптимальности выполняется
Решение задачи: x 1 = 3, x 2 = 0.1, x 3 = 0, z = 54.9.
Условие целочисленности не выполнено для переменной х2.
Итерация 4. Рассматриваем исходную ЗЛП с дополнительными ограничениями:
х1 £ 3 и х3 ³ 1.
max z = 18x1 + 9x2 + 8x3
2x1 + 21x2 + 4x3 £ 15
6x1 + 20x2 + 5x3 £ 20
х1 £ 3
х3 ³ 1
xi ³ 0
Стандартная форма:
max z = 18x1 + 9x2 + 8x3 – Мх8
2x1 + 21x2 + 4x3 + x 5 = 15
6x1 + 20x2 + 5x3 + x 6 = 20
х1 + х7 = 3
х3 – х4 + х8 = 1
xi ³ 0
Решение ЗЛП с помощью программы:
Исходные данные
1 | Число переменных | 8 |
2 | Число ограничений | 4 |
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 | -1 |
Номера базисных переменных
огр.1 | огр.2 | огр.3 | огр.4 | |
x | 5 | 6 | 7 | 8 |
Матрица коэффициентов
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | правые части | |
огр. 1 | 2 | 21 | 4 | 0 | 1 | 0 | 0 | 0 | 15 |
огр. 2 | 6 | 20 | 5 | 0 | 0 | 1 | 0 | 0 | 20 |
огр. 3 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 3 |
огр. 4 | 0 | 0 | 1 | -1 | 0 | 0 | 0 | 1 | 1 |
Результирующая симплекс-таблица
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | правые части | |
z | 0 | 51 | 0 | 7 | 0 | 3 | 0 | -7 | 53 |
zm | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
x5 | 0 | 14.333 | 0 | 2.333 | 1 | -0.333 | 0 | -2.333 | 6 |
x1 | 1 | 3.333 | 0 | 0.833 | 0 | 0.167 | 0 | -0.833 | 2.5 |
х7 | 0 | -3.333 | 0 | -0.833 | 0 | -0.167 | 1 | 0.833 | 0.5 |
х3 | 0 | 0 | 1 | -1 | 0 | 0 | 0 | 1 | 1 |
|
|
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!