Ход работы

Лабораторная работа №6.

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

методом ветвей и границ.

Выполнил:

студент гр АС-31

Кухарчук А. Н.

Проверил:

Парфомук И.И.

Брест 2011

Цель работы. Изучение алгоритма метода ветвей и границ для решения задачи целочисленного линейного программирования.

Задание:

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

1. Отбросим требование целочисленности и решим задачу при помощи программы SIMPLEX.EXE:

Получили нецелочисленное решение поставленной задачи:

2. Для каждого небазисного х будем по очереди вводить ограничения и где [x_i] – целая часть числа x_i и решать полученную задачу линейного программирования:

x₁≤14 x₁≥15

x₂≤10 x₂≥11

x₁=14 x₂=10 x₃=3,167 L(x)=107    

ОГРАНИЧЕНИЯ НЕСОВМЕСТНЫ

ОГРАНИЧЕНИЯ НЕСОВМЕСТНЫ

x₃≤3

x₃≥4

	x1=14 x2=10 x3=3 L(x)=106

РЕКОРД

Получили целочисленное решение поставленной задачи:

Вывод. Изучили алгоритм метода ветвей и границ для решения задачи целочисленного линейного программирования.

Дата добавления: 2014-01-15