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

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

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

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

Университет

–

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

ИСПОЛЬЗОВАНИЕ табличного симплекс - метода для РЕШЕНИЯ ЗАДАЧ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

ДЛЯ

ОПТИМИЗАЦИИ ЭКОНОМИЧЕСКИХ задач

Пояснительная записка к курсовой работе

по дисциплине “Методы исследования операций”

Гибкий магнитный диск

59 листов

Выполнил:

ст. гр. И-22 д

Крыльцова Т.В.

Принял:

Старобинская Л.П.

Севастополь

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

[pic]

при условии : 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 ,

где А - матрица ограничений размером ( m(n), b(m(1) - вектор-столбец

свободных членов, 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 -

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

работать с частью матрицы ограничений. Иногда метод называют методом

обратной матрицы.

В процессе работы алгоритма происходит спонтанное обращение матрицы

ограничений по частям, соответствующим текущим базисным векторам. Указанная

способность делает весьма привлекательной машинную реализацию вычислений

вследствие экономии памяти под промежуточные переменные и значительного

сокращения времени счёта. Хорош для ситуаций, когда число переменных n

значительно превышает число ограничений m.

В целом, метод отражает традиционные черты общего подхода к решению

задач линейного программирования, включающего в себя канонизацию условий

задачи, расчёт симплекс-разностей, проверку условий оптимальности, принятие

решений о коррекции базиса и исключение Жордана-Гаусса.

Особенности заключаются в наличии двух таблиц - основной и

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

формул.

- 10 -

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

Для производства двух видов изделий А и В используется три типа

технологического оборудования. На производство единицы изделия А идёт

времени, часов : оборудованием 1-го типа - а1 , оборудованием 2-го типа

- а2 , оборудованием 3-го типа - а3 . На производство единицы изделия В

идёт времени, часов : оборудованием 1-го типа - b1 , оборудованием 2-го

типа - b2 ,, оборудованием 3-го типа - b3 .

На изготовление всех изделий администрация предприятия может

предоставить оборудование 1-го типа не более, чем на t1 , оборудование 2-

го типа не более, чем на t2 , оборудование 3-го типа не более, чем на t3

часов.

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

изделия В - ( рублей.

Составить план производства изделий А и В, обеспечивающий максимальную

прибыль от их реализации. Решить задачу простым симплекс-методом. Дать

геометрическое истолкование задачи, используя для этого её формулировку с

ограничениями-неравенствами.

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

а2 = 3 b2 = 2 t2 = 12 ( = 3

а3 = 2 b3 = 4 t3 = 10

- 11 -

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. Формирование системы ограничений.

При определении плана производства продукции должны быть учтены

ограничения на время, которое администрация предприятия сможет пре -

- 12 -

доставить на изготовления всех изделий. Это приводит к следующим

трём ограничениям :

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. Канонизируем систему ограничений :

- 13 -

x1 + 5x2 + x3 = 10 ;

3x1 + 2x2 + x4 = 12 ;

2x1 + 4x2 + x5 = 10 .

x1 ( 0 ; x2 ( 0 .

A1 A2 A3 A4 A5 A0

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

разности по формулам :

(0 = [pic] - текущее значение целевой функции

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

| | |C |2 |3 |0 |0 |0 |

|Б |Cб |A0 |A1 |A2 |A3 |A4 |A5 |

|A3 |0 |10 |1 |5 |1 |0 |0 |

|A4 |0 |12 |3 |2 |0 |1 |0 |

|A5 |0 |10 |2 |4 |0 |0 |1 |

| |( |0 |-2 |-3 |0 |0 |0 |

Так как при решении задачи на max не все симплекс-разности

положительные, то оптимальное решение можно улучшить.

4. Определяем направляющий столбец j*. Для задачи на max он

определяется минимальной отрицательной симплекс-разностью. В данном случае

это вектор А2

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

отношению :

min [pic] при аi j > 0

- 14 -

В данном случае сначала это А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 |0 |0 |0 |

|Б |Cб |A0 |A1 |A2 |A3 |A4 |A5 |

|A2 |3 |2 |1/5 |1 |1/5 |0 |0 |

|A4 |0 |8 |13/5 |0 |-2/5 |1 |0 |

|A5 |0 |2 |6/5 |0 |-4/5 |0 |1 |

| |( |6 |-7/5 |0 |3/5 |0 |0 |

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

| | |C |2 |3 |0 |0 |0 |

|Б |Cб |A0 |A1 |A2 |A3 |A4 |A5 |

|A2 |3 |5/3 |0 |1 |1/3 |0 |-1/6 |

|A4 |0 |11/3 |0 |0 |4/3 |1 |-13/6 |

|A1 |2 |5/3 |1 |0 |-2/3 |0 |5/6 |

| |( |8 1/3 |0 |0 |-1/3 |0 |7/6 |

| | |C |2 |3 |0 |0 |0 |

|Б |Cб |A0 |A1 |A2 |A3 |A4 |A5 |

|A2 |3 |3/4 |0 |1 |0 |-1/4 |3/8 |

|A3 |0 |11/4 |0 |0 |1 |3/4 |-13/8 |

Страницы: 1, 2