Некоторые модели задач ЦЛП

Задачи с неделимостью. Класс задач с неделимостями представляется двумя типами моделей. Первый тип моделей это обычные целочисленные модели ЛП. Т.е.

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

Приведем примеры задач такого типа.

1)Пусть есть m видов транспортных единиц для перевозки груза .Грузоподъемность i- ой транспортной единицы составляет p_i тонн. Груз должен быть доставлен по n направлениям , по b_i тонн каждому. Фонд полезного времени i- ой транспортной единицы - T_i часов. Продолжительность доставки i- ой транспортной в j- ом направлении - t_ij часов, а стоимость этой доставки - c_ij грн. Необходимо определить количество транспортных единиц каждого вида, которые идут вовсе направления. Распределение будем считать оптимальным, если суммарная стоимость доставки всех грузов будет минимальной.

Построим модель. Обозначим через x_ij - количество транспортных средств i– ого вида идущих в j- ом направлении. Тогда

ограничения на фонд времени

ограничения на доставку грузов

ограничения на неизвестные

Условие целочисленности неизвестных обязательна, так как это количество транспортных средств.

2) Задача про ранец. Есть n предметов , заданы величины: a_j -вес предмета j; c_j - ценность предмета j. Необходимо загрузить ранец, грузоподъемность которого равна А, набором предметов с максимальной суммарной ценностью.

Введем переменные x_j, которые принимают значения

тогда задача про ранец запишется так

В других вариантах этой модели может быть несколько типов ограничений, например, ограничения не только на суммарную массу предметов, но и на суммарный объем и т.д.Такие задачи называются багатомерными задачами про ранец. А если, предположить, что каждый предмет может загружаться не в одном экземпляре, а в нескольких, то ограничения заменятся условием неотрицательности и целочисленности всех неизвестных.

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

1)Пример задачи: задача про назначения. Пусть есть работ n и n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами c_ij . Необходимо найти назначения кандидатов на все работы, которые дают минимальные суммарные затраты; причем каждого кандидата можно назначить только на одну работу и каждая работа может быть занята только одним кандидатом.

Иначе говоря, решение этой задачи представляет собой перестановку (p₁,p₂,…,p_n), каждое из чисел описывается соответствием .При этом единственность выбора варианта выполняется автоматически и наша цель сводится к минимизации суммы по всем перестановкам .

Это типовая экстремально комбинированная задача. Ее решение путем прямого перебора, т.е. вычисление значении целевой функции при всех перестановках и сравнения их, практически невозможно при больших n, так как число перестановок будет .Известно, что каждая такая перестановка может быть описана точкой в двухмерном евклидовом пространстве. Эту точку удобно представить в виде матрицы . Элементы x_ij этой матрицы можно описать так:

Элементы матрицы Х должны удовлетворять следующим условиям

Эти условия говорят, что в каждой строке и в каждом столбце матрицы Х есть только по одной единице. Иначе говоря, каждый кандидат имеет работу и каждая работа имеет своего кандидата. Эти назначения должны быть такими, чтобы минимизировать суммарные затраты, получаем целевую функцию

Условие, что x_ij это булевая переменная можно записать так .

2) Задача про коммивояжера. Пусть n есть городов. Известна матрица расстояний между любой парой городов .Выезжая из начального города, коммивояжер должен побывать во всех городах ровно один раз и вернуться в начальный город. Необходимо узнать в каком порядке нужно объезжать города, чтобы пройденный путь был минимальным.

Введем неизвестные

Тогда получаем задачу

Первая группа ограничений говорит о том, что коммивояжер выезжает из каждого города один раз, а вторые о том, что он один раз въезжает в каждый город.

ЛЕКЦИЯ 11.