46279 (665480)

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

Текст из файла

ИСПОЛЬЗОВАНИЕ ТАБЛИЧНОГО СИМПЛЕКС-МЕТОДА ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ОПТИМИЗАЦИИ ЭКОНОМИЧЕСКИХ ЗАДАЧ

ВВЕДЕНИЕ

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

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

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

Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом : найти экстремум некоторой функции многих переменных f ( x₁, x₂, ... , x_n ) при ограничениях g_i ( x₁, x₂, ... , x_n ) b_i , где g_i - функция, описывающая ограничения, - один из следующих знаков , , , а b_i - действительное число, i = 1, ... , m. f называется функцией цели ( целевая функция ).

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

Задачу линейного программирования можно сформулировать так . Найти max

при условии : a₁₁ x₁ + a₁₂ x₂ + . . . + a_1n x_n b₁ ;

a₂₁ x₁ + a₂₂ x₂ + . . . + a_2n x_n b₂ ;

_{. . . . . . . . . . . . . . . . . . . . . . . . . . . .}

a_m1 x₁ + a_m2 x₂ + . . . + a_mn x_n b_m ;

x₁ 0, x₂ 0, _{. . .} , x_n 0 _.

Эти ограничения называются условиями неотрицательности. Если все ограничения заданы в виде строгих равенств, то данная форма называется канонической.

В матричной форме задачу линейного программирования записывают следующим образом. Найти max c^T x

при условии

A x b ;

x 0 ,

где А - матрица ограничений размером ( mn), b^(m1) - вектор-столбец свободных членов, x^{(n 1)} - вектор переменных, с^Т = [c₁, c₂, ... , c_n ] - вектор-строка коэффициентов целевой функции.

Решение х₀ называется оптимальным, если для него выполняется условие с^Т х₀ с^Т х , для всех х R(x).

Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.

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

1) графический;

2) табличный ( прямой, простой ) симплекс - метод;

3) метод искусственного базиса;

4) модифицированный симплекс - метод;

5) двойственный симплекс - метод.

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

Для его применения необходимо, чтобы знаки в ограничениях были вида “ меньше либо равно ”, а компоненты вектора b - положительны.

Алгоритм решения сводится к следующему :

Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.

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

искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума.

Формируется симплекс-таблица.

Рассчитываются симплекс-разности.

Принимается решение об окончании либо продолжении счёта.

При необходимости выполняются итерации.

На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом.

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

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

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

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

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

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

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

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

2. СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ

Для производства двух видов изделий А и В используется три типа технологического оборудования. На производство единицы изделия А идёт времени, часов : оборудованием 1-го типа - а₁ , оборудованием 2-го типа - а₂ , оборудованием 3-го типа - а₃ . На производство единицы изделия В идёт времени, часов : оборудованием 1-го типа - b₁ , оборудованием 2-го типа - b₂ ,_, оборудованием 3-го типа - b₃ .

На изготовление всех изделий администрация предприятия может предоставить оборудование 1-го типа не более, чем на t₁ , оборудование 2-го типа не более, чем на t₂ , оборудование 3-го типа не более, чем на t₃ часов.

Прибыль от реализации единицы готового изделия А составляет рублей, а изделия В - рублей.

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

а₁ = 1 b₁ = 5 t₁ = 10 = 2

а₂ = 3 b₂ = 2 t₂ = 12 = 3

а₃ = 2 b₃ = 4 t₃ = 10

3. РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

3.1 Построение математической модели задачи

Построение математической модели осуществляется в три этапа :

1. Определение переменных, для которых будет составляться математическая модель.

Так как требуется определить план производства изделий А и В, то переменными модели будут:

x₁ - объём производства изделия А, в единицах;

x₂ - объём производства изделия В, в единицах.

2. Формирование целевой функции.

Так как прибыль от реализации единицы готовых изделий А и В известна, то общий доход от их реализации составляет 2x₁ + 3x₂ ( рублей ). Обозначив общий доход через F, можно дать следующую математическую формулировку целевой функции : определить допустимые значения переменных x₁ и x₂ , максимизирующих целевую функцию F = 2x₁ + 3x₂ .

3. Формирование системы ограничений.

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

x₁ + 5x₂ 10 ; 3x₁ + 2x₂ 12 ; 2x₁ + 4x₂ 10 .

Так как объёмы производства продукции не могут принимать отрицательные значения, то появляются ограничения неотрицательности :

x₁ 0 ; x₂ 0 .

Таким образом, математическая модель задачи представлена в виде : определить план x₁ , x₂ , обеспечивающий максимальное значение функции :

max F = max ( 2x₁ + 3x₂ )

при наличии ограничений :

x₁ + 5x₂ 10 ;

3x₁ + 2x₂ 12 ;

2x₁ + 4x₂ 10 .

x₁ 0 ; x₂ 0 .

3.2 Решение задачи вручную

Табличный метод ещё называется метод последовательного улучшения оценки. Решение задачи осуществляется поэтапно.

1. Приведение задачи к форме :

x₁ + 5x₂ 10 ;

3x₁ + 2x₂ 12 ;

2x₁ + 4x₂ 10 .

x₁ 0 ; x₂ 0 .

2. Канонизируем систему ограничений :

x₁ + 5x₂ + x₃ = 10 ;

3x₁ + 2x₂ + x₄ = 12 ;

2x₁ + 4x₂ + x₅ = 10 .

x₁ 0 ; x₂ 0 .

A₁ A₂ A₃ A₄ A₅ A₀

3. Заполняется исходная симплекс-таблица и рассчитываются симплекс-разности по формулам :

₀ = - текущее значение целевой функции

_i = - расчёт симплекс-разностей, где j = 1..6 .

Так как при решении задачи на max не все симплекс-разности положительные, то оптимальное решение можно улучшить.

4. Определяем направляющий столбец j^*. Для задачи на max он определяется минимальной отрицательной симплекс-разностью. В данном случае это вектор А₂

5. Вектор i^*, который нужно вывести из базиса, определяется по отношению :

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

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