Примеры

Пример 1. Оптимизация капиталовложений.

Имеется 10 работ (А₁  А₂), каждая из которых характеризуется тремя технико-экономическими показателями:

а_j — трудозатраты;

b_j — размер, необходимых капиталовложений;

с_j — ожидаемый экономический эффект.

Исходные данные приведены в следующей таблице:

Общие трудозатраты не должны превышать 20. Общий объем капиталовложений не должен превышать 20. Определите, какие из 10 работ следует выполнить, чтобы максимизировать ожидаемый экономический эффект, учитывая следующие условия взаимообусловленности и взаимоисключения:

Решение. Помимо целевой функции и двух ограничений по общему объему трудозатрат и капиталовложений, данную задачу характеризует следующая система неравенств:

В результате расчетов получаем х* = (0101110010).

Пример 2. Оптимизация производственной программы.

Автомобилестроительный завод выпускает три модели автомобилей, которые изготавливаются последовательно в трех цехах. Мощность цехов составляет 300, 250 и 200 человекодней в декаду. В первом цехе для сборки одного автомобиля первой модели требуется б человекодней, второй модели — 4 и третьей модели — 2 человекодня в декаду соответственно. Во втором цехе трудоемкость равна 3,4 и 5 человекодней соответственно, в третьем — по 3 человекодня на каждую модель. Прибыль, получаемая заводом от продажи одного автомобиля каждой модели, составляет соответственно 15, 13 и 10 тыс. долл.

Постройте модель для определения оптимального плана.

Решение. Пусть х_i — количество выпускаемых автомобилей i-й модели в течение декады (i = 1,..., n). В принятых обозначениях модель имеет вид:

Вопросы

Вопрос 1. В задаче оптимального выбора проектов развития предприятия сформулировано дополнительное условие: реализация первого проекта возможна только в случае реализации хотя бы одного из двух проектов — второго или третьего.

Пусть х_i = 1, если вариант i реализуется, и х_i = 0 в противном случае. Тогда дополнительное условие может быть формализовано в виде:

Вопрос 2. В задаче оптимального выбора проектов развития предприятия сформулировано дополнительное условие: реализация первого проекта возможна в случае реализации хотя бы одного из двух проектов — второго или третьего, причем хотя бы один из них должен быть реализован.

Пусть х_i = 1, если вариант i реализуется, и x_i = 0 в противном случае. Тогда дополнительное условие может быть формализовано в виде:

Вопрос 3. Задача какого типа из указанных ниже не обязательно содержит хотя бы одну целочисленную переменную:

1) унимодулярная задача с целочисленной исходной информацией;

2) задача с неоднородной разрывной целевой функцией;

3) комбинаторная задача;

4) задача с неделимостями;

5) производственно-транспортная задача.

Вопрос 4. Задача целочисленного линейного программирования

заменой переменных сведена к задаче линейного программирования с булевыми переменными. Чему равно минимальное число переменных в новой задаче?

Варианты ответов:

1) 2; 2) 3; 3) 5; 4) 6; 5) 7.

Задачи

Задача 1. В текущем году заводу необходимо:

1) закупить два универсальных станка с ЧПУ общей стоимостью 200 тыс. руб. Для этого требуются трудовые ресурсы в объеме 250 человекодней и производственные площади 100 м²;

2) смонтировать транспортный конвейер стоимостью 100 тыс. руб. Необходимы трудовые ресурсы 190 человекодней и производственные площади 200 м².

Для проведения этих мероприятий завод располагает финансовыми ресурсами 250 тыс. руб., трудовыми — 200 человекодней и производственными площадями 200 м².

Недостаток средств и ресурсов можно компенсировать, проведя некоторые из следующих мероприятии:

1) внедрить новые резцы для обработки металла. Экономия трудозатрат — 130 человекодней, финансовые затраты — 50 тыс. руб.;

2) провести профилактический ремонт станочного парка. Трудозатраты — 10 человекодней, прибыль — 20 тыс. руб.;

3) внедрить систему контроля качества продукции. Экономия трудозатрат — 190 человекодней, затраты производственных площадей — 50 м², прибыль — 5 тыс. руб.;

4) реализовать устаревшее оборудование. Трудозатраты — 60 человекодней, высвобождение производственных площадей — 200 м², прибыль — 300 тыс. руб.;

5) провести инвентаризацию запасов материальных ресурсов. Трудозатраты — 20 человекодней, высвобождение производственных площадей — 150 м².

Вопрос: Какое минимальное количество мероприятий следует провести, чтобы закупить станки с ЧПУ и смонтировать транспортный конвейер?

Задача 2. Для реконструкции машиностроительного предприятия было представлено 10 проектов, каждый из которых характеризуется четырьмя агрегированными показателями: затратами труда, энергии, материалов, денежных средств, а также ежегодной прибылью в случае реализации проекта. Соответствующие данные и объем имеющихся ресурсов приведены в таблице:

При выборе проектов необходимо учесть ряд ограничений технологического характера:

1) одновременно может быть реализовано не более семи проектов;

2) проекты 5 и 8 исключают друг друга;

3) проект 1 может быть реализован лишь при условии реализации проекта 2;

4) проект 4 может быть реализован лишь при условии реализации хотя бы одного из двух проектов: либо проекта 3, либо проекта 10.

Вопросы:

1. Какова максимальная прибыль?

2. Следует ли реализовывать проект 3?

ЗАДАНИЕ 3. ТРАНСПОРТНАЯ ЗАДАЧА

Рассматривается задача транспортировки продукта, который в определенных количествах предлагается различными производителями. Известны потребности нескольких потребителей в этом продукте. Требуется определить, от каких производителей и в каких объемах должны получать продукт потребители. Поставки должны осуществляться таким образом, чтобы совокупные издержки на транспортировку продукта были минимальными.

После того как вы выполните задания, предлагаемые в этой главе, вы будете уметь составлять и использовать для экономического анализа:

• замкнутую и открытую транспортные задачи;

• транспортную задачу с запретами;

• транспортную задачу с фиксированными перевозками;

• транспортную задачу с ограничениями на пропускную способность;

• транспортную задачу с фиксированными доплатами;

• транспортную таблицу.

Модели

Обозначения:

а_i — величина предложения продукта в пункте i (i = 1, ..., n);

b_j — величина спроса на продукт в пункте j (j = 1,..., т);

c_ij — затраты на транспортировку единицы продукта из пункта i в пункт j;

x_ij — количество продукта, перевозимого из пункта i в пункт j.

Модель транспортной задачи:

Здесь (1) — целевая функция (минимум затрат на транспортировку продукта);

(2) — ограничения по величине предложения в каждом пункте производства;

(3) — ограничения по величине спроса в каждом пункте потребления;

(4) — условия неотрицательности объемов перевозок.

1. Замкнутая транспортная задача. Общее предложение равно общему спросу:

Это необходимое и достаточное условие существования допустимого плана задачи (1)-(4).