kurs_mat.ppt

массивы информации n типов с заданными вероятностями Pi обращений к

ним. Di – объем массива i-го типа. Память j-го типа характеризуется быстродействием ti, емкостью Qj и стоимостью единицы памяти Bj. Общая стоимость памяти не должна превышать L.
Распределить массивы информации по m уровням памяти оптимально

специальной форме .
Шаг 1 Составляем симплекс-таблицу, соответствующую специальной форме.
Заметим, что

этой таблице соответствует допустимое базисное решение задачи . Значение целевой функции на этом решении
Шаг 2 Проверка на оптимальность. Если среди элементов индексной строки симплекс – таблицы нет ни одного положительного элемента то, оптимальное решение задачи ЛП найдено: . Алгоритм завершает работу.
Шаг 3 Проверка на неразрешимость.
Если среди есть положительный элемент , а в соответствующем столбце нет ни одного положительного элемента , то целевая функция L является неограниченной снизу на допустимом множестве. В этом случае оптимального решения не существует. Алгоритм завершает работу.
Шаг 4 Выбор ведущего столбца q. Среди элементов выбираем максимальный положительный элемент. Этот столбец объявляем ведущим (разрешающим).
Шаг 5 Выбор ведущей строки p.
Среди положительных элементов столбца находим элемент , для которого выполняется равенство:
Строку p объявляем ведущей (разрешающей). Элемент объявляем ведущим (разрешающим).
Шаг 6 Преобразование симплексной таблицы.
Составляем новую симплекс-таблицу, в которой:
а) вместо базисной переменной записываем не базисную , вместо небазисной переменной записываем базисную;
б) ведущий элемент заменяем на обратную величину ;

в) все элементы ведущего столбца (кроме ведущего ) умножаем на ;
г) все элементы ведущей строки (кроме ведущего) умножаем на ;
д) оставшиеся элементы симплексной таблицы преобразуются по следующей схеме «прямоугольника».
Из элемента вычитается произведение трех сомножителей:
первый - соответствующий элемент ведущего столбца;
второй - соответствующий элемент ведущей строки;
третий - обратная величина ведущего элемента .
Преобразуемый элемент и соответствующие ему три сомножителя как раз и являются вершинами «прямоугольника».
Шаг 7 Переход к следующей итерации осуществляется возвратом к шагу 2.

учета условия целочисленности. Если задача не имеет решения, то неразрешима

и исходная задача ЦЛП. В случае алгоритм завершает работу.
Шаг 2. Пусть найдена оптимальная таблица.
Если элементы bi– целые, то оптимальное решение является целочисленным. В этом случае вычисления заканчиваем. Иначе, переходим к следующему шагу.
Шаг 3. Среди дробных компонент bi таблицы выбираем элемент с максимальной дробной частью и по строке i составляем дополнительное ограничение:


Здесь - [z] целая часть числа (наибольшее целое число, не превышающее число ).
Шаг 4. Добавляем построенное ограничение к последней симплекс-таблице и, применяя двойственный симплекс-метод, находим оптимальное решение. Переходим к шагу 2.
Замечания.
Признаком отсутствия целочисленного решения служит появление в таблице хотя бы одной строки с дробным свободным членом и целыми остальными коэффициентами (поскольку соответствующее уравнение неразрешимо в целых числах).
На шаге 4 двойственный симплекс-метод применяется до тех пор, пока не будет получена оптимальная симплексная таблица (возможно, потребуется несколько итераций).
Если на шаге 4 в базис вводится переменная дополнительного ограничения , то эта строка вычеркивается из симплексной таблицы), ответствующее ограничение является избыточным).

Шаг 1. Проверка на оптимальность. Если ,

то решение -

оптимальное.
Шаг 2. Выбор ведущей строки. Выбираем среди номеров i, для которых , номер k с максимальным по модулю значением
Строка k объявляется ведущей.
Шаг 3. Проверка на неразрешимость. Если в строке нет отрицательных элементов, то двойственная целевая функция неограниченна и, следовательно, прямая задача не имеет допустимых решений. Процесс решения завершается.
Шаг 4. Выбор ведущего столбца s. Выбираем среди отрицательных элементов строки э элемент с номером s, для которого выполняется равенство



Столбец s объявляется ведущим, а элемент - ведущим элементом.
Шаг 5. Проводим стандартное преобразование симплексной таблицы (Шаг 6 из прямого симплекс-метода).

Решаем полученную целевую функцию и ограничения с помощью сначала симплекс методом потом методом Гомори.
Так как у нас 2 типа информации то , то введем значения P, d, t, Q, C и L.
P1=0.5; P2=1; t1=5; t2=3;
d1=8; d2=6; Q1=8; Q2=6;
C1=7; C2=9;
L=500

До...

После...

выход

На главную...

главную...