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

 

Содержание

 

 

 

Введение………………………………………………………………………….. 4

1. Теоретическая часть…………………………………………………………. 6
1. Двойственность в линейном программировании………………………….. 6
2. Несимметричные двойственные задачи……………………………………. 8
3. Двойственный симплексный метод………………………………………… 11
2. Практическая часть………………………………………………………….. 13
1. Задача №1…………………………………………………………………….. 13
2. Задача №2……………………………………………………………………. 17
3. Задача №3…………………………………………………………………….. 23
4. Задача №4…………………………………………………………………….. 23

Заключение……………………………………………………………………….. 26

Литература………………………………………………………………………… 27

 

 

Введение

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

Позвольте задать несколько философский вопрос: какое место в современном  мире занимают математические методы?

Математика  стала "языком" и методом соответствующей  предметной науки. И этому не приходится удивляться, поскольку "область применения математического метода не ограничена: все виды движения материи могут  изучаться математически" (А.Н. Колмогоров). И то, что общество материально  поддерживает развитие такой абстрактной  науки как математика, свидетельствует  о понимании им роли математических методов в прогрессе наук и  общества в целом.

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Теоретическая часть

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

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

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

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

В качестве примера рассмотрим задачу использования ресурсов. Предприятие  имеет т видов ресурсов в количестве b_i (i = 1, 2, ., m) единиц, из которых производится n видов продукций. Для производства 1 ед. i-й продукции расходуется a_ij ед. t-гo ресурса, а ее стоимость составляет Cj ед. Составить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении.

Обозначим через x_j(j =1,2, ., n) количество ед. j-й продукций, Тогда исходную задачу сформулируем так: найти вектор Х =(x₁, x₂, …, x_n), который удовлетворяет ограничениям

 а₁₁x₁ + a₁₂х₂ + … + a_1nх_n ≥ b₁,

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n ≥ b₂,

                       …

a_m1x₁+ a_m2x₂ + … + a_mnx_n ≥ b_m,

и доставляет максимальное значение линейной функции 

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

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

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

Стоимость всех имеющихся ресурсов выразится  величиной

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

Найти вектор Y =(y₁, y₂, …, y_n), который удовлетворяет ограничениям

a₁₁y₁ + a₁₂y₂ + … + a_m1y_m ≤ C₁,

a₁₂y₁ + a₂₂y₂ + … + a_m2y_m ≤ C₂,          при    y_i≥ 0 (i =1,2, ., m) ,

                          …

a_1ny₁+ a_2ny₂ + … + a_mny_m ≤ C_m,

и доставляет минимальное значение линейной функции 

f = b₁y₁ + b₂y₂ + … + b_my_m.

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

И с х о д н а я з а д а ч а. Сколько и какой продукции x_j (j =1,2, ., n) необходимо произвести, чтобы при заданных стоимостях C_j (j =1,2, ., n) единицы продукции и размерах имеющихся ресурсов b_i (i =1,2, ., n) максимизировать выпуск продукции в стоимостном выражении.

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

Переменные у_i называются оценками или учетными, неявными ценами. Многие задачи линейного программирования первоначально ставятся в виде исходных или двойственных задач, поэтому имеет смысл говорить о паре двойственных задач линейного программирования.

 

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

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

И с х о д н а я з а д а ч а. Найти матрицу-столбец X = (x₁, x₂, …, x_n), которая удовлетворяет ограничениям

(1.1) AX = A₀, Х > 0

и минимизирует линейную функцию Z = СХ.

Д в о й с т в е н н а я з а д а ч а. Найти матрицу-строку Y = (y₁, y₂, …, y_m), которая удовлетворяет ограничениям

(1.2) YA ≤ С

и максимизирует линейную функцию  f = YA₀

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

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

min Z = max f.

Если линейная функция  одной из задач не ограничена, то другая не имеет решения.

Д о к  а з а т е л ь с т в о. Предположим, что исходная задача обладает оптимальным планом, который получен симплексным методом. Не нарушая общности, можно считать, что окончательный базис состоит из т первых векторов A₁, A₂, ., A_m. Тогда последняя симплексная таблица имеет вид табл. 1.1.

 

 

 

 

 

 

 

 

Таблица 1

i	Базис	С базиса	A0	C1	C2	…	Cm	Cm+1	…	cn
				A1	A2	…	Am	Am+1	…	An
1 2 . . . m	A1 A2 . . . Am	C1 C2 . . . Cm	x1 x2 . . . xm	1 0 . . . 0	0 1 . . . 0	. . . . . .	0 0 . . . 1	x1, m+1 x2, m+1 . . . xm, m+1	… … . . . …	x1n x2n . . . xmn
m+1	Zi - Cj		Z0	Z1 – C1	Z2 – C2	.	Zm – Cm	Zm+1 – Cm+1	…	Zn – Cn

Пусть D — матрица, составленная из компонент векторов окончательного базиса A₁, A₂, ., A_m; тогда табл. 1.1 состоит из коэффициентов разложения векторов A₁, A₂, ., A_n исходной системы по векторам базиса, т. е. каждому вектору A_j в этой таблице соответствует такой вектор X_j что

(1.3) A_j = DX_j(j= 1,2, , , n).

Для оптимального плана  получаем

(1.4) A₀ = DX*,     где X* = (x*₁, x*₂, …, x*_m).

Обозначим через  матрицу, составленную из коэффициентов разложения векторов А_j (j = 1, 2, ., n), записанных в табл. 1.1. Тогда, учитывая соотношения (1.3) и (1.4), получаем:

(1.5) A = D

, D-1A = ,

(1.6) A₀=DX*; D-1A₀ = X*,

(1.7) min Z= C*X*,

(1.8)

= C* -C ≤ 0,

где С* = (C*₁, C*₂, …, C*_m), С = (C₁, C₂, …, C_m, C_m+1, …, C_n), a = (C*X₁ – C₁; С*Х₂ - С₂, ., C*X_n – C_n) = (Z₁ – С₁; Z₂ - C₂; ., Z_n - C_n) — вектор, компоненты которого неположительны, так как они совпадают с Z_j — C_j ≤ 0, соответствующими

 

оптимальному плану.

Оптимальный план исходной задачи имеет вид X* = D-1 А₀, поэтому оптимальный план двойственной задачи ищем в виде

(1.9) Y* = C*D-1.

Покажем, что Y* действительно план двойственной задачи. Для этого ограничения (1.2) запишем в виде неравенства YA - С ≤ 0, в левую часть которого подставим Y*. Тогда на основании (1.9), (1.5) и (1.8) получим

Y* А – С = С* D-1А – С = С*

- С ≤ 0,

откуда  находим Y*A ≤ С.

Так как Y* удовлетворяет ограничениям (1.2), то это и есть план двойственной задачи. При этом плане значение линейной функции двойственной задачи f (Y*) = Y*A₀. Учитывая соотношения (1.9), (1.6) и (1.7), имеем

(1.10) f (Y*) = Y*A₀ = C*D-1 A₀ = C*X* = min Z(X).

 

Таким образом, значение линейной функции  двойственной задачи от Y* численно равно минимальному значению линейной функции исходной задачи.

Докажем теперь, что Y* является оптимальным планом. Умножим (1.1) на любой план Y двойственной задачи, а (1.2) — на любой план X исходной задачи: YAX=YA0=f (Y), YAX ≤ СХ = Z (X), отсюда следует, что для любых планов Х и Y выполняется неравенство

(1.11) f (Y) ≤ Z (X).

 

Этим же соотношением связаны и экстремальные значения max f (Y) ≤ min Z (Х). Из последнего неравенства заключаем, что максимальное значение линейной функции достигается только в случае, если max f (Y) = min Z (X), но это значение [см. (1.10)] f (Y) достигает при плане Y*, следовательно, план Y* — оптимальный план двойственной задачи.

Аналогично можно доказать, что если двойственная задача имеет  решение, то исходная также обладает решением и имеет место соотношение max f (Y) = min Z (X).

Для доказательства второй части теоремы допустим, что линейная функция исходной задачи не ограничена снизу. Тогда из (1.11) следует, что f (Y)≤Y. Это выражение лишено смысла, следовательно, двойственная задача не имеет решений.

Аналогично предположим, что линейная функция двойственной задачи не ограничена сверху. Тогда из (1.11) получаем, что Z (X) ³ +Y. Это выражение также лишено смысла, поэтому исходная задача не имеет решений.

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

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

Пусть необходимо решить исходную задачу линейного программирования, поставленную в общем виде: минимизировать функцию Z =СХ при АХ = A₀, Х ≥ 0. Тогда в двойственной задаче необходимо максимизировать функцию f = YA₀ при YA ≤ С. Допустим, что выбран такой базис D = (A₁, А₂, ., А_i, ., А_m), при котором хотя бы одна из компонент вектора Х = D-1 A₀ = (x₁, x₂, ., x_i, ., x_m) отрицательная (например, x_i < 0), но для всех векторов Aj выполняется соотношение Z_j – C_j ≤ 0 (i = 1,2, ., n). Тогда на основании теоремы двойственности Y = С_баз D-1 - план двойственной задачи. Этот план не оптимальный, так как, с одной стороны, при выбранном базисе X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны, оценки оптимального плана двойственной задачи должны быть неотрицательными.

Таким образом, вектор А_i, соответствующий компоненте x_i < 0, следует исключить из базиса исходной задачи, а вектор, соответствующий отрицательной оценке,— включить в базис двойственной задачи.

Для выбора вектора, включаемого  в базис исходной задачи, просматриваем i-ю строку: если в ней не содержатся x_ij < 0, то линейная функция двойственной задачи не ограничена на многограннике решений, а исходная задача не имеет решений. Если же некоторые x_ij < 0, то для столбцов, содержащих эти отрицательные значения, вычисляем q_0j= min (x_i/x_ij) ≥ 0 и определяем вектор, соответствующий max q_0j(Z_j — C_j) при решении исходной задачи на минимум и min q_0j(Z_j — C_j) при решении исходной задачи на максимум. Этот вектор и включаем в базис исходной задачи. Вектор, который необходимо исключить из базиса исходной задачи, определяется направляющей строкой.

Если q_0j= min (x_i/x_ij) = 0, т. е. x_i = 0, то x_ij берется за разрешающий элемент только в том случае, если x_ij > 0. Такой выбор разрешающего элемента на данном этапе не приводит к увеличению количества отрицательных компонент вектора X. Процесс продолжаем до получения Х ≥ 0; при этом находим оптимальный план двойственной задачи, следовательно, и оптимальный план исходной задачи.

В процессе вычислений по алгоритму  двойственного симплексного метода условие Z_j – C_j ≤ 0 можно не учитывать до исключения всех х_i < 0, затем оптимальный план находится обычным симплексным методом. Это удобно использовать, если все х_i < 0; тогда для перехода к плану исходной, задачи за одну итерацию необходимо q_0j определить не по минимуму, а по максимуму отношений, т. е. q_0j= max (x_i/x_ij) > 0.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 Практическая часть

2.1 Задача №1

Транспортная задача

          Транспортная фирма обслуживает 4 поставщиков однородного груза и 4 потребителей этого груза. В течение дня из каждого пункта поставки фирма должна вывезти соответственно A1 = 300, A2 = 250, AЗ = 280, A4 = 150 тонн груза, а в каждый пункт потребления доставить соответственно B1= 80, B2 = 220, BЗ = 155, B4 =495 тонн. Себестоимость перевески 1 тонны груза от -го поставщика -му потребителю составляет тыс. руб.

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

 

 

1. Решение методом северо-западного угла

Таблица 2

 

Z=25*80+17*220+17*155+23*95+19*280+20*120=18280

 

Ответ: при данной схеме перевозки, затраты составят 18280 руб.

 

 

 

 

 

 

2. Решение методом минимального элемента

Таблица 3

 

Рис.1

 

Z=14*5+20*295+19*20+23*200+18*60+14*220+13*150=17060

 

 

Ответ: при данной схеме перевозки, затраты составят 17060 руб.

 

 

 

 

 

 

 

2.1.3 Решение в Microsoft Office Excel

Заносим исходные данные:

Рис. 2

Вводим формулы суммы по поставщикам и потребителям в расчетную таблицу:

Рис. 3

 

Рис. 4

 

Рис. 5

Зададим функцию поиск решения.

Для этого  устанавливаем целевую ячейку равной минимальному значению, выбираем изменяемые ячейки и устанавливаем ограничения:

Рис. 6

В параметрах поиска функции ставим галочки «Линейная  модель» и «Неотрицательные значения»

Рис. 7

Получаем  ответ:

Рис. 8

Ответ: при решении с помощью Excel затраты на отправление груза составят Z=17325.

 

 

Вывод по задаче.

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

 

2.2  Задача №2

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

Организации, занимающейся перевозкой и продажей продукции, необходимо перевезти партию товара. При этом можно арендовать для перевозки по железной дороге 5-ти и 7-тонные контейнеры. Пятитонных контейнеров имеется в наличии  не более a штук, а семитонных - не более b штук. На перевозку всей продукции по смете выделено не более N тысяч рублей, причем цена за аренду 5-тонного контейнера - 2 тысячи рублей, а 7-тонного - 3 тыс. рублей. Определить, сколько и каких контейнеров следует арендовать, при условии, что общий объем грузоперевозок должен быть максимальным. 
Решение задачи оформить поэтапно: - построить математическую модель задачи; - решить задачу графически, определив область решения системы неравенств; - решить задачу симплекс-методом.

 

a=34, b=40, N=130

 

 

 

Математическая модель:

Пусть   x₁ – число задействованных 5-тонных контейнеров;

x₂ – число задействованных 7-тонных контейнеров;

Тогда общий объём грузоперевозок равен: Z=5* x₁+7* x₂→max

Имеем следующие ограничения: x₁≤34, x₂≤40

Ограничения по деньгам: 2000* x₁+3000* x₂≤70000

Таким образом, получим математическую модель задачи:

Z=5* x₁+7* x₂→max

2* x₁+3* x₂≤130

x₁≤34, x₂≤40

x₁≥0, x₂≥0

 

 

 

 

 

 

 

 

2.2.1 Решение графическим  методом

2* x₁+3* x₂≤130; (1)

x₁≤34; (2)

x₂≤40; (3)

x₁≥0; (4)

x₂≥0; (5)

Построим на графике прямые (1)…(5)

Рис. 9

A -> max

Ответ: a=34, b=62/3, Z=944,3

 

2.2.2 Решение симплекс-методом

Таблица 4

 

Шаг 1
Базис	БП	x 1	x 2	x 3	x 4	x 5
x3	130	2	3	1	0	0
x4	34	1	0	0	1	0
x5	40	0	1	0	0	1
ИС	0	-5	-7	0	0	0

 

 

 

 

 

 

 

 

 

Таблица 5

 

Шаг 2
Базис	БП	x 1	x 2	x 3	x 4	x 5
x3	10	2	0	1	0	-3
x4	34	1	0	0	1	0
x2	40	0	1	0	0	1
ИС	280	-5	0	0	0	7

 

 

 

Таблица 6

 

Шаг 3
Базис	БП	x 1	x 2	x 3	x 4	x 5
x1	5	1	0	1/2	0	-3/2
x4	29	0	0	-1/2	1	3/2
x2	40	0	1	0	0	1
ИС	305	0	0	5/2	0	-1/2

 

 

 

 

 

 

 

 

Таблица 7

 

Шаг 4
Базис	БП	x 1	x 2	x 3	x 4	x 5
x1	34	1	0	0	1	0
x5	58/3	0	0	-1/3	2/3	1
x2	62/3	0	1	1/3	-2/3	0
ИС	944/3	0	0	7/3	1/3	0

 

 

 

 

 

 

 

 

 

Ответ: x1=a=34, x2=b=62/3, Z=944,3

 

 

2.2.3 Решение методом линейного программирования

Зададимся формулами:

Рис. 10

Рис. 11

Рис. 12

Рис. 13

Зададим функцию поиск решения.

Для этого  устанавливаем целевую ячейку равной максимальному значению, выбираем изменяемые ячейки и устанавливаем ограничения:

Рис. 14

Получаем  ответ:

Рис. 15

Ответ: a=34, b=20,67, Z=314,67

 

 

 

 

Вывод по задаче:

необходимо 5-тонных контейнеров 34 штуки, а 7-тонных контейнеров 20 штук. При этом перевезут 314,67 тонн на сумму менее 130 тысяч рублей. Исходный результат получили во всех трех задачах.

 

 

 

 

 

 

3. Задача №3

Определение кратчайшего пути

На рисунке 16 показана коммуникационная сеть между двумя примерно передающими станциями 1 и 7. Возле каждой дуги указаны вероятности передачи сообщений без потерь по этим дугам.

Необходимо  найти маршрут от станции 1 к станции 7 с максимальной вероятностью успешной передачи сообщений.

Рис. 16

1. Расчёт маршрута (при нормальных условиях)

x=12*0.01=0.12

y=√12=0.34641

 

Рис. 17

 

1-2 = | ln(0,8)| = 0,223

1-3 = | ln(0.036)| = 3,324

1-4 = | ln(0,65)| = 0,431

2-4 = | ln(0,102)| = 2,283

2-5 = | ln(0,846)| = 0.167

3-4 = | ln(0,85)| = 0,163

 

 

3-6 = | ln(0,95)| = 0,051

4-5 = | ln(0,7)| = 0,357

4-6 = | ln(0,208)| = 1,57

5-6 = | ln(0,5)| = 0,693

5-7 = | ln(0,8)| = 0,223

6-7 = | ln(0,9)| = 0,105           

Рис. 18

P=1-2-5-7=0.8*0.846*0.8=0.54144

Ответ: вероятность P = 0.54144

 

2. Пересчёт маршрута при отказе узла №2

Рис. 19

Рис. 20

P=1-4-6-7=0.65*0.208*0.9=0.12168

Вывод по задаче:

Максимальная вероятность успешной передачи сообщения равна 0.54144, и это сообщение пройдёт через станции 1-2-5-7.

При отказе 5 станции максимальная вероятность успешной передачи сообщения  равна 0.12168, и это сообщение пройдёт через станции 1-4-6-7.

 

Задача №4 Метод критического пути

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

Разработайте сеть этих работ.

Таблица 8

	Процесс	Предшествующий процесс	Длительность (дни)
A	Очистка строительного участка	-	1
B	Завоз оборудования	-	2
C	Земельные работы	A	2
D	Заливка фундамента	C	2
E	Наружные технические работы	B,C	7
F	Возведение каркаса дома	D	10
G	Прокладка электропроводки	F	3
H	Создание покрытий	G	1
I	Создание каркаса крыши	F	1
J	Внутренние сантехнические работы	E,H	6
K	Покрытие крыши	I	1
L	Наружные изоляционные работы	F,J	1
M	Вставки окон и наружных дверей	F	2
N	Обкладка дома кирпичом	L,M	4
O	Штукатурка стен и потолков	G,J	2
P	Облицовка стен и потолков	O	2
Q	Изоляция крыши	I,P	1
R	Окончание внутренних отделочных работ	P	5
S	Окончание наружных отделочных работ	I,N	7
T	Ландшафт работы	S	3