Прикладні задачі лінійного та цілочисельного програмування

Розглянуті питання з теми:

Задача про дієту. Різні способи завдання обмежень. Задача про призначення. Задача оптимального розкрою. Цілочисельне програмування. Метод Гоморі. Задача закріплення літаків за авіалініями.

Л6.2. Задача о диете (о смесях)

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

Конкретнее, пусть в состав дневной нормы питания должно входить не менее чем единиц -го вещества, . Пусть имеется видов продуктов, по цене за единицу -го продукта, причем известно, что в единице -го продукта содержится единиц -го вещества. Тогда, если обозначить через количество единиц -го продукта, которое планируется ввести в дневной рацион, то при плане дневное содержание -го вещества составит единиц, а так как оно должно удовлетворять минимальной дневной потребности, то

(6.1)

При таком плане цена всего дневного рациона составит величину

, (6.2)

которую следует минимизировать.

Если запасы продуктов, из которых составляется рацион, ограничены, то в сформулированную задачу линейного программирования (6.2)-(6.1) добавятся ограничения вида .

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

Л6.2. Смешанная система ограничений

Часто, вместо системы неравенств (3.2), ограничения ЛП-задачи задаются в виде системы уравнений или в виде смешанной системы, состоящей из уравнений и неравенств.

Рассмотрим случай смешанной системы ограничений, когда не все переменные свободны:

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

причем .

Геометрический смысл этой задачи такой же, как и у ОЗЛП, с тем лишь отличием, что пространство, в котором рассматривается задача, имеет размерность меньшую, чем . Действительно, каждое ограничение равенство определяет гиперплоскость, размерность которой (). Многогранник ограничений W в этом случае принадлежит пересечению гиперплоскостей и имеет размерность .

Симплекс-метод может быть применен непосредственно к задаче со смешанной системой ограничений.

Перепишем ограничения в следующей форме:

,

;

составим таблицу:

		...
		...
...	.	.	.	...
		...
		...
...	.	.	.	...
		...
		...

и исключаем из нее свободные переменные так, как это показано в п. Л4.2.

Примечание. Для минимизации количества отрицательных элементов единичного столбца рекомендуется:

а) записывать ограничения-равенства уже в исходную таблицу так, чтобы их свободные члены были неотрицательными;

б) при исключении свободных переменных использовать процедуру нахождения МНО.

Для удобства записи будем считать, что на верх таблицы вместо исключенных переброшены , причем столбцы с перешедшими на верх таблицы нулями вычеркиваются (так, например, всегда будет, если ), так что получена таблица:

		...			...
		...			...
...	.	.	.	.	.	.	...
		...			...
		...			...
...	.	.	.	.	.	.	...
		...			...
		...			...

и отдельно выражения для свободных переменных .

Если на верх таблицы вместо какого-нибудь свободного перейдет ноль из левого столбца (так всегда будет, если ), то расположенный под ним столбец вычеркивается

Контрольні запитання

1. Задача про дієту.

2. Різні способи завдання обмежень.

3. Задача про призначення.

4. Задача оптимального розкрою.

5. Цілочисельне програмування.

6. Метод Гоморі.

7. Задача закріплення літаків за авіалініями.

Рекомендована література: [1,3,8,9,10]

Тема 4.