Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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




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


 

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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



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

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

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

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

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

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

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

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



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

 

 

ЛЕКЦИЯ 11.


mylektsii.ru - Мои Лекции - 2015-2019 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал