3. Модели целочисленного линейного программирования
Нередко приходится рассматривать задачи, в которых неизвестные величины могут принимать только целочисленные значения. Например, задачи, связанные с определением необходимого числа рабочих мест или количества дорогостоящих станков. При решении таких задач с целочисленными переменными методы линейного программирования неприменимы.
Другая сфера применения целочисленных моделей — выбор вариантов. В соответствующих задачах все или некоторые переменные могут принимать только два значения: 0 или 1. Такие переменные называют булевыми.
Задача линейного целочисленного программирования формулируется следующим образом: найти такое решение, при котором линейная функция
принимает максимальное или минимальное значение при ограничениях
Наиболее известные методы решения целочисленных задач — метод отсечения и метод ветвей и границ. В Mathcad нет реализаций методов решения задач целочисленного линейного программирования. Существуют задачи, в которых можно определить пределы изменения значений переменных из системы ограничений, при этом полученные диапазоны изменения значений переменных позволяют получить решение задачи, осуществив полный перебор всех возможных значений переменных. Учитывая небольшое количество возможных вариантов, а также использование программных средств для автоматизации вычислений будем решать такие задачи методом полного или сплошного перебора.
Метод заключается в переборе всех возможных вариантов сочетаний допустимых значений, проверке выполнения для каждого из ограничений и вычислении в удовлетворительных случаях соответствующих значений целевой функции. Из полученного множества значений выбирается максимальное (или минимальное), а набор значений переменных для него и будет решением задачи. Данный метод имеет простой алгоритм и может быть легко реализован с использованием средств программирования пакета Mathcad.
3.1. Решение задачи целочисленного линейного программирования в Mathcad
Если вычисление функции требует выполнения нескольких операторов, то в этом случае необходимо использовать операторы из палитры программирования (рис. 10). Составление программы начинается с нажатия кнопки Add line (Добавить строку), после чего в появившиеся шаблоны можно вставлять операторы программирования. Реализуем поэтапно, например, программу вычисления функции, которая задает единичный скачок в точке а (рис. 11).
Рис. 10. Панель программирования
Рис. 11. Создание программы вычисления функции
В этом примере вначале набрано имя функции с двумя формальными параметрами х и а, затем оператор присвоения и нажата кнопка Add line. На втором этапе в первый шаблон вставлен оператор if (если). На следующем этапе в шаблоны оператора if вставлено значение функции при х>а. Затем нажата кнопка otherwise (иначе), и в шаблон этого оператора вставлено нулевое значение функции, которое она принимает при х Обращение к функции с фактическими параметрами дает требуемые значения функции.
В более сложных программах необходима операция присвоения. Оператор присвоения в палитре программирования изображен в виде стрелки, направленной влево: .
Рассмотрим пример использования оператора цикла for (для), показанный на рис. 12. После ввода оператора присвоения нажать кнопка Add line дважды.
Рис. 12. Программа с оператором цикла for
На первом этапе обнуляем переменную суммирования s и вводим во вторую строку программы оператор for, получая в результате и третью строку — шаблон для тела цикла. Далее вставляем в шаблоны для оператора цикла имя циклической переменной и пределы ее изменения. На следующем этапе вводим оператор тела цикла, осуществляющий суммирование квадратов целых чисел и, добавляя еще одну строку нажатием Add line, в последнюю строку программы вводим имя переменной s как результат выполнения программы — суммы квадратов всех целых чисел от m до n.
3.2. Пример решения задачи целочисленного линейного программирования в Mathcad
Предприниматель для приобретения оборудования выделяет 40 денежных единиц. Оборудование должно быть размещено на площади, не превышающей 100 кв. м. Предприниматель может заказать оборудование трех типов, стоимость, занимаемая производственная площадь и производительность которых приведены в таблице:
Составить оптимальный план приобретения оборудования, обеспечивающий максимальную общую производительность при условии, что количество единиц 1-го типа оборудования должно быть не меньше, чем количество единиц 2-го типа.
Построим математическую модель задачи. Обозначим через , количество единиц оборудования соответственно 1, 2 и 3 типа. Математическая модель задачи примет вид:
Это задача целочисленного линейного программирования. Найдем решение задачи средствами Mathcad. Будем использовать средства программирования пакета Mathcad для реализации метода полного или сплошного перебора. Для этого определим пределы изменения переменных. Из ограничений получим, что , а
Протокол решения задачи в Mathcad приведен ниже.
Ответ. Максимальную производительность 80 можно получить приобретением 2 единиц 1-го типа оборудования и 5 единиц 3-го типа оборудования.
Задание 3.
Построить математическую модель задачи. Решить задачу целочисленного линейного программирования средствами Mathcad.
Вариант 1. Для приобретения оборудования выделено 34 ден. ед. Оборудование должно быть размещено на площади, не превышающей 60 кв. м. Можно заказать оборудование двух видов: менее мощные машины типа А стоимостью 3 ден. ед, требующие производственную площадь 3 кв. м (с учетом проходов) и обеспечивающие производительность за смену 200 единиц продукции, и более мощные машины типа В стоимостью 4 ден.ед., занимающие площадь 5 кв.м. и обеспечивающие производительность за смену 300. Требуется составить оптимальный план приобретения оборудования, обеспечивающий максимальную общую производительность при условии, что фермер может приобрести не более 8 машин типа В.
Вариант 2. Для приобретения оборудования выделено 38 ден. ед. Оборудование должно быть размещено на площади, не превышающей 50 кв. м. Можно заказать оборудование двух видов: менее мощные машины типа А стоимостью 3 ден. ед, требующие производственную площадь 3 кв. м (с учетом проходов) и обеспечивающие производительность за смену 150 единиц, и более мощные машины типа В стоимостью 4 ден.ед., занимающие площадь 4 кв.м. и обеспечивающие производительность за смену 100. Требуется составить оптимальный план приобретения оборудования, обеспечивающий максимальную общую производительность при условии, что фермер может приобрести не более 8 машин типа В.
Вариант 3. Для приобретения оборудования выделено 40 ден. ед. Оборудование должно быть размещено на площади, не превышающей 60 кв. м. Можно заказать оборудование двух видов: менее мощные машины типа А стоимостью 3 ден. ед, требующие производственную площадь 4 кв. м (с учетом проходов) и обеспечивающие производительность за смену 120 единиц, и более мощные машины типа В стоимостью 4 ден.ед., занимающие площадь 5 кв.м. и обеспечивающие производительность за смену 130. Требуется составить оптимальный план приобретения оборудования, обеспечивающий максимальную общую производительность при условии, что можно приобрести не более 8 машин типа В.
Варианты 4-10. Предприниматель для приобретения оборудования выделяет С денежных единиц. Оборудование должно быть размещено на площади, не превышающей S кв. м. Предприниматель может заказать оборудование трех типов, стоимость, занимаемая производственная площадь и производительность которых приведены в таблице. Составить оптимальный план приобретения оборудования, обеспечивающий максимальную общую производительность при условии, что количество единиц 1-го типа оборудования должно быть не меньше, чем количество единиц 2-го типа.
Графическое решение задачи линейного программирования с помощью MathCAD.
Пример 2. Найти значения переменных хь хг, которые доставляют максимум и минимум функции z=3xi+2×2 при ограничениях х,+х2 2х1+х2>2, Х1-х2 0, х2>0.
? Переходим от неравенств к равенствам, выражая из них х2 через xi, и строим на поле X-Y Plot область допустимых решений вместе с одной линией уровня,
Каждое неравенство-ограничение означает, что допустимые значения переменных лежат в первой четверти выше или ниже соответствующей прямой (на рис.6.5 эти направления указаны стрелками). Область допустимых решений для данной задачи пятиугольник ABCDE, ограниченный пересекающимися прямыми и координатными осями Ох і и Ох2 (рис. 6.5).
Линии уровня функции Z=Zq Рис.6.5. Нахождение ОДР в MathCADe семейство параллельных прямых 3xi+2x 2=zo- Из рис. 6.5
видно, что целевая функция z достигает наибольшего значения в самой правой вершине пятиугольника ABCDE — в точке D, находящейся на пересечении 1-го и 3-го ограничений. Вычисления в MathCAD координат этой точки и значения
целевой функции в ней приведены на рис. 6.6.
xl + х2 = 4 2(х1 ,х2) := 3×1 + 2 ? х2
xl — х2 = 2 find(xl ,х2) —> I I z(3,1) = 11
Рис.6.6. Вычисления в MathCAD координат точки
максимума и значения целевой функции
Из рис. 1 также видно, что минимум целевой функции достигается в точке А, координаты которой очевидны из графика: Л(1,0), zmjn 3.
Задача ЛИ решена графически:
Можно рекомендовать следующую последовательность графического решения задачи ЛП в MathCAD:
- 1. Установить режим автоматических вычислений.
- 2. Записать уравнения прямых, ограничивающих ОДР, в виде Хг=кх+Ь.
- 3. Изобразить на графике соответствующие прямые и определить вид ОДР.
- 4. Построить ДЛЯ ОДНОГО ИЛИ нескольких значений Zq линии уровня целевой функции Z=Z().
- 5. Если задача имеет решение, найти вершину (или вершины — в случае альтернативного решения), в которой находится искомый экстремум, определить ее координаты и вычислить значение целевой функции в ней.