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

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 Построение математической модели задачи

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

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 .

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 0 = - текущее значение целевой функции

d i = - расчёт симплекс-разностей, где 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*

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

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

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

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

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

4. АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ

4.1 Построение двойственной задачи и её численное решение

Проведение анализа на чувствительность связано с теорией двойственности, поэтому в курсовой работе необходимо построить двойственную задачу и найти её численное решение.

Для рассматриваемой модели двойственная задача имеет вид :

min T( y ) = min ( 10y1 + 12y2 + 10y3 ) при условиях

y1 + 3y2 + 2y3 ³ 2 А1

5y1 + 2y2 + 4y3 ³ 3 А2

y1 ³ 0 , y2 ³ 0 , y3 ³ 0. А3, А4, А5

Оптимальное решение двойственной задачи получается при решении прямой задачи из последней симплекс-таблицы. В результате получаем оптимальное решение двойственной задачи :

Yопт = ( 0, 1/4, 5/8, 0, 0 ), для которого Т(yопт) = 9 1/4.

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

Похожие работы

Симплекс метод в форме презентации

Скачать

25716

1

1

... - метод для решения задач линейного программирования. Задачи курсовой заботы: 1.         привести теоретический материал; 2.         на примерах рассмотреть симплекс метод; 3.         представить данную курсовую работу в виде презентации. Математическое программирование Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи ...

Графический метод и симплекс-метод решения задач линейного программирования

Скачать

33353

9

3

... ограничения несовместны, множество планов пусто и задача ЛП решения не имеет.    Рис. 1.4 Рис. 1.5 Рис. 1.6 2. Симплекс-метод   2.1 Идея симплекс-метода Рассмотрим универсальный метод решения канонической задачи линейного программирования , , , с n переменными и m ограничениями-равенствами, известный как симплекс-метод.  Множество планов канонической задачи – ...

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

Скачать

82416

8

19

... 0 505/103 0 792/103 669/103 500/103 Анализ Таблицы 6 позволяет сделать вывод о допустимости и оптимальности базиса XБ4=(x5, x7, x1, x2, x4)T. 3.4 Результат решения задачи планирования производства В результате решения поставленной задачи симплекс-методом получили набор производимой продукции x=(x1, x2, x3, x4, x5)=( 15145/103, 8910/103, 0, 1250/103, 3255/103), который удовлетворяет всем ...

Сравнительный анализ методов оптимизации

Скачать

48110

9

8

... Метод преобразования целевой функции, метод штрафных функций, табличный симплекс – метод. Список используемой литературы 1.  А.Г.Трифонов. Постановка задачи оптимизации и численные методы ее решения; 2.  Б. Банди. Методы оптимизации. Вводный курс., 1988; 3.  Мендикенов К.К. Лекции Приложение А using System; using System.Collections.Generic; using System.ComponentModel; using System. ...