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

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

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

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

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