При решении оптимизационных задач

Метод Гомори.

Значительная часть задач хозяйственной и коммерческой деятельности требует целочисленного решения, например, выпуск и распределение товаров, использование агрегатов при загрузке оборудования и т.д. Как быть, если симплекс-метод дает при оптимальном решении дробные значения основных переменных? В этом случае идет поиск наиболее близкого к оптимальному целочисленного решения. Применяются различные методики: 1) отсечения, 2) комбинированные, 3) приближенные. К числу первых относится известный метод Гомори.

Суть метода Гомори состоит в том, что сначала задача оптимизации решается непосредственно, без учета каким будет конечный результат. Если решение получено целочисленное, то задача решена, если нет, то вводится дополнительное ограничение, которое отвечает следующим критериям: 1)оно должно быть линейным, 2)должно отсекать найденный оптимальный нецелочисленный план, 3)не должно отсекать ни один целочисленный план. Такое дополнительное ограничение называется правильным отсечением. Для составления дополнительного ограничения выбирается элемент X_m с наибольшей дробной частью и составляется ограничение вида:

Q_i – Q_i1X₁ – Q_i2X₂…- Q_imX_m (11)

где Q_i=b_i – [b_i], Q_ij=a_ij –[a_ij], при этом [b_i] и [a_ij] целые числа, меньшие b_i и a_ij, но наиболее близкие к ним. Неравенство (11) преобразуется в уравнение путем введения дополнительной неотрицательной переменной и включается в оптимальную симплексную таблицу. Полученная расширенная задача далее решается симплексным методом. Если в процессе решения в симплексной таблице появится уравнение с нецелым свободным членом b_i и целыми коэффициентами a_ij, то данная задача не имеет целочисленного оптимального решения.

Пример №6.

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

Обозначив через Х₁ и Х₂ количество комплектов оборудования типа А и В, целевую функцию доходности выразим как Z(X) = 8X₁+ 5X₂. Найдем максимум целевой функции при ограничениях

5Х₁+ 2Х₂ ,

Х₁+ Х₂ , где Х₁, Х₂ - целые числа.

Вводим новые базисные переменные Х₃, Х₄ и получаем нулевой опорный план:

5Х₁+ 2Х₂ + Х ₃ = ,

Х₁+ Х₂+ Х₄ =6.

Х=(0, 0, 20, 6), который вносим в симплексную таблицу:

План	Базис	Ci/Cj	Значения Xi	X1	X2	X3	Х4	Qmin
	X3							20/5=4
Х4							6/1=6
Z(X) = 0	-8	-5			Индексная строка
	→X1				0,4	0,2		4/0,4=10
Х4				0,6	-0,2		2/0,6=10/3
Z(X) = 8*4=32		- 1,8	1,6		Индексная строка
	Х1		8/3			1/3	-2/3	-
→X2		10/3			-1/3	5/3	-
Z(X) =8*8/3+5*10/3=114/3					Индексная строка

Оптимальный план Х=(8/3, 10/3, 0, 0) включает дробные значения основных переменных, поэтому по методу Гомори выбираем Х₁ с наибольшей дробной частью 2/3 (у Х₂ дробная часть 1/3) и составляем дополнительное ограничение:

Q₁ – Q₁₁X₁ – Q₁₂X₂ – Q₁₃X₃ – Q₁₄X₄ ,

где Q₁=b₁ – [b₁]= 8/3 -2=2/3, Q₁₁=a₁₁ –[a₁₁]= 1-1=0, Q₁₂=a₁₂ –[a₁₂]= 0-0=0,

Q₁₃=a₁₃ –[a₁₃ ]=1/3 – 0=1/3, Q₁₄=a₁₄ –[a₁₄]= -2/3 +1=1/3.

Дополнительное ограничение имеет вид: 2/3 – 0 – 0 -1/3Х₃ – 1/3Х₄ Вводим новую переменную Х₅, и преобразуем полученное неравенство в уравнение: 2/3 – 1/3Х₃ – 1/3Х₄+ Х₅=0,

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

План	Базис	Ci/Cj	Значения Xi	X1	X2	X3	Х4	Qmin
	X1		8/3			1/3	-2/3
Х2		10/3			-1/3	5/3
	Х5		-2/3			-1/3	-1/3
Z(X) = 114/3					Индексная строка
	X1						-1
Х2
→X3
Z(X) = 2*8+4*5=36					Индексная строка

Полученный целочисленный план является наиболее близким к плану с максимальным доходом. При этом остаток первого ресурса составляет 20-(2*5+4*2)=2кв. м, а деньги израсходованы полностью.

Варианты заданий к лабораторной работе №2.

Составить математическую модель производственной задачи и решить ее симплексным методом. Проанализировать полученные результаты и проверить их, используя программу «Симплекс-метод».

2.1. Для грузовых перевозок создается автоколонна. На покупку автомашин выделено 600 тыс.у.е. Можно заказать автомашины марок А,В и С, основные технические и производственные характеристики которых приведены в таблице:

Марка автомашины	Материально-технические характеристики	Производительность машины (т/км)
Стоимость единицы (тыс.у.е.)	Число водителей в смену	Число рабочих смен в сутки
А
В
С				37,8

Количество автомашин в колонне не более 30, общее число водителей не более 144, при этом каждая машина работает три смены, а водитель одну смену в сутки. Сколько автомашин марок А, В, С надо заказать, чтобы производительность колонны была максимальной?

2.2. Для изготовления обуви имеется три вида кожи в количествах: 500, 350 и 200 дм² соответственно. Для пошива мужских ботинок требуется 2дм² кожи первого вида и 2дм² кожи второго вида, для пошива женских туфель – 2,1,1 дм² кожи каждого вида. Доход от продажи пары мужской обуви составляет 40 руб., женской - 80 руб. Сколько пар ботинок и сапожек необходимо выпускать для получения максимальной прибыли?

2.3. Мебельный цех выпускает три вида изделий: шкафы (А), буфеты (В) и диваны (С), расходы ресурсов (в тыс.руб.) на изготовление единицы каждого из них приведены в таблице:

Вид ресурса	Материальные затраты на производство одного изделия
Изделие А	Изделие В	Изделие С
Оборудование
Сырье
Электроэнергия
Доход при реализации (тыс.руб.)

Суточные запасы ресурсов составляют для оборудования 780 тыс. руб., для сырья – 850 тыс.руб., для электроэнергии 780 тыс.руб. Какой объем суточного производства изделий каждого вида обеспечит максимальную стоимость выпускаемой продукции?

2.4. Показатели эффективности возделывания (в расчете на 1 га) трех культур: пшеницы, гречихи и картофеля, приведены в таблице:

Показатели	Посевные культуры (1га)
Пшеница	Гречиха	Картофель
Урожайность (ц)
Затраты труда механизаторов (чел.-дней)	0,5
Затраты конно-ручного труда (чел.-дней)	0,5	0,5
Прибыль от реализации 1ц

Основные производственные ресурсы хозяйства включают площадь пашни – 600га, затраты труда механизаторов – 500 чел.-дней, затраты конно-ручного труда – 900 чел.-дней. Найти оптимальное сочетание посевов пшеницы, гречихи и картофеля.

2.5. На двух участках различного плодородия высевают пшеницу и кукурузу. Площадь первого участка 100га, второго - 200га. Урожайность пшеницы на первом поле - 20ц/га, на втором поле 15 ц /га, у кукурузы 40 ц /га и 30ц /га соответственно. План по сбору пшеницы для хозяйства -1500ц, по кукурузе -4500ц. Найти оптимальный план посева, если доход от продажи 1ц пшеницы 6 долларов, а 1ц кукурузы - 4 доллара, а оба участка должны быть засеяны полностью.

2.6. Предприятие занимается выпуском пиццы. Нормы затрат на производство разных видов пиццы и стоимость приведены в Таблице. Запас продуктов на сутки составляет: грибов -20кг, колбасы -18кг, теста -25кг. Найти оптимальный объем выпуска разных видов пиццы, при котором доход предприятия максимален. При этом тесто, как скоропортящийся продукт, должно быть израсходовано полностью.

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

2.7. Швейная фабрика выпускает женские и мужские костюмы. Расход тканей на изготовление костюмов, запасы сырья и доход от реализации единицы продукции каждого вида указан в таблице.

Виды ресурсов	Нормы затрат на производство 1 ед.	Запасы ресурсов
Женский костюм	Мужской костюм
Ткань, арт.1(м)	1,0	3,0
Ткань,арт.2(м)	1,0	1,0
Доход с 1 ед., тыс. руб.

Согласно исследованиям маркетингового отдела количество выпускаемых женских костюмов должно быть как минимум на 20 шт. больше по сравнению с количеством мужских. Каков объем выпуска костюмов, при котором доход фабрики максимален?

2.8. Для изготовления изделий двух видов имеется 100кг металла. На изготовление одного изделия 1-го вида расходуется 2 кг металла, а изделия 2-го вида - 4кг. Отпускная стоимость одного изделия 1-го вида – 200 руб., а изделия 2-го вида – 300 руб., причем изделий 1-го вида требуется изготовить не менее 13, а 2 –го вида не более 40. Составить план выпуска продукции, при котором выручка будет наибольшей.

2.9. Цех производит два вида продукции на токарных и фрезерных станках, располагая ежедневными ресурсами в 900 и 300 человеко-часов, соответственно. Производство 1 тонны продукции первого и второго вида требует 150 и 300 человеко-часов работы на токарных станках, а также 100 и 50 человеко-часов работы на фрезерных станках. По условию заказчика продукция первого вида должна составлять не менее 1/3 от общей массы продукции. Доход от реализации 1 тонны продукции первого и второго вида составляет 12 и 19 тыс.руб. Найти оптимальный выпуск продукции, при котором доход цеха максимален.

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

Вещество	Содержание питательных веществ в 1кг фруктов	Норма потребления,г
Клубника	Яблоки	Смородина
Р1
Р2
Р3

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

2.11. На ферме по откорму бычков требуется составить кормовую смесь, одна тонна которой содержала бы белка не менее 35% от веса, жиров не менее 2,8%, а клетчатки не более 8% от веса. Содержание питательных веществ в различных компонентах смеси и их стоимость приведены в таблице:

Питательные вещества	Содержание питательных веществ в %
Люцерновая мука	Соевый шпрот	Рыбная мука
Белок
Жиры
Клетчатка
Стоимость, тыс. руб. за 1т

Каков самый дешевый вариант смеси?

2.12. Три марки тракторов следует распределить для выполнения боронования на поле 360га. Производительность техники и эксплуатационные затраты приведены в таблице:

Марки тракторов	Марки тракторов
ДТ 75М	МТЗ 80	Т 40М
Производительность га/смена
Эксплуатационные затраты (у.е.)

Требуется выполнить работы с минимальными затратами при условии использования не более 14 машин.

2.13.(дополнительно). Клиент поручил брокеру разместить 1000000 рублей на фондовом рынке, сформировав портфель с ценными бумагами, чтобы получить максимальные годовые проценты с вложенного капитала. Выбор брокера ограничен акциями трех групп предприятий: финансовой А (доход 10% годовых), сырьевой В (8%) и электронной С промышленности (12%). При этом клиент для надежности поручил не менее 60% общей суммы вложить в акции групп А и В, а в акции С должно быть вложено меньше, чем в акции группы В?