Введение. 
Решения задач линейного программирования

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

Задачи и методы, относящиеся к перечисленному кругу вопросов, в литературе именуются по-разному. Наибольшее распространение получил термин «целочисленное программирование», однако встречаются и такие как «дискретное программирование», реже «комбинаторное (или диофантово) программирование».

Существуют задачи линейного программирования, которые формально к целочисленным не относятся, но при соответствующих исходных данных всегда обладают целочисленным планом. Примеры таких задач — транспортная задача и ее модификации (задачи о назначениях, о потоках в сетях).

Исторически первой задачей целочисленного типа является опубликованная в 1932 г. венгерским математиком Е. Эгервари задача о назначении персонала. В 1955 г. на Втором симпозиуме по линейному программированию была рассмотрена задача о бомбардировщике, известная как задача о ранце.

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

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

Имеется n исполнителей, которые могут выполнять n различных работ. Стоимость выполнения i-работы j-м исполнителем известна и равна. Необходимо распределить исполнителей по работам (назначить одного исполнителя на каждую работу) так, чтобы минимизировать суммарные затраты, связанные с выполнением всего комплекса работ.

Известна полезность связанная с выполнением i-м исполнителем j-й работы.

.

Для составления математической модели задачи обозначим через факт назначения или не назначения i-го исполнителя на j-ю работу. Так как количество исполнителей равно количеству работ и каждый из них может быть назначен только на одну работу, то должны принимать только два значения: 1 или 0. Такие переменные называют булевыми. Итак,.

.

Приходим к задаче: найти план назначения, который максимизирует суммарную полезность назначений:

.

при следующих ограничениях.

Каждый исполнитель назначается только на одну работу:

.

На каждую работу назначается только один исполнитель.

.

Условия неотрицательности и целочисленности (булевости):

.

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

Задача о назначении имеет самое широкое применение. Например, при закреплении машин за маршрутами, распределении инструментов для обработки различных марок стали, рабочих или бригад и т. д. В каждом конкретном случае математическая модель задачи может иметь специфику. Например, в задаче распределения алгоритмов между вычислительными машинами число распределяемых алгоритмов, как правило, не равно числу машин. При назначении на должности для некоторых исполнителей существуют ограничения. Прежде всего необходимо отметить, что если задача о назначениях ставится при условии получения максимального эффекта, то ее сводят к задаче на минимум. Пусть дана матрица эффективности C=[]. В каждом столбце найдем максимальный элемент. Построим матрицу С'=[ ].

Задача.

.

где — область допустимых решений системы (1) — (3), эквивалентна задаче.

.

В самом деле,.

.

Функция Z' достигает минимума при условии, что Z достигает максимума,.

Если в задаче о назначениях число исполнителей равно числу работ, то говорят о закрытой модели, в противном случае — об открытой модели задачи о назначениях. Если число m меньше числа исполнителей n (mn вводят m-n фиктивных исполнителей. Соответствующие элементы матрицы потерь можно полагать очень большими («блокируют бесконечностью»).

И еще одна деталь. Если по каким-либо причинам запрещается выполнение какой-либо работы каким-либо исполнителем, то и в этом случае соответствующую клетку «блокируют бесконечностью» (ставят большую стоимость М). Точное решение задачи о назначениях можно найти венгерским методом, методом динамического программирования и др. Существует также много приближенных методов. Хорошее приближение дает модификация способа Фогеля для определения опорного плана транспортной задачи. [3].