- •Курсовой проект
- •1 Математическая модель
- •2 Теоретическая часть
- •2.1 Алгоритм метода искусственного базиса
- •2.2 Алгоритм симплекс-метода для задачи на минимум
- •2.3 Алгоритм метода Гомори
- •2.4 Алгоритм двойственного симплекс-метода
- •3 Описание интерфейса программы
- •4 Анализ модели на чувствительность список использованных источников
- •Приложение а пример решения задачи
- •Приложение б результат работы программы
Омский государственный технический университет
Кафедра «Автоматизированные системы обработки информации и управления»
Курсовой проект
по дисциплине «Математическое программирование»
Пояснительная записка
Руководитель проекта
Зыкина А.В.
Разработал студент гр. АС–331
Ершов Евгений Сергеевич
Омск – 2004
СОДЕРЖАНИЕ
ЗАДАНИЕ
8. Распределение памяти ЭВМ I
Рассматривается многоступенчатая система хранения данных: на верхнем уровне используются ЗУ большого объема, но с малым быстродействием, на нижнем – ЗУ небольшого объема, но с быстродействием, обеспечивающим производительность системы.
Пусть n– число массивов информации;di ,i=1,n– объемi-го массива информации;Pi ,i=1,n– вероятность использованияi-го массива в оперативной памяти;m– число уровней памяти;Θj,j=1…m– объем памятиj-го типа;tj,j=1…m– быстродействие памятиj-го типа.
Распределить массивы информации по уровням памяти так, чтобы свести к минимуму время их обработки (суммарное время обращения к памяти).
1 Математическая модель
n– число массивов информации;
di ,i=1…n– объемi-го массива информации;
Pi ,i=1…n– вероятность использованияi-го массива в оперативной памяти;
m– число уровней памяти;
Θj ,j=1…m– объем памятиj-го типа;
tj ,j=1…m– быстродействие памятиj-го типа (время доступа);
xij – i-й массив находится вj-й памяти {0,1};
–i-й массив находится только в одном типе памяти;
– общий объем информации содержащейся в памятиj-го типа ≤ объема памятиj-го типа.
2 Теоретическая часть
2.1 Алгоритм метода искусственного базиса
Ш1:Приводим задачу ЛП к канонической форме
с неотрицательными правыми частями .
Ш2:В каждуюi-ю строку ограничений вводим искусственную неотрицательную переменнуюxi и строим вспомогательную задачу ЛП вида:
Эта задача имеет допустимое базисное решение . Для этого целевую функцию необходимо выразить через свободные переменные:
Ш3:Для построенной вспомогательной задачи строим симплексную таблицу:
|
b |
… | ||
… | ||||
… | ||||
. |
. |
… | ||
… |
и находим оптимальное решение вспомогательной задачи с помощью симплекс-метода.
Ш4:Еслии все переменныеявляются небазисными, тоmпеременных извойдут в базис и система ограничений, соответствующих симплексной таблице, будет иметь вид:
Так как переменные , то их исключили, не нарушив при этом равенств. Выражая целевую функцию основной задачичерез небазисные переменныесистемы, получим исходную задачу.
Ш5:Если, но в базисе остались искусственные переменные, для которых, то проводим для каждой искусственной переменной из базиса следующее преобразование симплексной таблицы: выбираем ведущим столбцом столбец такой переменной, для которой элемент индексной строки, а элемент столбца . В этом случае строка искусственной переменнойбудет ведущей и после стандартного преобразования симплексной таблицы (Ш6 из прямого симплекс-метода) искусственная переменнаявыведется из базиса. В результате получим симплексную таблицу, соответствующуюШ4.
Ш6:Если, то допустимого решения в исходной задаче не существует (не могут все искусственные переменныебыть равными нулю), а значит, система ограничений задачи несовместна – процесс решения исходной задачи завершается.