Контрольная работа по "Информатике"

1вопрос

Принципы построения опорного плана при решении транспортной задачи линейного программирования.

 

Введение

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

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

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

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

Весьма типичной задачей, решаемой с помощью линейного  программирования, является транспортная задача.

Транспортная задача (transportation problem) - одна из наиболее распространенных задач математического программирования (обычно - линейного). В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям и наоборот.

Опорное решение  транспортной задачи

Опорное решение (опорный  план, базисное решение, basic solution) - одно из допустимых решений, находящихся в вершинах области допустимых решений. Оно является решением системы линейных ограничений, которое нельзя представить в виде линейной комбинации никаких других решений.

При решении задачи линейного  программирования можно поступить  следующим образом: найти любое  из таких "вершинных" решений, не обязательно оптимальное, и принять  его за исходный пункт расчетов. Такое решение и будет базисным. Если окажется, что оно и оптимальное, расчет на этом закончен, если нет - последовательно  проверяют, не будут ли оптимальными соседние вершинные точки. Ту из них, в которой план эффективнее, принимают  снова за исходную точку и так, последовательно проверяя на оптимальность  аналогичные вершины, приходят к  искомому оптимуму. На этом принципе строятся так называемый симплексный метод  решения задач линейного программирования, а также ряд других способов, объединенных общим названием "методы последовательного  улучшения допустимого решения (МПУ)": метод обратной матрицы, или модифицированный симплекс-метод, метод потенциалов  для транспортной задачи и другие. Они отличаются друг от друга вычислительными  особенностями перехода от одного базисного  решения к другому, улучшенному.

 Методы построения  начального опорного решения . Построение первоначального плана по способу северо-западного угла

В этом случае не обращают внимания на показатели затрат. Начав заполнение с клетки (1.1) - "северо-западного  угла" таблицы, ступенями спускаются вниз до клетки (k, l), вычеркивая либо одну строку, либо один столбец. На последнем  шаге вычеркиваются последняя (k-я) строка и последний (l-й) столбец. При практическом заполнении таблицы, вычеркивание строк  и столбцов производится лишь мысленно.

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

 Построение первоначального плана по способу минимального элемента

При построении первоначального  плана по способу северо-западного  угла совершенно не учитываются тарифы, потому план получается весьма далеким  от оптимального. Для решения задачи приходится делать много приближений (шагов).

Способ минимального элемента учитывает тарифы и потому позволяет  найти план, более близкий к  оптимальному.

Этот способ заключается  в следующем.

1. Располагаем все клетки  таблицы в очередь по мере  возрастания тарифов, начиная  с минимального.

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

 

Полученный план будет  ациклическим и будет состоять не более чем из k+l-1 компонент. Этот план и принимаем за исходный. Он будет лучше плана, построенного по способу северо-западного угла, и для нахождения оптимума потребуется меньше вычислений.

 

 

Переход от одного опорного решения к другому

Числа  и  называют потенциалами. В распределительную таблицу  добавляют строку  и столбец . Потенциалы  и находят из равенства , справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, а остальные потенциалы определяются однозначно. Если известен потенциал , то , если известен потенциал , то .

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

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

Для свободной клетки с  строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность и т.д. до тех пор, пока не получим оптимальное решение.

 

 

 

 

 

2вопрос

Теория расписания

Введение

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

Теории расписаний -- составление оптимального расписания, где критерием оптимальности служит минимальное значение функции штрафа. Данная задача является классической задачей упорядочения -- наиболее изученного класса задач теории расписаний. В этих задачах распределений задач по ЭВМ и длительности их выполнения предполагаются заданными. Необходимо указать наиболее эффективную стратегию управления очередями задач на выполнение каждой ЭВМ.

Таким образом, решение задачи может быть получено в результате рассмотрения конечного числа расписаний, определяемых возможными последовательностями обслуживания требований. Такие расписания называются перестановочными. Если множество N не упорядочено, то число перестановочных  расписаний n!.

 

Постановка задачи:

1.Алгоритм программ расписание

Пусть n требований обслуживается  одной ЭВМ. Все требования поступают  на обслуживание в момент времени d=0. Длительность обслуживания требования k равна tk единиц времени. Если требование k обслуживается первым, то для подготовки прибора к обслуживанию этого требования необходимо 0k единиц времени, . Если требование j обслуживается непосредственно после требования i, то для перегрузки программного обеспечения ЭВМ необходимо ij единиц времени, 1ijn. Обслуживание требования k желательно завершить к директивному сроку Dk>=0. Функция штрафа k(x)=сk*max(x-Dk,0). Требуется организовать так процесс обслуживания требований, чтобы функция штрафа

была минимальной. -фактическое время завершения обслуживания требования k.

2. Описание алгоритма

1. Инициализация данных

2. Выбор начальной расстановки

3. Определение функции  штрафа

4. Запомнить текущую расстановку  как оптимальную

5. Пока существуют нерассмотренные  варианты

a. Генерировать следующую  расстановку

b. Вычислить функцию штрафа

c. Если текущая расстановка  лучше, запомнить расстановку  как оптимальную

6. Вывод данных

Алгоритм работы программы:

Переменные:

c : вектор;

i,j : целое;

Начало:

i:=n-1;

Пока (c[i]>=c[i+1]) i:=i-1;

j:=n;

Пока (c[j]<=c[i]) j:=j-1;

c:переставить(i,j);

i:=i+1; j:=n;

Пока (i<j)

н.ц.

c:переставить(i,j);

i:=i+1;

j:=j-1;

к.ц.

Конец.

3. Описание программы

Переменные и массивы, используемые в программе:

int n - количество требований;

int [ ] tk - длительность обслуживания требований;

int [ ] dk - директивный срок;

int [ ] c - приоритет выполнения;

int [ ] sigma - подготовка прибора к обслуживанию;

int [ ] tek - текущее расписание;

int [ ] order - порядок обработки заданий;

int [ ] best - оптимальное расписание;

int f - значение функции штрафа;

int perest[ ] - массив перестановок;

Классы и методы используемы  в программе:

Класс Perebor выполняет генерацию перестановок с помощью алгоритма полного перебора

· Метод getPerms возвращает полученные перестановки

· Метод permut генерирует перестановки

· Метод vector меняет местами требования согласно алгоритму

· Метод inv - реверс полученного вектора перестановок

· Метод factorial вычисляет факториал n

Класс Main содержит главный метод, который управляет работой всей программы

· Метод f вычисляет для  каждой перестановки функцию штрафа

· Метод main является главным методом программы, который выполняет управление над программой

Например

Введите n: 3

Ввод  длительности обслуживания требования tk(3): 3 4 5

Ввод  директивных сроков dk(3): 4 5 6

Ввод  времени на подготовку каждого требования и время на перезагрузку ЭВМ sigma(3*3):

3 4 5 4 5 6 1 3 4

Ввод  приоритетов c(3): 4 5 6

Решение с помощью алгоритма полного  перебора:

Перестановка: Функция

штрафа

[0, 1, 2]: 83

[1, 0, 2]: 122

[0, 2, 1]: 71

[2, 0, 1]: 100

[1, 2, 0]: 102

[2, 1, 0]: 116

Минимальная функция штрафа: 71, при порядке: [0, 2, 1].

Время выполнения: 60 мc.

 

Заключение

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

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

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

Программа была написана на языке программирования высокого уровня Java в среде BlueJ