Инфоурок Другое Научные работыНаучная работа "Симплекс метод"

Научная работа "Тригонометрические подстановки"

Скачать материал
Скачать тест к материалу

 

Содержание

Введение.............................................................................................................. 3

1. Понятие о задаче линейного программирования........................................ 4

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

3. Об угловых точках канонической задачи.................................................. 12

4. Метод последовательного улучшения плана............................................. 13

5. Симплекс-метод ............................................................................................ 13 ....

Заключение....................................................................................................... 18

Список литературы.......................................................................................... 20

 

 

 

 

           

Введение

Наиболее изученным разделом математического программирования является линейное программирование.

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

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

В 1939 году Л.В. Канторович опубликовал работу «Математические методы организации и планирования производства», в которой сформулировал новый класс экстремальных задач с ограничениями и разработал эффективный метод их решения, таким образом, были заложены основы линейного программирования.

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

Универсальным методом решения задач линейного программирования является симплекс-метод [6]. Классический симплекс-метод был открыт в 1947 Дж. Данцигом. 

Симплекс-метод решения задачи линейного программирования основывается на переходе от одного опорного плана к другому таким образом, что каждый раз значение целевой функции стремится в направлении убывания (или возрастания) [2].

 

 


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

Пример 1. Для изготовления двух видов продукции P1 и P2 используют 4 вида ресурсов S1, S2 , S3, S4 . Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице 1 (цифры условные).

Таблица 1

Вид ресурса

Запас ресурса

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

P1

P2

S1

18

1

3

S2

16

2

1

S3

5

-

1

S4

21

3

-

 

Прибыль, получаемая от единицы продукции P1 и P2 , соответственно 2 и 3 руб. Составить экономико-математическую модель по нахождению плана производства продукции, который максимизирует суммарный доход.

Решение: Первым шагом составления математической модели задачи является введение переменных. Обозначим x1, x2 – число единиц продукции соответственно P1 и P2 , запланированных к производству. По смыслу задачи переменные: x1 0, x2 0.

Для их изготовления (см. таблицу 1) потребуется 1x1 3x2 единиц ресурса S1, 2x1 1x2 единиц ресурса S2 , 1x2 единиц ресурса S3, и 3x1 единиц ресурса S4 . Так как потребление ресурсов S1, S2 , S3, S4 не должно превышать их запасов – соответственно 18, 16, 5 и 21 единицы. 

Таким образом, введённые переменные должны удовлетворять системе неравенств

x1 3x2 18,

                                                                                   2x x1  2 16,

                                                                                     x2 5,          

3x1 21,

x1 0, x2 0.

Завершающим шагом построения экономико-математической модели задачи является выписывание целевой функции, которая в данной задаче является общим доходом от реализации продукции. Доход от реализации продукции P1 составит 2x1 руб., а от реализации продукции P2 составит 3x2 руб. Таким образом, общий доход, подлежащий максимизации, равен F 2x1 3x2.

Из решения примера 1 видим, что задача линейного программирования состоит в поиске максимума (минимума) линейной функции

n

                                              F c x1 1 c x2 2  ... c xn n c cj j max minX G                      (1)

j1

на множестве допустимых решений G, которое описывается системой ограничений

                                                                                                          n             

                                                               ai1  ... a xin n a xj j    bi

j1               

i 1,k,

(2)

xj 0 jJ,

где J 1,2,...,n – множество индексов.

 

(3)

Функция F называется целевой функцией или показателем эффективности. Совокупность значений неизвестных управляющих переменных X x1,...,xnT , которые удовлетворяют условиям (2)–(3), называется допустимым решением

Определение 1. Допустимое решение X* x1*,...,xn*T называется оптимальным, если он максимизирует (минимизирует) значения показателя эффективности. То есть:

F X F X*   X G.

Если в задаче (1) – (3) все ограничения (2) имеют вид неравенств и все переменные неотрицательные, то задача линейного программирования будет называться симметрической задачей линейного программирования [4].

Если в задаче (1) – (3) все ограничения (2) имеют вид уравнений и все

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

Утверждение 1. Любая задача линейного программирования равносильна некоторой канонической задаче.

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

                                                                                                        ai1  ... a xin n  yi bi , i 1,k

                                               a xi1 1  ... a xin n  bi                                                         (4)

yi 0,

или

                                                                                                      ai1  ... a xin n  yi bii 1,k

                                              a xi1 1  ... a xin n  b                                                      (5)

yi 0.

В уравнении (4) 𝑦𝑖 – остаток ресурса, в уравнении (5) 𝑦𝑖 – перевыполнение минимального требования.

В случае, когда за физическим содержанием задачи (1) – (3) некоторая

переменная xs может иметь любой знак, то необходимо ввести в исследование две дополнительные переменные и эту переменную заменить их разностью

                                                                     xs    R    x us                             s s,        us 0, s 0.

Что требовалось доказать.

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

a xi1 1  ... a x bin n  i ai1  ... a x bin n i, ai1  ... a x bin n i.

 

 

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

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

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

Пример 2. Найти максимум функции F x1 3x2 при ограничениях


x x1  1,

x x1  5,



2x x1  2 8, x1 2x2 8,

(6)

x1 0, x2 0.

Решение. На рисунке 1 изображена область допустимых решений системы неравенств (6) (номер прямой соответствует порядковому номеру соответственной неравенству системы ограничений). Это шестиугольник ABCDEG с угловыми точками: A0,1, B0,4, C2,3, D3,2, E4,0,

G1,0, координаты которых находим, решая по очереди системы из соответствующих двух уравнений прямых.

Каждое неравенство описывает полуплоскость. Полуплоскость является выпуклым множеством. Решение системы неравенств – это пересечение полуплоскостей. Следовательно, множество допустимых планов всегда является выпуклым. 

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

                                                                  F x1 3x2 const a.                                                (7)

Равенство (7) задает уравнение прямой на плоскости с градиентом n1,3

Определение 2. Градиентом функции F X  F x1,...,xn называется вектор, проекциями которого на координатные оси служат соответствующие частные производные [2].

Изменяя значение параметра a, получим семейство параллельных прямых, которые называются линиями уровня, то есть линиями равных значений функции. На рисунке 1 прямая V соответствует значению a 0. Максимальное значение функции F будет принимать в точке B0,4, то есть в точке из области допустимых решений системы, наиболее отдаленной от начала координат в направлении вектора n. Таким образом,

                                                                                        Fmax  1 0 3 4 12         

при оптимальном плане x1 0, x2 4.

Пример 3. Найти максимум функции F 3x1 4x2 при ограничениях 

                                                                                                 x1   x2,

x1 2x2 2,

                                                                                                                 

2x

1 3x2 6,

x1 0, x2 0.

Решение. На рисунке 2. изображена неограниченная многогранная область ABCD решений заданной системы ограничений, где A0,2, B0,1, C2,0, D3,0; и линию уровня 3x1 4x2 25 (прямая (IV)) с вектором n4,3, который указывает направление движения линии уровня для нахождения Fmax

 

Рисунок 2

Очевидно, что при заданной системе ограничений функция F может неограниченно возрастать при увеличении переменных x1, x2 , то есть

Fmax .

Пример 4. Найти максимум функции F 2x1 x2 при ограничениях 

                                                                                             x1  x2 1,

2x1 3x2 6,

                                                                                                                 

5x1 4x2 20, x1 0, x2 0.

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

 

Рисунок 3

Пример 5. Найти максимум функции F 3x1 3x2  при ограничениях 

                                                                                             x1  x2 8,

                                                                                           2x1  x2 1,

                                                                                                                 

                                                                                             x1  x2 2,

x1 0, x2 0.

Решение. Геометрическое решение задачи показано на рисунке 4, из которого следует, что линия уровня с максимальным уровнем совпадает с граничной линией AB многоугольника ABCD, то есть с линией x1 x2 8. Следовательно, на всём отрезке AB линейная функция F 3x1 3x2 принимает одно и то же максимальное значение, равное 3(x1 x2)   3 8 24.

Это означает, что задача имеет бесконечно много оптимальных решений.

Итак, Fmax 24 при бесконечном множестве оптимальных решений x c1 , x2 8c, где 3 c 6.

 

Рисунок 4

 

Из приведённых решений примеров 2 – 5 можно сделать обобщающие выводы о множестве допустимых решений и месте расположения оптимального решения в этом множестве:

                 ü множество         допустимых        решений        задачи        линейного

программирования является выпуклым многогранником; ü оптимальное решение достигается в угловой точке; ü оптимальное решение может быть неединственно.

3.   Об угловых точках канонической задачи

Определение 3. Точка выпуклого множества называется угловой, если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству [𝟐].

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

Пример 6. Найти угловые точки системы ограничений

                                                                                       x  2y  3z  6,

x 0,

                                                                                                         

y 0, z 0.

Решение: Первое уравнение данной системы является уравнением плоскости, а три неравенства описывают первый октант. Пересечение плоскости с октантом даёт треугольник ABC (смотри рисунок 5) с вершинами на координатных плоскостях, следовательно, часть координат должна равняться нулю. В данном случае угловыми точками множества являются точки A0,0,2, B6,0,0 и C0,3,0.

 

Рисунок 5

 

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

 

4.   Метод последовательного улучшения плана

Метод последовательного улучшения плана состоит из следующих шагов: 

1)                 нахождение начального допустимого решения системы ограничений; 

2)                 проверка оптимальности решения; 

3)                 переход к новому допустимому плану с лучшим значением целевой функции. 

Последовательность выполнения шагов метода последовательного улучшения плана приведена на следующей схеме (рисунок 6).

 

Рисунок 6

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

 

Рисунок 7

 

5.   Симплекс-метод

Определение 4: Симплекс-методэто метод последовательного улучшения плана для задачи линейного программирования в канонической форме записи.

Покажем, как работает алгоритм симплекс-метода на примере задачи F  3x1 2x2 max при ограничениях

                                                                                             x1  x2 10,

2x1 3x2 15,

                                                                                                                 

x1 4x2 17, x1 0,x2 0.

Шаг 1. Приводим задачу к каноническому виду.

                                                                             Z   F        3x1                                                      2x2               min .                                                        (8)

                                                                  x1   x2     y1       10,

                                                               2x1 3x2  y2 15,

                                                                                                                                               (9)

1 4x2  y3            17, x

                                                                x x y y y1 2,        , 1, 2, 3 0.

Приведение симметричной задачи к каноническому виду позволяет найти начальное допустимое решение X0 x x y y y1, 2, 1, 2, 30,0,10,15,17, которое является угловой точкой множества допустимых планов канонической задачи.

Полученную каноническую задачу записывают в матричной форме записи, которая называется симплекс-таблицей (смотри таблицу 2), где первая строка – это строка целевой функции (8), а вторая-четвёртая строки – это расширенная матрица системы уравнений (9). Неравенства из системы (9) контролируются за счёт неотрицательности правой части системы уравнений.

Таблица 2

–3

–2

0

0

0

 

1

1

1

0

0

10

2

3

0

1

0

15

1

4

0

0

1

17

 

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

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

Шаг 2. Критерий оптимальности

Критерий оптимальности при отыскании минимума линейной функции состоит в отсутствии отрицательных элементов в строке целевой функции. 

Решение X0 0,0,10,15,17 не является оптимальным, поскольку в строке целевой функции есть отрицательные элементы.

Шаг 3. Переход к новому угловому решению.

А) Выбор ведущего столбца. Цель всех переходов к новому решению – избавиться от отрицательных элементов в строке целевой функции. Поэтому в качестве ведущего столбца выбираем любой столбец с отрицательным элементом в строке целевой функции, например, первый (таблица 3). Таблица 3

–3

–2

0

0

0

 

1

1

1

0

0

10

2

3

0

1

0

15

1

4

0

0

1

17

 

Б) Выбор ведущей строки. Для каждой строки, которая в ведущем столбце имеет положительный элемент, вычисляется оценочное отношение – отношение правой части к элементу ведущего столбца.

                                                                                        1   10;

2   7,5;

                                                                                        3   17.

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

В нашем случае минимальное значение оценочного отношения даёт 2 , значит, третья строка будет ведущей (таблица 4).

Таблица 4

–3

–2

0

0

0

 

1

1

1

0

0

10

2

3

0

1

0

15

1

4

0

0

1

17

 

В) Пересчёт симплекс-таблицы. Пересчёт симплекс-таблицы выполняется при помощи элементарных преобразований, как в методе Гаусса при решении систем линейных алгебраических уравнений. Результат пересчёта приведён в таблице 5.

Таблица 5

0

5

0

3

0

 

0

1

1

–1

0

5

2

3

0

1

0

15

0

5

0

–1

1

19

2I  3 III

2I  1III

 

2I  1III

 

Находим соответствующее угловое решение – X1 0,3,5,0,19. Это решение оптимально, так как в строке целевой функции нет отрицательных элементов. Вычисляем значение целевой функции на найденном решении F X1Fmax 3 0  2 3  6,

Что завершает решение примера.

Рассмотрим приведённую симплекс-таблицу (таблица 6), где допустимое оптимальное решение X0 x x1, 2,x ,3 y y1, 20,0,0,10,15

Таблица 6

3

2

0

0

0

 

1

1

1

0

7

10

2

3

0

1

8

15

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

Таблица 7

21

14

0

0

0

 

1

1

1

0

7

10

6

13

–8

1

0

25

Таким образом, мы получаем новое допустимое оптимальное решение X1 1,1,0,0,25.

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

Рассмотрим симплекс-таблицу (таблица 8), где все элементы свободного столбца являются неположительными. 

Таблица 8

–3

2

0

0

9

 

–1

1

1

0

7

10

–2

3

0

1

8

15

 

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

Вывод: Если в целевой функции присутствует положительный элемент, а все элементы соответствующего свободного столбца неположительные, то она неограниченна: Fmax .

Заключение

В результате проведенного исследования нами были получены следующие результаты:

1)                 рассмотрен теоретический материал по основам линейного программирования и симплекс-методу, особое внимание уделено геометрической интерпретации симплекс-метода;

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

3)                 Расширенный алгоритм симплекс-метода рассмотрен на примере задачи. 

 

Список литературы

1)            Банди Б. Основы линейного программирования: Пер. с англ. / Б. Банди. – М.: Радио и связь, 1989. – 176 с.

2)            Кремер Н. Ш.       Исследование      операций    в        экономике: Учеб. пособие для вузов / Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман. – М.: ЮНИТИ, 2005. – 407 с.

3)            Кузнецов А. В.     Высшая      математика.         Математическое программирование. / А. В. Кузнецов, Н. И. Холод, В.А. Сакович. – Мн.: Выш. школа, 1994. – 289 с.

4)            Палий И. А. Линейное программирование. Учебное пособие / И. А. Палий. – М.: Эксмо, 2008. – 256 с.

5)            Рыбенко И. А. Решение задач линейного программирования симплекс-метод. Методические рекомендации к выполнению лабораторных работ по дисциплине «Оптимизация в технике и технологиях» / И. А. Рыбенко, В. Н. Буинцев. – Новокузнецк: Сибирский государственный индустриальный университет, 2014. – 22 с.

6)            Таха Хемди А. Введение в исследование операций. Пер. с англ. /

Хемди А. Таха. – М.: Издательский дом «Вильямс», 2005. – 912 с.

 

Просмотрено: 0%
Просмотрено: 0%
Скачать материал
Скачать материал
Скачать тест к материалу
Скачать материал
Скачать тест к материалу

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

5 938 061 материал в базе

Скачать материал
Скачать тест к материалу

Другие материалы

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

  • Скачать материал
    Скачать тест к материалу
    • 22.09.2022 84
    • PDF 1.1 мбайт
    • Оцените материал:
  • Настоящий материал опубликован пользователем Горлова Дарья Дмитриевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

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

    Удалить материал
  • Автор материала

    Горлова Дарья Дмитриевна
    Горлова Дарья Дмитриевна
    • На сайте: 1 год и 9 месяцев
    • Подписчики: 0
    • Всего просмотров: 343
    • Всего материалов: 7

Ваша скидка на курсы

40%
Скидка для нового слушателя. Войдите на сайт, чтобы применить скидку к любому курсу
Курсы со скидкой