Поиск по сайту

Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ

реферат на тему: Использование табличного симплекс-метода для решения задач линейного программирования для оптимизации экономических задач

скачать реферат

Министерство образования Украины

Севастопольский Государственный Технический Университет

Департамент ИС

метод сжатия текстовой информации

Пояснительная записка к курсовой работе по дисциплине “Методы защиты и кодирования информации”

Гибкий магнитный диск 59 листов

Выполнил: ст. гр. И-32 д Крыльцова Т.В. Принял: Василенко В.А

Севастополь 1997

- 3 -

СОДЕРЖАНИЕ

ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1. КРАТКИЙ ОБЗОР АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДАННОГО ТИПА . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1 Математическое программирование . . . . . . . . . . . . . . . . . . . 6 1.2 Табличный симплекс - метод . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Метод искусственного базиса . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Модифицированный симплекс - метод . . . . . . . . . . . . . . . . . 8 2. СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ . . . . . . . . . . . . 10 3. РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1 Построение математической модели задачи . . . . . . . . . . . . . . 11 3.2 Решение задачи вручную . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4. АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ . . . . . . . . . . . . 16 4.1 Построение двойственной задачи и её численное решение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.2 Определение статуса ресурсов . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.3 Определение значимости ресурсов . . . . . . . . . . . . . . . . . . . . . . 17 4.4 Определение допустимого интервала изменения запаса ресурсов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.5 Исследование зависимости оптимального решения от изменений запасов ресурсов . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

- 4 -

5. ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 6. ВЫВОДЫ И РЕКОМЕНДАЦИИ ПО ПРАКТИЧЕСКОМУ ИСПОЛЬЗОВАНИЮ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 ПРИЛОЖЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 ЛИТЕРАТУРА . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 - 5 -

ВВЕДЕНИЕ

Цель данного курсового проекта - составить план производства требуемых изделий, обеспечивающий максимальную прибыль от их реализации, свести данную задачу к задаче линейного программирования, решить её симплекс - методом и составить программу для решения задачи этим методом на ЭВМ. - 6 -

1. КРАТКИЙ ОБЗОР АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДАННОГО ТИПА

1.1 Математическое программирование

Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом : найти экстремум некоторой функции многих переменных f ( x1, x2, ... , xn ) при ограничениях gi ( x1, x2, ... , xn ) bi , где gi - функция, описывающая ограничения, - один из следующих знаков , , , а bi - действительное число, i = 1, ... , m. f называется функцией цели
Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ

 ( целевая функция ). Линейное программирование - это раздел математического программирования, в котором рассматриваются методы решения экстремальных задач с линейным функционалом и линейными ограничениями, которым должны удовлетворять искомые переменные. Задачу линейного программирования можно сформулировать так . Найти max при условии : a11 x1 + a12 x2 + . . . + a1n xn b1 ; a21 x1 + a22 x2 + . . . + a2n xn b2 ; . . . . . . . . . . . . . . . . . . . . . . . . . . . . am1 x1 + am2 x2 + . . . + amn xn bm ; x1 0, x2 0, . . . , xn 0 . Эти ограничения называются условиями неотрицательности. Если все ограничения заданы в виде строгих равенств, то данная форма называется канонической.

- 7 -

В матричной форме задачу линейного программирования записывают следующим образом. Найти max cT x при условии A x b ; x 0 , где А - матрица ограничений размером ( mn), b(m1) - вектор-столбец свободных членов, x(n 1) - вектор переменных, сТ = [c1, c2, ... , cn ] - вектор-строка коэффициентов целевой функции. Решение х0 называется оптимальным, если для него выполняется условие сТ х0 сТ х , для всех х R(x). Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации. Для решения задач данного типа применяются методы: 1) графический; 2) табличный ( прямой, простой ) симплекс - метод; 3) метод искусственного базиса; 4) модифицированный симплекс - метод; 5) двойственный симплекс - метод.

1.2 Табличный симплекс - метод

Для его применения необходимо, чтобы знаки в ограничениях были вида “ меньше либо равно ”, а компоненты вектора b - положительны. Алгоритм решения сводится к следующему : 1. Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам. 2. Если в исходной системе ограничений присутствовали знаки “ равно ”

- 8 -

или “ больше либо равно ”, то в указанные ограничения добавляются искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума. 3. Формируется симплекс-таблица. 4. Рассчитываются симплекс-разности. 5. Принемается решение об окончании либо продолжении счёта. 6. При необходимости выполняются итерации. 7. На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом.

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

Данный метод решения применяется при наличии в ограничении знаков “ равно ”, “ больше либо равно ”, “ меньше либо равно ” и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами , а в задачи минимизации - с положительными . Таким образом из исходной получается новая - задача. Если в оптимальном решении - задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении - задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.

1.4 Модифицированный симплекс - метод В основу данной разновидности симплекс-метода положены такие особен -

- 9 -

ности линейной

скачать реферат

---

1 2 3 4 ...    последняя