ПРИМЕР РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО

Nbsp; МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Ижевский государственный технический университет имени М.Т.Калашникова" (ФГБОУ ВПО «ИжГТУ имени М.Т.Калашникова»)  

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К выполнению

Лабораторной работы по дисциплине «Теория принятия решений», «Системный анализ»

На тему «Симплексный метод решения задачи

Линейного программирования»

Рекомендовано советом факультета «Информатика и вычислительная техника» к использованию в качестве учебно - методических материалов для студентов

специальности:  230102.65 «Автоматизированные системы обработки информации и управления», специальности: 031301.65 «Теоретическая и прикладная лингвистика», направления: 230100.62 «Информатика и вычислительная техника» в области: «Автоматизированные системы обработки информации и управления», «Системы автоматизированного проектирования»,

форма обучения: очная, заочная

(протокол № 8 от 22.11.2013г. )

 

Ижевск 2013

 

Рецензент: Мокроусов М.Н., к.т.н., доцент кафедры АСОИУ.

Составители: Исенбаева Е.Н., старший преподаватель кафедры

АСОИУ.

 

 

Рекомендовано советом факультета «Информатика и вычислительная техника» к использованию в качестве учебно- методических материалов для студентов специальности 230102.65 «Автоматизированные системы обработки информации и управления», специальности: 031301.65 «Теоретическая и прикладная лингвистика»,  направления: 230100.62 «Информатика и вычислительная техника» в области: «Автоматизированные системы обработки информации и управления», «Системы автоматизированного проектирования»,

.

 (протокол № 8 от 22.11.2013г.                 ).

 

 

Методические указания к выполнению лабораторной работы на тему «Симплексный метод решения задачи линейного программирования » (теория и варианты заданий) / сост. Е.Н. Исенбаева.- Ижевск, 20013 г.- 17 с.

 

В методических указаниях описан симплексный метод решения задачи линейного программирования. Сформулирована постановка задачи линейного программирования, рассмотрен алгоритм симплексного метода, проиллюстрированный на примере. Приведены варианты заданий на лабораторную работу.

 

 

Учебное пособие предназначено для студентов, обучающихся по специальности 230102.65 «Автоматизированные системы обработки информации и управления», специальности: 031301.65 «Теоретическая и прикладная лингвистика», направления 230100.62 «Информатика и вычислительная техника» в области: «Автоматизированные системы обработки информации и управления», «Системы автоматизированного проектирования», форма обучения очная, заочная.

 

 

                                                                                     

 

 © Исенбаева Е.Н., составление, 20013

                  © ФГБОУ ВПО «ИжГТУ имени М.Т. Калашникова, 2013

 

 

                                

 

СОДЕРЖАНИЕ

                        

 

ВВЕДЕНИЕ.. 4

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

2. АЛГОРИТМ СИМПЛЕКС-МЕТОДА.. 7

3. ПРИМЕР РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО.. 9

ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ... 9

4. ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ.. 13

5. СОДЕРЖАНИЕ ОТЧЕТА ПО ЛАБОРАТОРНОЙ РАБОТЕ.. 15

6. ВОПРОСЫ ДЛЯ ПРОВЕРКИ ОСТАТОЧНЫХ ЗНАНИЙ.. 16

7.СУЩЕСТВУЮЩИЕ МАТЕМАТИЧЕСКИЕ.. 16

ПРОГРАММНЫЕ СИСТЕМЫ... 16

СПИСОК ЛИТЕРАТУРЫ... 17

 

 

 

 

 

 

ВВЕДЕНИЕ

Данные методические указания предназначены для использования студентами при выполнении лабораторной работы на тему «Симплексный метод решения задачи линейного программирования».

В пособии дается описание распространенного метода решения задачи линейного программирования – симплексного метода. Симплексный метод является классическим и наиболее проработанным методом в линейном программировании. В работе сформулирован алгоритм решения задачи, который проиллюстрирован на примере.

В пособии  предложены варианты заданий на лабораторную работу.

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

 

ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задача линейного программирования (ЛП) возникает из необходимости оптимально использовать имеющиеся ресурсы. Это задачи, связанные с  анализом целей и функций; задачи разработки или совершенствования структур ( производственных структур предприятий, организованных структур объединений); задачи проектирования( проектирование сложных – робототехнических комплексов, гибких производственных систем).

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

Рассмотрим задачу из экономической области на составление оптимальной производственной программы [5]. Для изготовления двух видов продукции Р₁, Р₂ используется три вида сырья S₁, S₂, S₃. Запасы сырья, количество единиц сырья, затраченных на изготовление единицы продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 1.

Таблица 1

 

Вид сырья	Запас сырья, Т	Затраты сырья на единицу продукции
		Р1	Р2
S1	9	1	1
S2	3	0,5	1
S3	3	1	0,5
Прибыль от единицы продукции, денежных единиц		1	2

 

Составить оптимальную производственную программу, т.е. такой план выпуска продукции, чтобы при ее реализации можно было получить максимальную прибыль.

Математически эта задача формулируется следующим образом.

Переменные.

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

x₁ – объем производства продукции Р₁

х₂ – объем производства продукции Р₂

Целевая функция. Конечную цель задачи- получение максимальной прибыли при реализации продукции – выразим как функцию 2-х переменных х₁ и х_2.

Суммарная прибыль Z = x₁ + 2 x₂

Ограничения.

При решении рассматриваемой задачи должны быть учтены ограничения на расход сырья.

х₁ + х₂ £ 9               (для вида S₁),

0,5 х₁ + х₂ £ 3 (для вида S₂),

х₁ + 0,5 х₂ £ 3 (для вида S₃).

Добавим ограничения на не отрицательность значений объемов производства продукции

х₁ ³ 0, х₂ ³ 0.

Итак, математическая модель формулируется следующим образом.

Определить объемы производства х_1, х₂ продукции вида Р₁ и Р₂ в тоннах, при которых достигается максимум целевой функции

Z = х₁ + 2 х₂

при ограничениях

х₁ + х₂ £ 9

0,5 х₁ + х₂ £ 3 

х₁ + 0,5 х₂ £ 3

Таким образом, задача ЛП заключается в отыскании вектора (х_1, х₂,…,х_J,…,х_n), который максимизирует линейную целевую функцию

Z= с₁х₁+с₂х₂+…+с_jх_j+…+с_nх_n,                               (1)

при следующих линейных ограничениях

a₁₁х₁ + a₁₂ х₂ + …+a_1n x_n £ b₁

a₂₁х₁ + a₂₂ х₂ + …+a_2n x_n £ b₂

. . .                                             (2)

a_m1х₁ + a_m2 х₂ + …+a_mn x_n £ b_m

 

x₁ ³0, x₂ ³0,. . .,x_n ³0.                                    (3)

Запись задачи ЛП в виде (1)-(3) называется симметричной  формой представления  задачи линейного программирования.

Эту же задачу ЛП можно представить в векторно-матричной записи:

CX ® max

AX £ B, Х ³ 0, где C = (c₁, c_2,…,c_n), , ,

A=(a_ij), ,  – матрица коэффициентов ограничений,

С - вектор коэффициентов целевой функции

Х- вектор решения.

Область  называется областью допустимых значений (ОДЗ) задачи линейного программирования.

Соотношения (2), (3) называются системами ограничений задачи ЛП.

Так как , то можно ограничиться изучением задачи одного типа.

Решением задачи ЛП называется вектор, удовлетворяющий системе ограничений задачи и оптимизирующий целевую функцию.

Другая форма представления задачи ЛП – каноническая. Она имеет вид:

CX ® max

AX = B, X ³ 0.

Наряду с задачей ЛП в симметричной форме (1)-(3) рассмотрим задачу

BU ® min                                        (4)

A^TU ³ C, U ³ 0,                                    (5)

где  - переменные двойственной задачи.

Задача (4), (5) называется двойственной по отношению к задаче (1)-(3).

 

АЛГОРИТМ СИМПЛЕКС-МЕТОДА

Симплекс метод является наиболее распространенным вычислительным методом, который может быть применен для решения любых задач ЛП как вручную, так и с помощью ЭВМ.

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

1. Рассмотрим задачу ЛП в симметричной форме (1)-(3). Сделаем допущения: В ³ 0.

Введем вектор Y такой, что Y = B ‑ AX, YÎR^m, Y ³ 0,

Y = (x_n+1, x_n+2, . . .,x_n+m)^T. Вектор Y называют балансовым, а x_n+1, x_n+2, . . .,x_n+m – балансовыми переменными.

 В целевую функцию балансовые переменные входят с нулевыми коэффициентами, т.е.

=c₁x₁ + c₂x₂ +…+ c_nx_n + 0x_n+1 +…+ 0×x_n+m

или

, где ,  Î R^n+m.                         (6)

 

Систему ограничений (2) задачи ЛП можно записать:

a₁₁х₁ + a₁₂ х₂ + …+a_1n x_n +х_n+1 = b₁

a₂₁х₁ + a₂₂ х₂ + …+a_2n x_n +х_n+2 = b₂

. . .                                             (7)

a_m1х₁ + a_m2 х₂ + …+a_mn x_n +х_n+m = b_m

 

причем x_j ³ 0,                                   (8)

Таким образом, задачу ЛП (1)-(3) преобразовали из симметричной формы в каноническую.

Итак, вместо задачи (1)-(3) будем искать решение задачи (6)- (8).

2. Положим j = 1. Взяв переменные х₁,…,х_n за свободные и положив их равными нулю, а х_n+1,…,х_n+m – за базисные, находим первую крайнюю точку.

= (0,…,0,b₁,b₂,...,b_m).

       n

3. Обозначим через А_{k -} вектор,  составленный из коэффициентов  ограничений при переменной х_k, С_Б ‑ вектор, составленный из коэффициентов целевой функции, соответствующих базисным переменным, через С_k –  коэффициент целевой функции при переменной x_k.

Вычислим симплексные разности D_k в j-той крайней точке по формуле

D_k = A_k∙ C_Б ‑ _k, .                       (9)

Заполняется симплекс-таблица (таблица 2) по указанным выше правилам.

Таблица 2

 

Базис	СБ		1	2	…	n	n+1	…	n+m
		B	A1	A2	…	An	An+1	…	An+m
xn+1 xn+2 . . . xn+m	n+1 n+2 . . . n+m	b1 b2 . . . bm	a11 a21 . . . am1	a12 a22 . . . am2	… … . . . …	a1n a2n . . . amn	1 0 . . . 0	… … . . . …	0 0 . . . 1
			D1	D2	…	Dn	Dn+1	…	Dn+m

 

4. Если для j-той крайней точки все симплексные разности D_k ³0, , то эта точка оптимальная. Конец решения.

Если есть столбец, в котором симплексная разность D_k0 £ 0 и все элементы столбца a_ik0 £ 0, , то задача ЛП решения не имеет, т.к. целевая функция не ограничена сверху.

В остальных случаях переход к пункту 5.

5. Находим k₀ ‑ направляющий столбец. Выбираем столбец, в котором самая минимальная симплекс разность среди отрицательных симплекс-разностей (напомним, что решаем задачу максимизации) т.е.

D_k0= min D_k                                       (10)

D_k < 0.

Направляющая строка i₀  выбирает из условия

, , α_ik0 › 0 .                   (11)

Итак, направляющий элемент a_i0k0.

Заполняем таблицу, соответствующую новому решению.

6. Выполняем один шаг метода Гаусса, введя в базис вектор А_k0 вместо вектора А_n0, имеющего i₀ – координату, равную 1. Для это используются следующие соотношения:

- новые элементы направляющей строки :

, ;                                  (12)

 

- новые элементы направляющего столбца:

, , причем i ¹ i₀;                      (13)

т.е. в направляющем столбце все элементы равны 0, а направляющий элемент равен 1.

- новые значения остальных элементов матрицы:

, ;                               (14)

- новые значения симплексных разностей:

,;                                     (15)

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

,                             (16)

Получаем (j + 1) крайнюю точку. Полагая j = j + 1, переходим к пункту 4.

Построение симплекс-таблиц продолжается до тех пор, пока не будет получено оптимальное решение.

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

Замечание 2. Пусть в некоторой крайней точке все симплексные разности неотрицательные D_k ³ 0 ( ),т.е. получено оптимальное решение и существует такой  А_k – небазисный вектор, у которого D_k = 0. Тогда максимум достигается по крайней мере  в двух точках, т.е. имеет место альтернативный оптимум. Если ввести в базис эту переменную x_k, значение целевой функции не изменится.

Замечание 3. Решение двойственной задачи находится в последней симплексной таблице. Последние m компонент вектора симплексных разностей( в столбцах балансовых переменных) – оптимальное решение двойственной задачи. Значение целевых функций прямой и двойственной задачи в оптимальных точках совпадают.

Замечание 4. При решении задачи минимизации в базис вводится вектор с наибольшей положительной симплексной разностью. Далее применяется тот же алгоритм, что и для задачи максимизации[3].

 

 

ПРИМЕР РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО

---

Дата добавления: 2018-04-15; просмотров: 363; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!