Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Упростить выражение
Примеры решений Теория игр Решение интегралов Пределы онлайн
Деление столбиком онлайн Транспортная задача Двойственная задача
Графический метод онлайн Производная онлайн Симплекс-метод

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

Раздел математического программирования, в котором на экстремальные задачи налагается условие дискретности переменных при конечной области допустимых решений, называется дискретным программированием. При наличии условия целочисленности имеется в виду подраздел дискретного программирования – целочисленное программирование.

Задача о рюкзаке

Задача о назначении: имеется  n исполнителей, которые могут выполнять n различных работ. Известна полезность cij, связанная с выполнением i-м исполнителем j-ой работы j=1..n, i=1..n. Необходимо назначить исполнителей на работы так, чтобы добиться максимальной полезности, при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должен быть закреплен только один исполнитель.
Математическая модель задачи имеет вид:
F=∑∑cijxij → max
Каждый исполнитель назначается только на одну работу: ∑xij = 1
На каждую работу назначается только один исполнитель: ∑xij = 1
Условие неотрицательности и целочисленности:
xij ≥ 0, xij = {0,1}, i=1..n, j=1..n
Для решения задачи о назначении используется сервис Задача о назначении.

Задача коммивояжера: коммивояжер должен посетить один и только один раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарное пройденное расстояние.
F=∑∑cijxij → min
∑xij = 1
∑xij = 1
Условие неотрицательности и целочисленности:
xij ≥ 0, xij = {0,1}, i=1..n, j=1..n
Добавляется условие прохождения маршрута через все города, т.е. так называемое условие цикличности. Иначе, маршрут должен представлять собой замкнутую ломаную, без пересечений в городах-точках.
Для решения задачи коммивояжёра используется сервис Задача коммивояжёра.

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

Методы решения целочисленных задач

Графический метод
При наличии в задаче линейного программирования двух переменных, задача может быть решена графическим методом.
В системе координат X10X2 находят область допустимых решений, строят вектор С и линию уровня. перемещая линию уровня по направлению С для задач на максимум, определяют наиболее удаленную от начала координат точку и ее координаты.
В случае, когда координаты этой точки нецелочисленные, в области допустимых решений строят целочисленную решетку и находят на ней такие целые числа x1 и x2, которые удовлетворяют системе ограничений и при которых значение целевой функции наиболее близко к экстремальному нецелочисленному решению. Координаты такой вершины являются целочисленным решением.
Аналогично решается задача на минимум. Целочисленному минимуму целевой функции будет соответствовать координаты вершины целочисленной решетки, лежащей в области допустимых решений, наиболее близкой к началу координат в направлении вектора С.
Для решения задачи графическим методом используется сервис Графический метод. Целочисленное программирование.

Пример №1. Решить целочисленную задачу линейного программирования методом Гомори.
В цехе размещены 100 станков 1-го типа и 200 станков 2-го типа, на каждом из которых можно производить детали А1 и А2. Производительность станков в сутки, стоимость 1 детали каждого вида и минимальный суточный план их выпуска представлен в таблице.

Детали

Производительность, деталей, сутки Стоимость одной детали, руб. Минимальный суточный план
Тип 1 Тип 2
А1 20 15 6 1510
А2 35 30 4 4500

Найти количество станков каждого типа, который необходимо выделить для производства деталей Aj, j=1,2, с таким расчетом, чтобы стоимость продукции производимой в сутки, была максимальной.

Решение.
Составим экономико-математическую модель задачи.
x1 – количество станков типа №1, выделенным для производства деталей A1
x2 – количество станков типа №1, выделенным для производства деталей A2
x3 – количество станков типа №2, выделенным для производства деталей A1
x4 – количество станков типа №2, выделенным для производства деталей A2
x1, x2, x3, x4 ≥ 0, x1, x2, x3, x4 целые числа,

Ограничения по плану
20x1 + 15x3 ≥ 1510
35x2 + 30x4 ≥ 4500

Ограничения по количеству
x1 + x2 ≤ 100
x3 + x4≤ 200

Целевая функция
6(20x1+15x3) + 4(35x2+30x4) → max`

Получим следующую систему ограничений:
20x1 + 15x3 ≥ 1510
35x2 + 30x4 ≥ 4500
x1 + x2 ≤ 100
x3 + x4 ≤ 200
120x1 + 140x2 +90x3 + 120x4 → max
x1, x2, x3, x4 ≥ 0, x1, x2, x3, x4 целые числа,

Методы отсечений

Методы отсечений относятся к численным методам решения дискретных задач оптимизации (методам дискретного программирования). Они предназначены для решения целочисленных задач линейного программирования (ЛП).
Идея методов отсечения состоит в следующем. Первоначально решается обычная ("непрерывная") задача ЛП, полученная из исходной задачи отбрасыванием требования целочисленности. Если полученное решение является целочисленным, то оно будет также решением исходной задачи. Если нет, то к ограничениям исходной задачи добавляется новое линейное ограничение, обладающее двумя свойствами:
  1. полученное нецелочисленное решение ему не удовлетворяет;
  2. все целочисленные точки допустимого множества исходной задачи ему удовлетворяют.

Такое ограничение называется правильным отсечением.
Затем решается расширенная непрерывная задача ЛП, т.е. непрерывная задача с добавленным ограничением. Если полученное решение не является целочисленным, добавляется новое правильное отсечение и т.д. Процесс повторяется до тех пор, пока решение очередной расширенной непрерывной задачи ЛП не окажется целочисленным. Таким образом, решение целочисленной задачи ЛП сводится к решению некоторой последовательности обычных задач ЛП.
Геометрически добавление каждого такого линейного ограничения означает проведение гиперплоскости, отсекающей от многогранника допустимых решений очередной непрерывной задачи ЛП оптимальную точку с нецелочисленными координатами, но не затрагивающей ни одной из целочисленных точек этого многогранника. Поэтому методы, опирающиеся на эту идею, получили название методов отсечений.

Пример №2. Мебельная фабрика выпускает диваны, кресла и стулья. Требуется определить, сколько можно изготовить диванов, подлокотников кресел и ножек стульев при известном удельном расходе ресурсов (табл.), чтобы доход был максимальным.

Показатели Изделия Наличие ресурса
спинка дивана подлокотники кресла ножки стула  
Цена, ден. ед. 20 6 8 -
Древесина 10 5 3 206
Трудозатраты 2 7 4 100
Спрос 10 8 12 -
  x1 x2 x3 bi

Причем выпуск спинок дивана может принимать любое значение, подлокотники изготавливаются парами, т.е. их количество должно быть кратно двум, а количество ножек стульев – четырем.

x1 - количество спинок дивана,
x2 - количество подлокотников (кратно двум),
x3 - количество ножек стула (кратно четырем),

Целевая функция
20x1+6*2x2+8*4x3 = max
Система ограничений по ресурсам
10x1+5*2x2+3*4x3≤206
2x1+7*2x2+4*4x3≤100

Система ограничений по спросу
x1≤10
2x2≤8
4x3≤12

x1,x2,x3≥0
x1,x2,x3 - целые

Задачу можно решить либо методом Гомори, либо методом ветвей и границ (см. соответствующие калькуляторы). Оптимальный целочисленный план можно записать так:
x1 = 10
x2 = 2
x3 = 3
F(X) = 12•2 + 20•10 + 32•3 = 320

С учетом комплектации получаем:
x1 = 10 - количество спинок дивана,
x2 = 2*2=4 - количество подлокотников (кратно двум),
x3 = 3*4 = 12 - количество ножек стула (кратно четырем),

Пример №2. В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено 19.3 м2 - площади. На приобретение оборудования предприятие может израсходовать 10 тыс. у.е., при этом оно может купить оборудование двух видов. Комплект оборудования I вида стоит 1000 у.е., а II вида — 3000 у.е. Приобретение одного комплекта оборудования I вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида — на3 ед. Зная, что для установки одного комплекта оборудования1 вида требуется 2 м2 площади, а оборудования II вида — 1 м2 площади, определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.

Решение находим с помощью калькулятора. Составим математическую модель задачи. Предположим, что предприятие приобретет х1 комплектов оборудования 1 вида и х2 комплектов оборудованияII вида. Тогда переменные х1 и х2 должны удовлетворять следующим неравенствам:
2x1 + x2 ≤ 19/3
x1 + 3x2 ≤ 10
Если предприятие приобретет указанное количество оборудования, то общее увеличение выпуска продукции составит:
F = 2x1 + 3x2
По своему экономическому содержанию переменные х1 и х2 могут принимать лишь целые неотрицательные значения, т. е,
x1,x2 ≥ 0
x1,x2 - целые числа.

Далее задача решается методом ветвей и границ или методом отсечений.