Пример. Если fi и хотя бы одно значение hij дробны, то с учётом введённых обозначений целых и дробных чисел дополнительное ограничение по целочисленности примет вид

Если f_i и хотя бы одно значение h_ij дробны, то с учётом введённых обозначений целых и дробных чисел дополнительное ограничение по целочисленности примет вид

Примечания. 1) Если f_i – дробное число, а все h_ij – целые числа, то задача линейного программирования не имеет целочисленного решения.

2) Ограничение целочисленности может быть наложено не на все переменные, а лишь на их часть. В этом случае задача является частично целочисленной.

Графический метод решения задач

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

В системе координат Х₁ОХ₂ находят область допустимых решений, строят и линию уровня. Перемещая линию уровня по направлению для задач на максимум, находим наиболее удалённую от начала координат точку и её координаты.

В том случае, когда координаты этой точки нецелочисленные, в области допустимых решений строят целочисленную решётку и находят на ней такие целые числа, которые удовлетворяют системе ограничений и при которых значение целевой функции наиболее близко к экстремальному целочисленному решению. Координаты такой вершины и являются целочисленным решением.

Аналогично решается задача на минимум.

Прогнозирование эффективного использования производственных площадей

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

РЕШЕНИЕ. Составим математическую модель задачи. Предположим, что фирма приобретает х₁ комплектов дополнительного оборудования 1-го вида и х₂ комплектов оборудования 2-го вида. Математическая модель задачи будет иметь вид

при ограничениях:

- целые.

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

ОТВЕТ. Фирме следует приобрести один комплект оборудования 1-го вида и три комплекта оборудования 2-го вида, что обеспечит её при имеющихся ограничениях на производственные площади и денежные средства максимальное увеличение выпуска продукции, равное 14 усл.ед. в смену.

Метод Гомори

Решим эту же задачу методом Гомори.

сi	БП
х1	х2	х3	х4	bi
	x3 x4					19/3
∆j	-2	-4
	x3 x2	5/3 1/3			-1/3 1/3	10/3
∆j	-2/3			4/3	40/3
	x1 x2			3/5 -1/5	-1/5 2/5	9/5 41/15
∆j			2/5	6/5	218/15

Получим

Найдём дробные части чисел 9/15 и 41/15:

Учитывая дробные части чисел 3/5 и -1/5:

составляем дополнительное ограничение целочисленности для 1-й строки:

или

которое вводим в таблицу:

сi	БП
х1	х2	х3	х4	х5	bi
	x1 x2			3/5 -1/5 3/5	-1/5 2/5 4/5	-1	9/5 41/15 4/5
	x1 x2 х3				-1 2/3 4/3	-1/3 -5/3	4/3
∆j				2/3	2/3

Получили

Дата добавления: 2014-01-11