Метод Гомори. Целочисленное решение

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

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

Задача целочисленного программирования формулируется так же, как и задача линейного программирования, но включает дополнительное требование, состоящее в том, что значения переменных должны быть целыми неотрицательными числами, например =30 станков, =16 самолетов, =7 человек.

Методы целочисленной оптимизации можно разделить на три основные группы: а) методы отсечения; б) комбинированные методы; в) приближенные методы. Рассмотрим один из методов отсечения — метод Гомори.

Сущность методов отсечения состоит в том, что сначала задача решается без условия целочисленности. Если полученный план целочисленный, то задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее

следующими свойствами:

а) оно должно быть линейным;

б) должно отсекать найденный оптимальный нецелочисленный план;

в) не должно отсекать ни одного целочисленного плана.

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

Алгоритм Гомори, основанный на симплексном методе, имеет простой способ построения правильного отсечения и содержит следующие этапы.

1. Задача линейного программирования решается без учета условия целочисленности симплексным или двойственным симплексным методом. Если все элементы оптимального плана целые числа, то решение заканчивается для задачи целочисленного программирования.

2. Если среди элементов оптимального решения есть нецелые числа, то необходимо выбрать элемент с наибольшей дробной частью и составить дополнительное ограничение (сечение), которое отсекает нецелочисленные решения.

Дополнительное ограничение дается в том случае, если значение базисной переменной в оптимальном плане — дробное число. Тогда некоторые элементы в i-й строке симплексной таблицы также дробные числа. Обозначим [ ]и [ ] целые части чисел и ,т.е. наибольшие целые числа, не превышающие и .Величины дробных частей и определяются как разности следующим образом:

= -[ ], = -[ ] и являются положительными числами.

Тогда неравенство , сформированное по i-й строке симплексной таблицы, обладает всеми свойствами правильного отсечения.

3. Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной и включается в оптимальную симплексную таблицу.

4. Полученная расширенная задача решается двойным симплексным методом. Если новый оптимальный план будет целочисленным, то задача решена. В противном случае необходимо вернуться к п. 2 алгоритма.

Если в процессе решения в симплексной таблице появится уравнение с нецелым свободным членом и целыми коэффициентами , то данная задача не имеет целочисленного оптимального решения.

Пример. Маркетинговые исследования указали на необходимость освоения выпуска новой продукции. Поэтому на предприятии решено установить новое технологическое оборудование на освободившейся площади 10 кв.м. На приобретение оборудования двух видов выделено 6 млн. руб. Комплект первого вида оборудования стоимостью 1 млн. руб. устанавливается на площади 5 кв.м и позволяет увеличить доход предприятия на 8 млн. руб. Комплект второго вида оборудования занимает площадь 2 кв.м, стоит 1 млн. руб. и обеспечивает увеличение дохода предприятия на 5 млн. руб.

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

Решение. Обозначим через , количество комплектов технологического оборудования соответственно первого и второго видов, через F(Х)— доход предприятия от продажи продукции.

Тогда математическая модель задачи имеет вид:

,

при ограничениях:

где , - целые числа.

Приведем задачу к каноническому виду, для чего введем дополнительные неотрицательные переменные , и решим ее симплексным методом, а результаты запишем в таблицу 2.4.7.

Таблица 2.4.7

Базисные переменные	Значения базисных переменных
		5
		-8	-5			max
			2/5	1/5
			3/5	-1/5		10/3
			-9/5	8/5		max
	8/3			1/3	-2/3
	10/3			-1/3	5/3

 

В таблице 2.4.7 на третьей итерации получен оптимальный план , в котором =8/3 и =10/3 - дробные числа.

По первому уравнению с переменной , получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью (2/3), составляем дополнительное ограничение:

= -[ ]=8/3-2=2/3;

= -[ ]=1-1=0;

= -[ ]=0-0=0;

= -[ ]=1/3-0=1/3;

= -[ ]=-2/3+1=1/3.

Дополнительное ограничение имеет вид:

Преобразуем полученное неравенство в уравнение:

,

коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу 2.4.7; тогда получим продолжение таблицу 2.4.8.

 

Таблица 2.4.8

Базисные переменные	Значения базисных переменных
	8/3			1/3	-2/3
	10/3			-1/3	5/3
	-2/3			-1/3	-1/3
	max	-	-			-
					-1
						-1
						-3

 

Применяя алгоритм двойственного симплексного метода, проводим одну итерацию, в результате которой получаем оптимальное целочисленное решение: X=(2, 4, 2); =36 млн руб.

Таким образом, предприятию необходимо установить два комплекта оборудования первого вида и четыре комплекта второго вида. Это позволит максимально увеличить доход предприятия.

В задачах 1 и 2 найти оптимальные решения методом Гомори.

1) 2)

; .

Контрольные вопросы

 

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

2. Каков признак оптимальности в симплексном методе?

3. Как строится опорный план?

4. Как определяются ведущий столбец и ведущая строка симплексной таблицы?

5. Как осуществляется перерасчет элементов симплексной таблицы?

6. Каковы основные случаи при реализации симплексного метода?

7. В каких вариантах постановки задач следует пользоваться для их решения методом искусственного базиса?

8. Какие задачи следует решать методом Гомори?

Задачи

 

1—7. Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально- денежных ресурсов в количестве единиц. При этом для продажи первой группы товаров на 1 тыс. руб. товарооборота расходуется

ресурса первого вида в количестве единиц, ресурса второго вида - в количестве единиц, ресурса третьего вида – в количестве единиц. Для продажи второй и третьей групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве единиц, ресурсов второго вида — в количестве единиц, ресурсов третьего вида — в количестве единиц. Доход от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно (тыс. руб.).

Определите плановый объем и структуру товарооборота так, чтобы доход торгового предприятия был максимальным.

1. =3, =6, =4, =2, =1, =2, =2, =3, =1, =180, =50, =40, =6, =5, =5.

2. =3, =2, =1, =2, =1, =3, =, =2, =1, =420, =600, =900, =3, =3, =4.

3. =16, =18, =9, =7, =7, =2, =9, =2, =3, =520, =140, =810, =8, =6, =4.

4. =4, =8, =2, =3, =8, =4, =12, =4, =6, =116, =240, =432,

=83, =6, =6.

5. =8, =10, =20, =4, =13, =8, =2, =18, =12, =800, =520, =940, =3, =6, =7.

6. =1, =4, =0, =0, =3, =1, =2, =0, =5, =36, =50, =80, =6, =16, =25.

7. =17, =5, =5, =8, =6, =6, =4, =2, =4, =850, =1120, =1060, =8, =7, =4.

8. Ha кондитерскую фабрику г. Покров перед Новым годом поступилизаказы на подарочные наборы конфет из магазинов. Возможные варианты наборов, их стоимость и товарные запасы представлены в таблице.

Наименование конфет	Вес конфет в наборе, кг.	Запасы конфет, кг
А	В	С
«Спикерc»	0,3	0,2	0,4
«Марс»	0,2	0,3	0,2
«Баунти»	0,2	0,1	0,1
Цена, руб.

Определите оптимальное количество подарочных наборов, обеспечивающее максимальный доход от продажи.

9. Нормы затрат на производство разных видов пиццы, объемы ресурсов и стоимость приведены в таблице. Определите оптимальное количество пиццы, обеспечивающее максимальный доход от продаж.

Продукты	Нормы затрат на изготовление 100 шт. пиццы, кг	Запасы продуктов, кг
ассорти	грибная	салями
Грибы
Колбаса
Тесто
Цена за 100 шт., тыс. руб.

 

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

Ресурсы	Плановый фонд ресурсов	Нормативные затраты ресурсов, кг на 100 блюд
1-е блюда	2-е мясные	2-е рыбные	2-е молочные	2-е прочие
Мясо		4,0	8,0	-	-	3,8
Рыба, т		2,5	-		-	-
Овощи, т		3,2	2,0	3,0	-	4,6
Мука, крупа, макаронные изделия, т		2,1	2,6	2,3	-	2,8
Молоко, л	50 000	6,5	-	-		-
Доход, руб.		1,3	2,0	1,5	0,3	1,7

 

11. Предприниматель арендовал технологическую линию деревообрабатывающих станков для изготовления вагонки. Магазин «Стройматериалы» заказал комплекты из трех элементов: две вагонки длиной 2 м и одной вагонки длиной 1,25 м. Поставщик завозит на грузовом автомобиле доски толщиной 20 мм, шириной 100 мм, длиной по 6,5 м — 200 шт. и длиной по 4 м — 50 шт.

Рассчитайте, как распилить доски, чтобы продать максимальное количество комплектов.

12. Составьте самый дешевый вариант 1 т кормовой смеси в соответствии с требованиями, представленными в следующей таблице.

Питательные вещества	Требования, % от веса	Содержание питательных веществ, %
люцерновая мука	сухая барда	рыбная мука	соевый шрот
Белок	Не менее 35
Жиры	Не менее 1,5				0,5
Клетчатка	Не более 8				6,5
Вес	1т
Стоимость, руб.за 1 т	?

 

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

Вещества	Содержание питательных веществ в 1 кг фруктов	Нормы потребления, г
клубника	яблоки	смородина
Цена, руб. за 1 кг

Определите, какое количество фруктов каждого вида необходимо купить, чтобы выполнить предписание врача с минимальными расходами.

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

Ресурсы	Плановый фонд ресурсов	Нормы затрат ресурсов на 100 блюд
1-е блюда	2-е мясные	2-е рыбные	2-е молочные
Затраты труда на производство, чел.-ч	80 000	3,6	6,0	37,0	2,5
Затраты труда на обслуживание, чел.-ч	140 000	2,2	5,3	5,2	2,7
Издержки производства и обращения, руб.	17 000	4,4	6,7	6,8
Доход, руб.		1,4	2,1	1,6	0,31
Товарооборот, руб.	300 000

 

15. Брокеру биржи клиент поручил разместить 100 000 долл. США на фондовом рынке. Необходимо сформировать такой портфель с ценными бумагами, чтобы получить максимальные проценты с вложенного капитала. Выбор ограничен четырьмя возможными объектами инвестиций-акций А, В, С, Д, которые позволяют получить доход в размерах соответственно 6, 8, 10 и 9% годовых от вложенной суммы. При этом клиент поручил не менее половины инвестиций вложить в акции А и В. С целью обеспечения ликвидности не менее 25% общей суммы капитала нужно поместить в акции Д. Учитывая прогноз на изменение ситуации в будущем, в акции С можно вложить не более 20% капитала. Специфика налогообложения указывает на необходимость вложения в акции А не менее 30% капитала.

Определите распределение инвестиций капитала, обеспечивающее максимальный годовой доход.

16. Сформируйте оптимальный ассортиментный набор торгового предприятия, включающий 60 наименований товаров, если известны ежедневный товарооборот в целом и по товарным позициям количественно-суммового учета, статистические данные

количественного учета неудовлетворенного спроса по всем наименованиям товаров, остатки товарных запасов, торговая площадь, расстояние до поставщиков, транспортные расходы, вид транспорта и фафики завоза товаров.

Определите потери товарооборота за счет неудовлетворенного спроса и затрат на дополнительные расходы по его удовлетворению. Введите условные обозначения показателей хозяйственной деятельности и постройте экономико-математическую модель формирования оптимального ассортиментного набора.

17. Авиакомпания «Аэрофлот» располагает парком из самолетов семи типов.

Тип самолета	Загрузка пассажирами	Время полета без посадки, ч.	Парк самолетов, шт.
минимальная	максимальная
1. ТУ-154
2. ИЛ-62
3. ИЛ-86
4. ИЛ-96		-
5. В-737		-
6. В-777		-
7. А-310

 

Самолеты используются для перевозки пассажиров на пяти авиалиниях, по каждой из них задан объем ежемесячных перевозок.

Постройте оптимальный план перевозки пассажиров.

Рейс	Протяженность линий, ч.	Количество промежуточных посадок	Объем пассажирских перевозок, чел.
I. Египет — Хургада	5,5
II. Испания- Малага	4,5
III. Япония — Токио			35 000
IV. Франция— Париж	3,5
V. США - Нью-Йорк

18—25. Решить задачи методом искусственного базиса.

18. 19.

20. 21.

22. 23.

24. 25.