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

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования

"Ижевский государственный технический университет имени М.Т.Калашникова"

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

 

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

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

на тему "Задача линейного программирования"

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

специальности: 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. ДВОЙСТВЕННАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 8

3. ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ.. 9

4. ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ.. 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) если прямая задача является задачей максимизации, то двойственная будет задачей минимизации, и наоборот;

2) коэффициенты целевой функции прямой задачи c₁,c₂,…,c_n становятся свободными членами ограничений двойственной задачи;

3) свободные члены ограничений прямой задачи b₁,b₂,…,b_m становятся коэффициентами целевой функции двойственной задачи;

4) матрицу ограничений двойственной задачи получают транспонированием матрицы ограничений прямой задачи;

5) знаки неравенств в ограничениях изменяются на обратные;

6) число ограничений прямой задачи равно числу переменных двойственной задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи.

Переменные y₁,y₂,…,y_m двойственной задачи иногда называют теневыми ценами.

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

 

 

---

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

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

---

---

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