Типовой отчет к лабораторной работе — КиберПедия 

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...

Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...

Навигация:

Главная Случайная страница Обратная связь ТОП Интересно знать Избранные Новые материалы

Топ:

Динамика и детерминанты показателей газоанализа юных спортсменов в восстановительном периоде после лабораторных нагрузок до отказа...

Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из по­вторяющихся рабочих циклов, каждый из которых соответствует...

Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...

Интересное:

Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...

Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...

Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...

Дисциплины:

Автоматизация Антропология Археология Архитектура Аудит Биология Бухгалтерия Военная наука Генетика География Геология Демография Журналистика Зоология Иностранные языки Информатика Искусство История Кинематография Компьютеризация Кораблестроение Кулинария Культура Лексикология Лингвистика Литература Логика Маркетинг Математика Машиностроение Медицина Менеджмент Металлургия Метрология Механика Музыкология Науковедение Образование Охрана Труда Педагогика Политология Правоотношение Предпринимательство Приборостроение Программирование Производство Промышленность Психология Радиосвязь Религия Риторика Социология Спорт Стандартизация Статистика Строительство Теология Технологии Торговля Транспорт Фармакология Физика Физиология Философия Финансы Химия Хозяйство Черчение Экология Экономика Электроника Энергетика Юриспруденция

Типовой отчет к лабораторной работе

2021-02-05 48
Типовой отчет к лабораторной работе 0.00 из 5.00 0 оценок
Заказать работу

⇐ ПредыдущаяСтр 4 из 5Следующая ⇒

"Решение задач целочисленного программирования"

 

Задание.

Решить полностью целочисленную задачу линейного программирования:

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

⇐ Предыдущая12345Следующая ⇒
Поделиться с друзьями:

История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...

Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьше­ния длины пробега и улучшения маневрирования ВС при...

Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...

Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.063 с.