Целочисленное программирование

Целочисленное программирование

(дискретная оптимизация)

Значительная часть экономических ЗЛП требует целочисленного решения. Это, прежде всего, задачи по производству и распределению неделимой продукции (число станков при загрузке оборудования, число турбин в энергосистеме и т.д.). ЗЛП может записываться в любой форме при условии, что переменные х_j 0, но принимают только целые значения. Округление значений переменных может дать решение, но не лучшее среди целочисленных значений, или привести к решению, не удовлетворяющему условиям задачи. Покажем на примере получение целочисленных значений переменных.

Пример 4.1. Принято решение об установке в цехе площадью 19/3 м² оборудования. На приобретение этого оборудования выделено 10 млн. руб. Можно купить оборудование 2-х видов. Приобретение одного комплекта оборудования 1-го вида стоит 1 млн. руб., а 2-го вида 3 млн. руб. Приобретение одного комплекта оборудования 1-го вида позволяет предприятию увеличить выпуск продукции в смену на 2 шт., а одного комплекта оборудования 2-го вида – на 4 шт. Для установления одного комплекта оборудования 1-го вида требуется 2 м² площади, а одного комплекта оборудования 2-го вида 1 м². Определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.

Пусть x₁ и x₂ – количество комплектов оборудования 1-го и 2-го видов соответственно в штуках. Тогда ЭММ может быть представлена в виде:

max

x₁ 0, x₂ 0 и целые числа.

Покажем решение этой задачи в графическом и аналитическом виде.