Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Самая верхняя строка - коэффициенты при целевой функции.

Вторая верхняя строка - сами переменные, входящие в целевую функцию и в систему ограничений.

Основное поле симплекс метода - система коэффициентов из уравнения.

Последняя строка - служит для того, чтобы ответить на вопрос: «оптимален план или нет».

Для первой итерации F0= ci*hi.

m - оценки они рассчитываются по формуле:

j =  ciqij-cj.

Индексная строка позволяет нам судить об оптимальности плана:

1. При отыскании Fmin в индексной строке должны быть отрицательные и нулевые оценки.

2. При отыскании Fmax в индексной строке должны быть нулевые и положительные оценки.

Переход ко второй итерации:

Для этого отыскиваем ключевой (главный) столбец и ключевую (главную) строку.

Ключевым столбцом является тот в котором находится наибольший положительный элемент индексной строки при отыскании Fmin или наименьший отрицательный элемент при отыскании Fmax.

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

На пересечении строки и столбца находится разрешающий элемент.

На этом этапе осуществляется к переходу к последующим итерациям.

Переход к итерациям:

1. Выводится базис ключевой строки, уступая место переменной из ключевого столбца со своим коэффициентом.

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

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

4. Если в главном столбце имеется нулевой элемент, то строка, в которой он находиться переноситься без изменения в последующую итерацию.

5. Остальные элементы переносятся по формуле:

Метод искусственного базиса.

(Вторая симплекс таблица)

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

1. Построение искусственного базиса и оптимизация функции суммы искусственных переменных, т.е. F0=Y1+Y2+…+Yn = 0 (Fmin). Если при этом F0=0, то искусственный базис мы вывели из состава переменных, переходим ко второй фазе – решаем задачу по первой симплекс таблице с действительными переменными. Если же F00, т.е. искусственный базис не выведен из состава переменных – ОЗЛП решений не имеет.

2. Решение преобразованной системы ограничений с заданной целевой функцией и действительными переменными. При этом столбцами искусственных переменных в симплекс методе пренебрегаем.

Замечания:

1. При решении задач на max с искусственным базисом следует переходить к решению на min, меняя лишь только целевую функцию:

Fmax = - Fmin.

1. При решении ОЗЛП с искусственным базисом особое внимание следует обратить на вычисление элементов индексных строк.

a) Для столбцов X вычисление элементов идет по формулам:

j =  qij.

 yi = y1+y2+…+yR.

Hi=F0.

Примечание: только для строк Y.

б) Для столбцов Y работает старая формула:

j =  ciqij-cj.

1. СХЕМА АЛГОРИТМА И ЕЕ ОПИСАНИЕ

1. Начало программы

1. Процедура ввода данных

2. Процедура привидения к каноническому виду

3. Процедура построения симплекс таблицы

4. Функция поиска ключевого столбца

5. Функция поиска ключевой строки

6. Проверка условия: Если в главной строке нулевой элемент.

7. Процедура переноса в следующую итерацию главной строки.

8. Проверка условия: Если в главном столбце нулевые элементы.

9. Процедура переноса столбца в следующую итерацию.

11, 12. Процедура расчета остальных элементов по формуле.

13, 14. Функция исследования на max.

15, 16. Функция исследования на min.

1. Процедура вывода оптимального решения.

2. Конец программы.

5. КРАТКАЯ ХАРАКТЕРИСТИКА ЭВМ И ЕЕ

ПРОГРАМНОГО ОБЕСПЕЧЕНИЯ

Общие сведения о IBM PC

Когда произносят слова "персональный компьютер", обычно подразумевается не что иное, как компьютер типа IBM PC. Именно американская компания IBM в августе 1981 года объявила о выпуске самого первого компьютера, получившего название Personal Computer, или просто PC.

Впрочем, еще до создания IBM PC множеством разных фирм вы пускались компьютеры, которые было бы вполне уместно называть персональными. Даже весьма далекая от электроники фирма Coca - Cola пыталась выпускать собственную модель персонального компьютера!

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

Когда IBM вышла на рынок настольных компьютеров, казавшийся сомнительным и рискованным, разнобой среди персональных компьютеров довольно быстро пошел на убыль. Маленький персональный компьютер IBM PC на процессоре 8088 фирмы Intel оказался тем долгожданным стандартом, который с радостью поддержали многочисленные программисты и фирмы - изготовители прикладного программного обеспечения: наконец - то появился компьютер солидной фирмы, для которого можно было разрабатывать и успешно продавать большими тиражами достаточно сложные, совершенные и универсальные программы. По сути дела, компьютер IBM PC создал не только стабильный и обширный рынок персональных компьютеров, но и огромный рынок прикладного программного обеспечения, на котором за последние полтора десятилетия разбогатело множество венчурных фирм.

Вот яркий тому пример. Компьютер IBM PC почти с самого начала работал под управлением дисковой операционной системы DOS, которую разработала для IBM маленькая и никому тогда не известная фирма Microsoft. Сегодня Microsoft - бесспорный флагман индустрии программного обеспечения, одна из богатейших фирм мира, выпускающая не только операционные средства MS - DOS и Windows для управления компьютерами, но и различные прикладные пакеты. А основатель и руководитель Microsoft Билл Гейтс, несмотря на молодость, один из самых богатых людей.

Разумеется, персоналка IBM PC оказалась только первым шагом в верном направлении. Затем фирма IBM выпустила множество моделей персональных компьютеров XT, AT, PS/2 и PS/1 на различных процессорах Intel 80286, 80386, 80486, Pentium. Все эти компьютеры предназначены для работы под управлением операционных систем DOS, WINDOW’95, OS/2.

Основной поставщик процессоров для IBM-совместимых компьютеров является фирма INTEL. В последнее время многие другие фирмы, такие как AMD, CYREX стали выпускать собственные процессоры, которые полностью совместимы с процессорами фирмы INTEL.

Фирма AMD выпускает более дешевые, но не уступающие по качеству, а иногда и превосходящие процессоры (например процессоры серии K6). И многие фирмы, которые выпускают персональные компьютеры, стали переходить с процессоров фирмы INTEL на процессоры фирмы AMD.

Операционная система MS DOS и другие

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

Главным достоинством MS DOS является ее способность управлять устройствами памяти на магнитных дисках (именно поэтому она названа - дисковая операционная система).

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

В настоящее время существуют более современные операционные системы, с гораздо большим набором возможностей. Это WINDOWS’ 95, OS/2. Но так как эти операционные системы диктуют пользователю «свои условия», такие как работать в окне, программы должны иметь стандартные меню и общий вид, многие программисты делают свои программы по DOS, так как она позволяет более гибко использовать возможности компьютера.

Рекомендуемая конфигурация для программы SIMPLEX METHOD:

Данной программе требуется минимальная конфигурация:

Процессор 386 (рекомендуется 486 or high)

1М оперативной памяти.

2М жесткого диска.

VGA monitor

6. ОБОСНОВАНИЕ ВЫБОРА ЯЗЫКА ПРОГРАММИРОВАНИЯ

Язык Borland Pascal 7.0 обладает свойствами использования графики, строковых типов и констант, любых видов переменных, имеет возможность использования модулей (как уже существующих, так и созданных пользователями). Язык Borland Pascal 7.0 - язык высокого уровня, на нем писать программы намного удобнее так, как языки высокого уровня имеют резервированные слова, которые замещают ряд кодовых символов на языках низкого уровня. Язык Borland Pascal 7.0 имеет практичный интерфейс, который позволяет быстро и удобно совершить те или иные действия. Мой выбор остановился на этом языке.

7. РЕШЕНИЕ ЗАДАЧИ ТЕСТА ДЛЯ

НАПИСАНИЯ И ОТЛАДКИ ПРОГРАММЫ

Для нашей конкретной задачи ресурсные ограничения имеют вид:

1 .2X1 + 1.8X2 + 2.4X3  768

2.4X1 + 1.2X3 + 2.4X4  600

1.2X2 + 1.2X3 + 1.2X4  480

Ограничения по комплектности:

Отсюда составляем систему уравнений:

X1 - 2X2 = 0

X3 - 4X4 = 0

Итак, система ограничений задачи состоит из 5 уравнений и целевой функции:

Fmax = X1+X2+X3+X4

Приводим систему к каноническому виду:

1 .2X1 + 1.8X2 + 2.4X3 +X5  768

2.4X1 + 1.2X3 + 2.4X4 +X6  600

1.2X2 + 1.2X3 + 1.2X4 +X7  480

X1 - 2X2 +Y1 = 0

X3 - 4X4 +Y2 = 0

Приводим целевую функцию к каноническому виду:

Fmax = X1+X2+X3+X4 + 0X5+0X6+0X7-My1-My2

Так как введены искусственные переменные – исследуем на минимум.

Fmin = -X1-X2-X3-X4 - 0X5-0X6-0X7+My1+My2

Таблица 7.1

С имплекс таблица

Индексная строка при исследовании на минимум не содержит положительных элементов, значит, получено оптимальное решение:

Характеристики

Список файлов реферата