Лабораторная работа №6 Решение задач целочисленного линейного программирования в табличном процессоре Еxcel.

Цель работы.

Изучение математической модели задачи целочисленного линейного программирования, освоение технологии решения ЗЦЛП в табличном процессоре Excel.

Содержание лабораторной работы.

Дана ЗЦЛП. Требуется найти решение задачи методом «ветвей и границ» с помощью встроенной функции «Поиск решения» табличного процессора Excel.

Задание на лабораторную работу.

Вариант 6.

Задача:

На приобретение оборудования для нового цеха выделено b₁ тыс. ден. ед. Оборудование должно быть размещено на площади не превышающей b₂ м². Предприятие может заказать оборудование двух типов: машины типа А стоимость а₁₁ тыс.ден.ед, требующие площадь (с учетом проходов) в а₂₁ м² и обеспечивающие производительность с₁ ед. продукции за смену и машины типа В стоимостью а₁₂тыс.ден. ен., занимающие площадь а₂₂ м² и дающие за смену с₂ ед. продукции. При это следует учесть, что машин типа А можно заказaть не более b₃ штук. Найти оптимальный вариант приобретения оборудования, обеспечивающий новому цеху максимальную производительность.

Математическая модель

F = 10x₁+12x₂ max

Составим каноническую форму записи

Ход работы.

1.Решим задачу целочисленного линейного программирования через встроенную функцию «Поиск решений» в табличном процессоре Excelс использованием условия ограничения «целое».

Рис. 1 – Решение с условием ограничения «целое»

Рис. 2 – Отчет по результатам

Значение целевой функции при х₁=4, х₂ =7F_max=124.

Оптимальным будет вариант, при котором приобретаются 4 автомобиля типа А и 2 - типа В. При этом 84 м² площади останутся неиспользованными. Максимальная производительность будет составлять 124 ед. продукции.

2. Решим задачу целочисленного линейного программирования через встроенную функцию «Поиск решений» в табличном процессоре Excelбез использования условия ограничения «целое».

Рис. 3 – Решение без использования условия ограничения «целое»

В результате, имеем значения х₁=3,8 , х₂=7,466667 и целевую функцию F_max=127,6.

Воспользуемся метод «ветвей и границ». Выберем, допустим, переменную х₂ =7,466667. Исходя из условий х₂≤ [7,466667] и х₂ ≥ [7,466667]+1 , разобьем исходную задачу на две подзадачи х₂ ≤ 7 и х₂ ≥ 8. Разветвление продолжим до тех пор, пока не получим значения x , удовлетворяющие условию целочисленности и не достигнем оптимального значения целевой функции.

	0. Ответ: х1=3,8, х2=7,466667 ЦФ: f=127,6
1.1 Ответ: х1=4, х2=7 ЦФ: f=124	1.2 Ответ: х1=2,71, х2=8 ЦФ: f=123,14
	2.1 Ответ: х1=2, х2=8,35 ЦФ: f=120,21			2.2 Ответ:пустое множество допустимых решений.
	3.1 Ответ: х1=0,68, х2=9 ЦФ: f=114,79		3.2 Ответ: х1=2, х2=8 ЦФ: f=116
	4.1 Ответ: пустое множество допустимых решений.	4.2 Ответ: х1=2, х2=8 ЦФ: f=116

Очевидно, что уже после первой итерации в ветви 1.1мы получаем оптимальный вариант. Сравнив результаты решения с использованием ограничение «целое» и без его использования, мы убедились, что получили один и тот же результат: при х₁=4, х₂ = 7 F_max=124.

Найдено оптимальное решение задачи: х_ц^опт=(4;7), f(х_ц^опт)=124. Оптимальным будет вариант, при котором приобретаются 4 автомобиля типа А и 2 - типа В. При этом 84 м² площади останутся неиспользованными. Максимальная производительность будет составлять 124 ед. продукции.

Ответы на контрольные вопросы.

1 .Каковы особенности задачи целочисленного линейного программирования?

Под ЗЛЦП понимается задача, в которой все или некоторые переменные должны принимать целые значения.

2. Какие методы решения задачи целочисленного программирования Вы знаете?

Метод «ветвей и границ», метод Гомори или метод отсечений, Поиск решений в табличном процессоре Excel.

3. Каким образом формируются подзадачи в методе «ветвей и границ»?

Пусть х_i – целочисленная переменная, значение х_i^* которой в оптимальном решении исходной задачи является дробным. Рассмотрим интервал [x_i^*]<x_i<[x_i^*]+1. Он не содержит допустимых целочисленных компонент решения. Поэтому допустимое целое значение х_i должно удовлетворять одному из неравенств: Два последних неравенства разбивают область допустимых решений для переменной х_i на две подобласти. То есть исходная задача разветвилась на две подзадачи, каждая из которых решается отдельно от ЗЛП с целевой функцией исходной задачи.

4. Каким условиям должны удовлетворять подзадачи в методе «ветвей и границ»?

Целевая функция соответствует ЦФ исходной задачи, система ограничений остается прежней и к ней добавляются новые условия относительно хi: интервал [x_i^*]<x_i<[x_i^*]+1 не содержит допустимых целочисленных компонент решения. Поэтому допустимое целое значение х_i должно удовлетворять одному из неравенств:

5. Что является первым оптимальным решением, организующим процесс ветвления?

В качестве верхней границы на множестве планов рассматривают значение целевой функции без условий целочисленности.

6. Сформулируйте математическую модель задачи целочисленного линейного программирования.

Математическая модель ЗЦЛП:

Z – множество целых чисел. Если p=n, то задачу называют полностью целочисленной, если p<n, то частично целочисленной.