Двойственность задачи в линейном программировании

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

 

 

 

 

Курсовая работа

 

Дисциплина:                                                                                     Численные методы

Тема:                                     Двойственность задачи в линейном программировании

Выполнила:                                                                                      студент(ка) го курса

                                                                                                                   группы

                                                                                                 специальность:

__________

Проверил:                                                                                                   преподаватель

                                                                                           

Дата сдачи работы:                                                                  «__» __________ 2013 г.

Оценка:                                                                                                           __________

Подпись преподавателя:                                                                               __________

 

 

 

 

 

 

г.

2013 г. 
Оглавление

 

 

Введение ……………..……………………………………………………………….3-5         

1. Двойственность задачи в линейном программировании……………….6-17

1.1. Прямые и двойственные задачи в линейном программировании

1.2. Основные теоремы двойственности

1.2.1 Несимметричные двойственные  задачи

1.2.2 Симметричные двойственные  задачи

1.3 Виды математических моделей двойственных задач

1.4 Двойственный симплексный метод

2. Разработка программы ……………….17-27

2.1 Постановка задачи

2.2 Построение математической модели

2.3 Описание решения двойственной  задачи

Заключение ..………………………………………………………………………28-29

Список используемой литературы …………….………………………………...30-31

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

Одним из приоритетных направлений  процесса информатизации современного общества является информатизация образования - внедрение средств новых информационных технологий в систему образования. Это сделает возможным:

- совершенствование механизмов у правления системой образования на основе использования автоматизированных банков данных научно-педагогической информации, информационно-методических материалов, а также коммуникационных сетей;

- совершенствование методологии и стратегии отбора содержания, методов и организационных форм обучения, соответствующих задачам развития личности обучаемого в современных условиях информатизации общества;

- создание методических систем обучения, ориентированных на развитие интеллектуального потенциала обучаемого, на формирование умений самостоятельно приобретать знания, осуществлять информационно-учебную, экспериментально - исследовательскую деятельность, разнообразные виды самостоятельной деятельности по обработке информации;

- создание и использование компьютерных тестирующих, диагностирующих, контролирующих и оценивающих систем.

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

В работе рассмотрена  одна из сторон процесса информатизации общества и образования - создание одной  из форм обучения с использованием средств новых информационных технологий - электронно-методическое пособие  «Двойственные задачи линейного  программирования».

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

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

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

Объектом данного исследования является использование и создание компьютерных средств обучения.

В качестве предмета исследования рассматривается содержание и реализация электронного пособия.

Под двойственной задачей  понимается вспомогательная задача линейного программирования, формулируемая  с помощью определённых правил непосредственно  из условий прямой задачи. Заинтересованность в определении оптимального решения  прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными. Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных.

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

Для достижения поставленной цели были поставлены следующие задачи:

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

 

 

 

1. Двойственность в линейном программировании

 

1.1 Прямые и двойственные  задачи линейного программирования

 

С экономической точки зрения двойственную задачу можно интерпретировать так: какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов b_i и величинах стоимости единицы продукции C_j минимизировать общую стоимость затрат? А исходную задачу определим следующим, образом: сколько и какой продукции x_j(_j =1,2,…, n) необходимо произвести, чтобы при заданных стоимостях C_j (j=1,2,…, n) единицы продукции и размерах имеющихся ресурсов b_i(_i=1,2,…, n) максимизировать выпуск продукции в стоимостном выражении. Большинство задач линейного программирования изначально определяются как исходные или двойственные задачи. Сделав вывод можно говорить о паре двойственных задач линейного программирования.

Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования, состоящей, как мы уже знаем, в нахождении максимального значения функции:

 

F=c₁x₁+c₂x₂+…c_nx_n

 

при условиях

 

Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной на минимум.

2. Матрица

 

 

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

 

 

в двойственной задаче получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов – строками).

3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в соотношениях системы двойственной задачи – коэффициенты при неизвестных в целевой функции исходной задачи.

5. Если переменная x_j исходной задачи может принимать только лишь положительные значения, то j-е условие в системе двойственной задачи является неравенством вида «>». Если же переменная x_j может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i – соотношение в системе исходной задачи является неравенством, то i-я переменная двойственной задачи . В противном случае переменная у_j может принимать как положительные, так и отрицательные значения.

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

Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной. Решение двойственной задачи может быть получено из решения исходной и наоборот. Связующим фактом этих двух задач являются коэффициенты C_j функции исходной задачи. Данные коэффициенты называются свободными членами системы ограничений двойственной задачи. Коэффициенты B_i системы ограничений исходной задачи называются коэффициентами двойственной задачи. Транспонированная матрица коэффициентов системы ограничений исходной задачи является матрицей коэффициентов системы ограничений двойственной задачи.

Рассмотрим задачу использования  ресурсов. У предприятия есть t видов ресурсов в количестве b_i (i=1, 2,…, m) единиц, из которых выпускается n видов продукции. На изготовление 1 ед. i-й продукции тратится a_ij ед. t-гo ресурса, ее стоимость составляет C_j ед. Необходимо определить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Примем за x_j (j=1,2,…, n) количество ед. j-й продукций и составляет максимальное значение линейной функции

 

Z=C₁x₁+C₂x₂+ … +C_nx_n

 

Определим ресурсы, которые  потребуются для изготовления товара. Обозначим за единицу стоимости  ресурсов единицу стоимости выпускаемого товара. А через у_i (j=1,2,…, m) стоимость единицы i-го ресурса. Т.е. стоимость всех затраченных ресурсов, которые используются для изобретения единицы j-й продукции, составляет. Цена израсходованных ресурсов не должна превышать цены окончательного товара.

 

1.2 Основы теоремы  двойственности

 

1.2.1. Несимметричные  двойственные задачи

Теорема двойственности:

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

Сформулируем двойственную задачу. Необходимо определить матрицу-строку Y=(y₁, y₂,…, y_m), которая максимизирует линейную функцию f=YA₀ и удовлетворяет ограничениям

 

YA>С 

 

Сформулируем исходную задачу. Определить матрицу-столбец X=(x₁, x₂,…, x_n), которая минимизирует линейную функцию Z=СХ и. удовлетворяет ограничениям

 

AX=A0,Х>0

 

Как в исходной так и в двойственной задачах А=(a_ij) – матрица коэффициентов системы ограничений, A₀=(b₁, b₂,…, b_m) – матрица-столбец, C=(c₁, c₂,…, c_n) – матрица-строка. Теорема двойственности устанавливает связь между оптимальными планами пары двойственных задач.

Теорема двойственности гласит: если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем для экстремальных значений линейных функций выполняется соотношение minZ =maxf. Если линейная функция одной из задач не ограничена, то другая не имеет решения

Доказательство.

Будем считать, что исходная задача имеет оптимальный план. План определен симплексным методом. Можно считать, что конечный базис состоит из т первых векторов A₁, A₂,…, A_m.