Получение целочисленных решений

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

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

Значительная часть задач хозяйственной и коммерческой деятельности требует целочисленного решения, например, выпуск и распределение товаров, использование агрегатов при загрузке оборудования и т.д. Как быть, если симплекс-метод дает при оптимальном решении дробные значения основных переменных? В этом случае идет поиск наиболее близкого к оптимальному целочисленного решения. Применяются различные методики: 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), который вносим в симплексную таблицу:

Оптимальный план Х=(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,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Согласно исследованиям маркетингового отдела количество выпускаемых женских костюмов должно быть как минимум на 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кг клубники 100руб., яблок – 50 руб., смородины – 80 руб.

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

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

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

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

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

Поиск по сайту: