Реферат по предмету "Математика"


Решение задач симплексным методом

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ
 Для производства двух видов изделий А и В используется три типа технологического оборудования. На производство единицы изделия А идёт времени, часов: оборудованием 1-го типа — а1, оборудованием 2-го типа — а2, оборудованием 3-го типа — а3.На производство единицы изделия В идёт времени, часов: оборудованием 1-го типа — b1, оборудованием 2-го типа — b2 ,, оборудованием 3-го типа — b3 .

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

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

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

а1 = 1 b1 = 5 t1 = 10 a= 2

а2 = 3 b2 = 2 t2 = 12 b= 3

а3 = 2 b3 = 4 t3 = 10

3.РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ 3.1 Построение математической модели задачи


На произв-во изделия А, часов

На произв-во изделия B, часов

Предпр-е предоставит, часов

Оборуд-е 1го типа

1

5

10

Оборуд-е 2го типа

3

2

12

Оборуд-е 3го типа

2

4

10

Прибыль от реализации, за ед. изд-я

2

3



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

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

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

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

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

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

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

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

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

 x1 + 5x2 £10;3x1 + 2x2 £12; 2x1 + 4x2£10 .

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

 x1 ³0; x2³0 .

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

max F = max ( 2x1 + 3x2 )

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

 x1 + 5x2 £10;

3x1 + 2x2 £12;

2x1 + 4x2£10 .

x1 ³0; x2³0 .
    продолжение
--PAGE_BREAK--3.2 Решение задачи вручную
Табличный метод ещё называется метод последовательного улучшения оценки. Решение задачи осуществляется поэтапно.

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

x1 + 5x2 £10;

3x1 + 2x2 £12;

2x1 + 4x2£10 .

x1 ³0; x2³0 .

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

x1 + 5x2 + x3 =10;

3x1 + 2x2 + x4 = 12;

2x1 + 4x2 + x5 = 10 .

x1 ³0; x2³0 .

A1 A2 A3 A4 A5 A0

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

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





C

2

3







Б



A0

A1

A2

A3

A4

A5

A3



10

1

5

1





A4



12

3

2



1



A5



10

2

4





1



d




-2

-3







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

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

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

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

min  при аi j > 0

В данном случае сначала это А3 .

5. Заполняется новая симплекс-таблица по исключеню Жордана — Гаусса :

 а). направляющую строку i* делим на направляющий элемент:

a i j = a i j / a i j, гдеj = 1..6

 б). преобразование всей оставшейся части матрицы :

a ij = aij — a i j×aij, гдеi ¹i*, j ¹j*





C

2

3







Б



A0

A1

A2

A3

A4

A5

A2

3

2

1/5

1

1/5





A4



8

13/5



-2/5

1



A5



2

6/5



-4/5



1



d


6

-7/5



3/5





В результате преобразований получаем новую симплекс-таблицу :

Повторяя пункты 3 — 5, получим следующие таблицы :





C

2

3







Б



A0

A1

A2

A3

A4

A5

A2

3

5/3



1

1/3



-1/6

A4



11/3





4/3

1

-13/6

A1

2

5/3

1



-2/3



5/6



d


8 1/3





-1/3



7/6





C

2

3







Б



A0

A1

A2

A3

A4

A5

A2

3

3/4



1



-1/4

3/8

A3



11/4





1

3/4

-13/8

A1

2

7/2

1





1/2

-1/4



d


9 1/4







1/4

5/8

Так как все симплекс-разности положительны, то оптимальное решение найдено :

X = ( 7/2, 3/4, 11/4, 0, 0 ) ( единиц )

max F = 9 1/4 ( рублей )

    продолжение
--PAGE_BREAK--


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

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем реферат самостоятельно:
! Как писать рефераты
Практические рекомендации по написанию студенческих рефератов.
! План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом.
! Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач.
! Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты.
! Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ.

Читайте также:
Виды рефератов Какими бывают рефераты по своему назначению и структуре.