Реферат: Математические методы в решении экономических задач

--PAGE_BREAK--


Решение:

Предположим, что будет изготовлено Х₁ единиц изделий вида А₁ и Х₂ единиц — вида А₂. Поскольку производство продукции ограничено имеющимися в распоряжении предприятия сырьем каждого вида и количество изготовляемых изделий не может быть отрицательным, должны выполняться неравенства:
<img width=«142» height=«73» src=«ref-1_1246651621-1473.coolpic» v:shapes="_x0000_i1042">

<img width=«113» height=«33» src=«ref-1_1246653094-525.coolpic» v:shapes="_x0000_i1043">




Общая прибыль от реализации Х₁ изделий А₁ и Х₂ изделий вида А₂ составит
F = 30Х₁ +49Х₂<img width=«61» height=«33» src=«ref-1_1246653619-346.coolpic» v:shapes="_x0000_i1044">.
Таким образом, мы приходим к следующей математической задаче: среди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция F принимает максимальное значение.

Найдем решение сформулированной задачи, используя ее геометрическую интерпретацию. Сначала определим многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств и найдем соответствующие прямые:
<img width=«142» height=«73» src=«ref-1_1246653965-1432.coolpic» v:shapes="_x0000_i1045">

<img width=«113» height=«33» src=«ref-1_1246655397-493.coolpic» v:shapes="_x0000_i1046">
Эти прямые изображены на рис №1. Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой — нет. Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты данному неравенству. Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой принадлежит эта точка, в противном случае — другая полуплоскость.

Найдем, например, полуплоскость, определяемую неравенствами.




<img width=«620» height=«482» src=«ref-1_1246655890-16364.coolpic» v:shapes=«Рисунок_x0020_323»>
Построим область допустимых решений:

для прямой<img width=«139» height=«33» src=«ref-1_1246672254-590.coolpic» v:shapes="_x0000_i1048">
<img width=«184» height=«82» src=«ref-1_1246672844-1519.coolpic» v:shapes=«Рисунок_x0020_321»>
С(0;0) => 5·0+2·0=0, а 0≤750, значит прямая стремится к нулю (рис.1)

для прямой <img width=«135» height=«33» src=«ref-1_1246674363-616.coolpic» v:shapes="_x0000_i1050">
<img width=«216» height=«68» src=«ref-1_1246674979-1812.coolpic» v:shapes=«Рисунок_x0020_318»>




В(0;0) => 4·0+5·0=0, а 0≤807, значит прямая стремится к нулю (рис.1)

для прямой <img width=«124» height=«33» src=«ref-1_1246676791-570.coolpic» v:shapes="_x0000_i1052">
<img width=«199» height=«60» src=«ref-1_1246677361-1718.coolpic» v:shapes=«Рисунок_x0020_322»>
А(0;0) => 1·0+7·0=0, а 0≤840, значит прямая стремится к нулю (рис.1). Это и показано стрелками.

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

Как видно из рис №1, многоугольником решений является пятиугольник OABCD. Координаты любой точки, принадлежащей этому пятиугольнику, удовлетворяют данной системе неравенств и условию неотрицательности переменных. Поэтому сформулированная задача будет решена, если мы сможем найти точку, принадлежащую пятиугольнику OABCD, в которой функция F принимает максимальное значение.

Чтобы найти указанную точку, построим вектор с =(30; 49) и прямую 30Х1 + 49Х2 = h, где h — некоторая постоянная такая, что прямая 30Х1 + 49Х2 = h имеет общие точки с многоугольником решений. Положим, например, h = 510 и построим прямую 30Х1 + 49Х2 = 510 (рис. №1).

Если теперь взять какую-нибудь точку, принадлежащую построенной прямой и многоугольнику решений, то ее координаты определяют такой план производства изделий А1 и А2, при котором прибыль от их реализации равна 510 руб. Далее, полагая h равным некоторому числу, большему чем 510, мы будем получать различные параллельные прямые. Если они имеют общие точки с многоугольником решений, то эти точки определяют планы производства изделий А1 и А2, при которых прибыль от их реализации превзойдет 510 руб.

Перемещая построенную прямую 30Х1 + 49Х2 = 510 в направлении вектора с, видим, что последней общей точкой ее с многоугольником решений задачи служит точка В. Координаты этой точки и определяют план выпуска изделий А1 и А2, при котором прибыль от их реализации является максимальной.

Найдем координаты точки В как точки пересечения прямых <img width=«135» height=«33» src=«ref-1_1246674363-616.coolpic» v:shapes="_x0000_i1054"> и <img width=«124» height=«33» src=«ref-1_1246676791-570.coolpic» v:shapes="_x0000_i1055">. Следовательно, ее координаты удовлетворяют уравнениям этих прямых
<img width=«142» height=«51» src=«ref-1_1246680265-1037.coolpic» v:shapes="_x0000_i1056">
Решим эту систему уравнений:

Х1 = 840 – 7Х2, подставим полученное в первое уравнение <img width=«212» height=«36» src=«ref-1_1246681302-857.coolpic» v:shapes="_x0000_i1057"> => 3360 – 28Х2 + 5Х2 = 807 => 23Х2 = 2553 =>

Х2 = 111, из этого решения следует, что Х1 = 840 – 7·111 = 63 => Х1 = 63

Следовательно, если предприятие изготовит 63 изделий вида А1 и 111 изделий вида А2, то оно получит максимальную прибыль, равную Fmax = 30·63 + 49·111= 7329 руб.
Решение задачи аналитическим симплекс-методом
Симплексный метод — это метод целенаправленного перебора опорных решений задачи линейного программирования. Он позволяет за конечное число шагов расчета либо найти оптимальное решение, либо установить, что оптимального решения не существует.

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

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

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

Дадим математическую формулировку задачи. Пусть Х1 и Х2 — количество изделий А1 и А2, запланированных к производству. Так как количество сырья по каждому виду ограничено, то должны выполняться следующие неравенства:
<img width=«142» height=«73» src=«ref-1_1246651621-1473.coolpic» v:shapes="_x0000_i1058">

<img width=«113» height=«33» src=«ref-1_1246653094-525.coolpic» v:shapes="_x0000_i1059">
Эта система неравенств и является системой ограничений данной задачи. Целевая функция (линейная форма), выражающая прибыль предприятия, имеет вид
F = 30Х₁ +49Х₂<img width=«61» height=«33» src=«ref-1_1246653619-346.coolpic» v:shapes="_x0000_i1060">.
Итак, задача сводится к нахождению максимума функции F = 30Х₁ +49Х₂ при ограничениях:




<img width=«142» height=«73» src=«ref-1_1246651621-1473.coolpic» v:shapes="_x0000_i1061">

<img width=«113» height=«33» src=«ref-1_1246653094-525.coolpic» v:shapes="_x0000_i1062">
Для сведения системы ограничений-неравенств к системе уравнений прибавим к левой части каждого неравенства добавочные неотрицательные переменные Х3, Х4, Х5. В условиях данной задачи они имеют конкретное экономическое содержание, а именно выражают объем остатков сырья каждого вида после выполнения плана по выпуску продукции. После введения добавочных переменных получим систему уравнений:

<img width=«28» height=«98» src=«ref-1_1246686501-202.coolpic» v:shapes="_x0000_s1026">


5Х1+2Х2+Х3 = 750

4Х1+5 Х2+ Х4 = 807

Х1+7Х2+Х5 = 840

Хi≥0, i=1….5
Нужно найти такое допустимое базисное решение этой системы ограничений, которое бы максимизировало линейную форму F = 30Х₁ +49Х₂.

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

Для решения задачи симплексным методом прежде всего нужно найти любое базисное решение. В данном случае это легко сделать. Для этого достаточно взять в качестве базисных добавочные переменные Х3, Х4, Х5. Так как коэффициенты при этих переменных образуют единичную матрицу, то отпадает необходимость вычислять определитель. Считая свободными переменные Х1 и Х2 равными нулю, получим базисное решение (0; 0; 750; 807; 840), которое к тому же оказалось допустимым. Переходим к поискам оптимального решения.

I ш а г. Базисные переменные: Х3, Х4, Х5; свободные переменные: Х1 и Х2. В системе (1.1) базисные переменные выразим через свободные. Для того чтобы судить, оставить ли свободные переменные в числе свободных или их выгоднее с точки зрения приближения к оптимальному решению перевести в базисные, следует выразить через них и линейную форму (в данном случае она уже выражена через переменные Х1 и Х2). Тогда получим:
<img width=«18» height=«78» src=«ref-1_1246686703-162.coolpic» v:shapes="_x0000_s1027">Х3 = 750 — 5 Х1 — 2 Х2

Х4 = 807 — 4 Х1 — 5Х2

[Х5 = 840 — Х1 — 7Х2]

F = 30Х₁ +49Х₂
При Х1 = Х2 = 0 имеем Х3 = 750, Х4 = 807, Х5 = 840, что дает базисное решение (0; 0; 750; 807; 840), которое мы приняли за исходное. При этом базисном решении значение линейной формы

<img width=«48» height=«40» src=«ref-1_1246686865-191.coolpic» v:shapes="_x0000_s1028">


F = 30Х₁ +49Х₂ = 0.
Когда мы предположили, что Х1 = Х2 = 0 (предприятие ничего не выпускает), была поставлена цель — найти первое, безразлично какое, базисное решение. Эта цель достигнута. Теперь от этого первоначального решения нужно перейти к другому, при котором значение линейной формы увеличится. Из рассмотрения линейной формы видно, что ее значение возрастает при увеличении значений переменных Х1 и Х2. Иными словами, эти переменные невыгодно считать свободными, т. е. равными нулю, их нужно перевести в число базисных. Это и означает переход к новому базисному решению. При симплексном методе на каждом шаге решения предполагается перевод в число базисных только одной из свободных переменных. Переведем в число базисных переменную Х2 так как она входит в выражение линейной формы F = 30Х₁ +49Х₂ с большим коэффициентом.

Как только одна из свободных переменных переходит в число базисных, одна из базисных должна быть переведена на ее место в число свободных. Какую же из четырех базисных переменных нужно вывести? Ответить на этот вопрос помогут следующие рассуждения: значение Х2 необходимо сделать как можно большим, так как это соответствует конечной цели — максимизации F. Однако оказывается, что увеличение Х2 может продолжаться только до известных границ, а именно до тех пор, пока не нарушится требование неотрицательности переменных.

<img width=«13» height=«40» src=«ref-1_1246687056-115.coolpic» v:shapes="_x0000_s1029"><img width=«16» height=«42» src=«ref-1_1246687171-127.coolpic» v:shapes="_x0000_s1030">Х2 = min <img width=«31» height=«43» src=«ref-1_1246687298-313.coolpic» v:shapes="_x0000_i1063"> <img width=«23» height=«43» src=«ref-1_1246687611-298.coolpic» v:shapes="_x0000_i1064">;<img width=«23» height=«42» src=«ref-1_1246687909-299.coolpic» v:shapes="_x0000_i1065"> = min{375; 161,4; 120} = 120,

далее Х2 переведём в базисные вместо Х5.

II ш а г. Базисные переменные: Х3, Х4, Х2; свободные переменные: Х1, Х5. Выразим базисные переменные и линейную форму через свободные. В системе (1.2) берем то уравнение, из которого получено минимальное значение отношения свободного члена к коэффициенту при Х2. В данном случае это третье уравнение, которое выделено рамкой. Выразив из этого уравнения Х2, получим:
Х2 = 120 — <img width=«14» height=«42» src=«ref-1_1246688208-175.coolpic» v:shapes="_x0000_i1066"> Х1 — <img width=«14» height=«42» src=«ref-1_1246688208-175.coolpic» v:shapes="_x0000_i1067"> Х5
Подставив это выражение Х2 во все остальные уравнения системы (1.2) и в линейную форму F, получим:
<img width=«23» height=«102» src=«ref-1_1246688558-196.coolpic» v:shapes="_x0000_s1031">Х2 = 120 — <img width=«14» height=«42» src=«ref-1_1246688208-175.coolpic» v:shapes="_x0000_i1068"> Х1 — <img width=«14» height=«42» src=«ref-1_1246688208-175.coolpic» v:shapes="_x0000_i1069"> Х5

Х3 = 750 — 5 Х1 – 2(120 — <img width=«14» height=«42» src=«ref-1_1246688208-175.coolpic» v:shapes="_x0000_i1070"> Х1 — <img width=«14» height=«42» src=«ref-1_1246688208-175.coolpic» v:shapes="_x0000_i1071"> Х5) = 510 — <img width=«15» height=«42» src=«ref-1_1246689454-254.coolpic» v:shapes="_x0000_i1072"> Х1 + <img width=«14» height=«42» src=«ref-1_1246689708-235.coolpic» v:shapes="_x0000_i1073"> Х5

Х4 = 807 — 4 Х1 – 5(120 — <img width=«14» height=«42» src=«ref-1_1246688208-175.coolpic» v:shapes="_x0000_i1074"> Х1 — <img width=«14» height=«42» src=«ref-1_1246688208-175.coolpic» v:shapes="_x0000_i1075"> Х5) = 207 — <img width=«15» height=«42» src=«ref-1_1246690293-258.coolpic» v:shapes="_x0000_i1076"> Х1 + <img width=«14» height=«43» src=«ref-1_1246690551-178.coolpic» v:shapes="_x0000_i1077"> Х5




<img width=«15» height=«106» src=«ref-1_1246690729-177.coolpic» v:shapes="_x0000_s1032">Х2 = 120 — <img width=«14» height=«42» src=«ref-1_1246688208-175.coolpic» v:shapes="_x0000_i1078"> Х1 — <img width=«14» height=«42» src=«ref-1_1246688208-175.coolpic» v:shapes="_x0000_i1079"> Х5

  Х3 = 510 — <img width=«15» height=«42» src=«ref-1_1246689454-254.coolpic» v:shapes="_x0000_i1080"> Х1 + <img width=«14» height=«42» src=«ref-1_1246689708-235.coolpic» v:shapes="_x0000_i1081"> Х5

[Х4 = 207 — <img width=«15» height=«42» src=«ref-1_1246690293-258.coolpic» v:shapes="_x0000_i1082"> Х1 + <img width=«14» height=«43» src=«ref-1_1246690551-178.coolpic» v:shapes="_x0000_i1083"> Х5]

F = 30Х₁ +49(120 — <img width=«14» height=«42» src=«ref-1_1246688208-175.coolpic» v:shapes="_x0000_i1084"> Х1 — <img width=«14» height=«42» src=«ref-1_1246688208-175.coolpic» v:shapes="_x0000_i1085"> Х5) = 5880 + 23 Х1 — 7 Х5
При Х1 = Х5 = 0 имеем F = 5880. Это уже лучше, чем на I шаге, но не искомый максимум. Дальнейшее увеличение функции F возможно за счет введения переменной Х1 в число базисных; так как эта переменная входит в выражение F с положительным коэффициентом, поэтому ее увеличение приводит к увеличению линейной формы и ее невыгодно считать свободной, т. е. равной нулю.

<img width=«16» height=«42» src=«ref-1_1246692531-124.coolpic» v:shapes="_x0000_s1034"><img width=«13» height=«40» src=«ref-1_1246692655-118.coolpic» v:shapes="_x0000_s1035">Для ответа на вопрос, какую переменную вывести из базисных в свободные, примем:

Х1 = min <img width=«31» height=«42» src=«ref-1_1246692773-323.coolpic» v:shapes="_x0000_i1086"> <img width=«31» height=«43» src=«ref-1_1246693096-330.coolpic» v:shapes="_x0000_i1087">;<img width=«30» height=«43» src=«ref-1_1246693426-341.coolpic» v:shapes="_x0000_i1088"> = min{840; 108,2; 63} = 63,

далее Х1 переведём в базисные вместо Х4.

III шаг. Базисные переменные: Х1, Х2, Х3; свободные переменные: Х4, Х5. Выразим основные переменные и линейную форму через свободные. Из последнего уравнения системы (1.3) имеем:
<img width=«15» height=«42» src=«ref-1_1246693767-258.coolpic» v:shapes="_x0000_i1089"> Х1 = 207 + <img width=«8» height=«43» src=«ref-1_1246694025-171.coolpic» v:shapes="_x0000_i1090"> Х5 – Х4 => Х1 = 63 + <img width=«23» height=«43» src=«ref-1_1246694196-306.coolpic» v:shapes="_x0000_i1091"> Х5 — <img width=«15» height=«42» src=«ref-1_1246694502-258.coolpic» v:shapes="_x0000_i1092"> Х4
Подставляя это выражение в остальные уравнения и в линейную форму, получим:
<img width=«15» height=«112» src=«ref-1_1246694760-182.coolpic» v:shapes="_x0000_s1036">Х1 = 63 + <img width=«23» height=«43» src=«ref-1_1246694196-306.coolpic» v:shapes="_x0000_i1093"> Х5 — <img width=«15» height=«42» src=«ref-1_1246694502-258.coolpic» v:shapes="_x0000_i1094"> Х4

Х2 = 120 — <img width=«14» height=«42» src=«ref-1_1246688208-175.coolpic» v:shapes="_x0000_i1095"> (63 + <img width=«23» height=«43» src=«ref-1_1246694196-306.coolpic» v:shapes="_x0000_i1096"> Х5 — <img width=«15» height=«42» src=«ref-1_1246694502-258.coolpic» v:shapes="_x0000_i1097"> Х4) — <img width=«14» height=«42» src=«ref-1_1246688208-175.coolpic» v:shapes="_x0000_i1098"> Х5 = 111 — <img width=«23» height=«43» src=«ref-1_1246694196-306.coolpic» v:shapes="_x0000_i1099"> Х5 — <img width=«23» height=«43» src=«ref-1_1246696726-304.coolpic» v:shapes="_x0000_i1100"> Х4

Х3 = 510 — <img width=«15» height=«42» src=«ref-1_1246689454-254.coolpic» v:shapes="_x0000_i1101"> (63 + <img width=«23» height=«43» src=«ref-1_1246694196-306.coolpic» v:shapes="_x0000_i1102"> Х5 — <img width=«15» height=«42» src=«ref-1_1246694502-258.coolpic» v:shapes="_x0000_i1103"> Х4) + <img width=«14» height=«42» src=«ref-1_1246689708-235.coolpic» v:shapes="_x0000_i1104"> Х5 = 213 — <img width=«37» height=«42» src=«ref-1_1246698083-358.coolpic» v:shapes="_x0000_i1105"> Х5 + <img width=«29» height=«43» src=«ref-1_1246698441-327.coolpic» v:shapes="_x0000_i1106"> Х4

<img width=«15» height=«124» src=«ref-1_1246698768-192.coolpic» v:shapes="_x0000_s1037">Х1 = 63 + <img width=«23» height=«43» src=«ref-1_1246694196-306.coolpic» v:shapes="_x0000_i1107"> Х5 — <img width=«15» height=«42» src=«ref-1_1246694502-258.coolpic» v:shapes="_x0000_i1108"> Х4

  Х2 = 111 — <img width=«23» height=«43» src=«ref-1_1246694196-306.coolpic» v:shapes="_x0000_i1109"> Х5 — <img width=«23» height=«43» src=«ref-1_1246696726-304.coolpic» v:shapes="_x0000_i1110"> Х4

Х3 = 213 — <img width=«37» height=«42» src=«ref-1_1246698083-358.coolpic» v:shapes="_x0000_i1111"> Х5 + <img width=«29» height=«43» src=«ref-1_1246698441-327.coolpic» v:shapes="_x0000_i1112"> Х4

F = 5880 + 23(63 + <img width=«23» height=«43» src=«ref-1_1246694196-306.coolpic» v:shapes="_x0000_i1113"> Х5 — <img width=«15» height=«42» src=«ref-1_1246694502-258.coolpic» v:shapes="_x0000_i1114"> Х4) — 7 Х5 = 7329 — 2 Х5 — 7 Х4
Так как в выражение линейной формы переменные Х4 и Х5 входят с отрицательным коэффициентами, то никакое увеличение F за счет этих переменных невозможно.

Следовательно, на III шаге критерий оптимальности достигнут и задача решена. Оптимальным служит решение (63;111;213;207;0), при котором Fmаx= 7329.

Таким образом, для получения наибольшей прибыли, равной 7329 ден. ед., из данных запасов сырья предприятие должно изготовить 63 вида изделий А1 и 111изделий вида А2.

Ответ: Х1* = 63; Х2* = 111. Fmаx= 7329.
Решить задачу табличным симплексным методом

Рассмотренный симплексный метод решения ЗЛП в предыдущем пункте можно свести к записи однотипно заполняемых таблиц. Осуществить это возможно, придерживаясь следующего алгоритма:

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

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

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

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

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

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

Если пункты 4-6 алгоритма не выполняются, находят новое опорное решение с использованием условий нахождения оптимального решения.

Составим математическую модель задачи. Искомый выпуск продукции А1 обозначим через Х1, продукции А2 – Х2. Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные Х1, Х2 должны удовлетворять следующей системе неравенств:
<img width=«19» height=«110» src=«ref-1_1246701383-190.coolpic» v:shapes="_x0000_s1039">5Х1+2Х2 ≤ 750

      продолжение
--PAGE_BREAK--4Х1+5 Х2 ≤ 807

Х1+7Х2 ≤ 840

Х1≥0, Х2≥0
Общая стоимость произведенной предприятием продукции при условии выпуска Х1изделий А1 и Х2 изделий А2 составляет F = 30Х₁ +49Х₂

По своему экономическому содержанию переменные Х1 и Х2 могут принимать только лишь неотрицательные значения: Х1, Х2 ≥0.

Таким образом, приходим к следующей математической задаче: среди всех неотрицательных решений системы неравенств (1.1) требуется найти такое, при котором функция F = 30Х₁ +49Х₂ принимает максимальное значение.

Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений:

<img width=«19» height=«125» src=«ref-1_1246701573-205.coolpic» v:shapes="_x0000_s1041">


5Х1+2Х2+Х3 = 750

  4Х1+5 Х2+ Х4 = 807

Х1+7Х2+Х5 = 840

Хi≥0, i=1….5
Эти дополнительные переменные по экономическому смыслу означают не используемое при данном плане производства количество сырья того или иного вида. Например, Х3 — это неиспользуемое количество сырья 1-ого вида и т.д.

Для решения задачи табличным симплексным методом прежде всего нужно найти любое базисное решение. В данном случае это легко сделать. Для этого достаточно взять в качестве базисных добавочные переменные Х3, Х4, Х5., а в качестве свободных переменные Х1 и Х2 равными нулю, получим базисное решение (0; 0; 750; 807; 840), которое к тому же оказалось допустимым. F = 30Х₁ +49Х₂ => F — 30Х₁ — 49Х₂ = 0

Переходим к поискам оптимального решения.

Составим симплексную таблицу:

Как видно из таблицы (2.1), значения всех переменных отвечают такому «плану», при котором ничего не производится, сырье не используется и значение целевой функции равно нулю (т. е. стоимость произведенной продукции отсутствует). Этот план, конечно, не является оптимальным.

Это видно и из 4-й строки таблицы (2.1), так как в ней имеется два отрицательных числа: (- 30; — 49;0;0;0). Отрицательные числа не только свидетельствуют о возможности увеличения общей стоимости производимой продукции, но и показывают, на сколько увеличится эта сумма при введении в план единицы того или другого вида продукции.

Даже с экономической точки зрения наиболее целесообразным является включение в план производства изделий А2. Это же необходимо сделать и на основании формального признака симплексного метода, поскольку максимальное по абсолютной величине отрицательное число -49, стоит в 4-й строке 2-го столбца => этот столбец является разрешающим.Определяем вектор, подлежащий исключению из базиса и выбираем разрешающую строку. Для этого находим:

<img width=«12» height=«37» src=«ref-1_1246701778-112.coolpic» v:shapes="_x0000_s1043"><img width=«11» height=«37» src=«ref-1_1246701890-111.coolpic» v:shapes="_x0000_s1044">Х2 = min <img width=«23» height=«43» src=«ref-1_1246702001-290.coolpic» v:shapes="_x0000_i1115">; <img width=«23» height=«43» src=«ref-1_1246687611-298.coolpic» v:shapes="_x0000_i1116">;<img width=«27» height=«42» src=«ref-1_1246702589-299.coolpic» v:shapes="_x0000_i1117"> = 120.

Найдя число <img width=«23» height=«42» src=«ref-1_1246687909-299.coolpic» v:shapes="_x0000_i1118"> = 120, => 3-я строка (Х5) является разрешающей. Следовательно, в базис введем Х2 вместо Х5. Тем самым мы, с экономической точки зрения определили, какое количество изделий А2 предприятие может изготовлять с учетом норм расхода и имеющихся объемов сырья каждого вида.
Таблица (2.1)

Базисные переменные

Свободные переменные

1

2

3

4

5

Х1

Х2

Х3

Х4

Х5

1

Х3

750

5

2

1

0

0

2

Х4

807

<img width=«47» height=«32» src=«ref-1_1246703187-171.coolpic» v:shapes="_x0000_s1045">4

5

0

1

0

3

Х5

840

1

7

0

0

1

4

F

0

-30

-49

0

0

0



На пересечении разрешающего столбца и строки находится разрешающий элемент — это число 7. Производим пересчет всех коэффициентов таблицы, таким образом, чтоб на месте разрешающего элемента получить 1, а в разрешающем столбце все элементы = 0.

Для этого: 1) Третью строку разделим на 7, в результате получим на месте разрешающего элемента 1.

2) Третью строку умножим на 2 и из первой строки вычтем то, что получилось при умножении. Результат записываем в первую строку.

3) Третью строку домножим на 5 и из второй строки вычтем то, что получилось при умножении. Результат записываем во вторую строку.

4) Третью строку умножим на 49 и прибавим к строке F.

При пересчете у нас в столбике F, таблицы (2.2), опять оказалось отрицательное число, а это говорит о том что решение нужно продолжать.

Далее, разрешающим столбцом у нас будет Х1, т.к отрицательное число -23 находится в нем.

<img width=«12» height=«37» src=«ref-1_1246703358-110.coolpic» v:shapes="_x0000_s1046">Определяем вектор, подлежащий исключению из базиса и выбираем разрешающую строку. Для этого находим:
<img width=«11» height=«37» src=«ref-1_1246701890-111.coolpic» v:shapes="_x0000_s1047">Х1 = min <img width=«31» height=«43» src=«ref-1_1246693096-330.coolpic» v:shapes="_x0000_i1119">; <img width=«30» height=«43» src=«ref-1_1246693426-341.coolpic» v:shapes="_x0000_i1120">;<img width=«27» height=«42» src=«ref-1_1246704250-296.coolpic» v:shapes="_x0000_i1121"> = 63.
Найдя число <img width=«30» height=«43» src=«ref-1_1246704546-336.coolpic» v:shapes="_x0000_i1122"> = 63, => 2-я строка (Х4) является разрешающей. Следовательно, в базис введем Х1 вместо Х4.

Запишем все расчёты в таблицу
Таблица (2.2)

Базисные переменные

Свободные переменные

1

2

3

4

5

Х1

Х2

Х3

Х4

Х5

1

Х3

510

<img width=«47» height=«32» src=«ref-1_1246704882-170.coolpic» v:shapes="_x0000_s1048">33/7

0

1

0

-2/7

2

Х4

207

23/7

0

0

1

-5/7

3

Х2

120

1/7

1

0

0

1/7

4

F

5880

-23

0

0

0

7



На пересечении разрешающего столбца и строки находится разрешающий элемент — это число 23/7. Производим пересчет всех коэффициентов таблицы, таким образом, чтоб на месте разрешающего элемента получить 1, а в разрешающем столбце все элементы = 0.

Для этого: 1) Третью строку разделим на <img width=«15» height=«42» src=«ref-1_1246693767-258.coolpic» v:shapes="_x0000_i1123"> и запишем получившееся в эту же строку.

2) Из первой строки вычтем вторую, умноженную на <img width=«15» height=«42» src=«ref-1_1246705310-254.coolpic» v:shapes="_x0000_i1124"> и записываем в первую строку.

3) Из третьей строки вычтем вторую умноженную на <img width=«8» height=«42» src=«ref-1_1246705564-166.coolpic» v:shapes="_x0000_i1125">, результат запишем в третью строку.

4) К строке F прибавим вторую строку умноженную на 23 и запишем в строку F.
Таблица (2.3)

Базисные переменные

Свободные переменные

1

2

3

4

5

Х1

Х2

Х3

Х4

Х5

1

Х3

213

0

0

1

-33/23

119/161

2

Х1

63

1

0

0

7/23

-5/23

3

Х2

111

0

1

0

-1/23

28/161

4

F

7329

0

0

0

7

2



Ответ: из изложенного выше экономического содержания данных таблицы (2.3) следует, что на втором шаге план задачи является оптимальным. Х1* = 63; Х2* = 111. Fmаx= 7329, это значит, что общая стоимость всей произведенной продукции, а она равна 7329 рублей, является максимальной

Решение задачи двойственным методом

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

Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой.
<img width=«2» height=«97» src=«ref-1_1246705730-79.coolpic» v:shapes="_x0000_s1049"><img width=«12» height=«97» src=«ref-1_1246705809-160.coolpic» v:shapes="_x0000_s1050">5Х1+2Х2 ≤ 750 Y1

  4Х1+5 Х2 ≤ 807 Y2

Х1+7Х2 ≤ 840 Y3

<img width=«113» height=«33» src=«ref-1_1246653094-525.coolpic» v:shapes="_x0000_i1126">

F = 30Х₁ +49Х₂ => max
Целевая функция исходной задачи задаётся на максимум, а целевая функция двойственной – на минимум.

<img width=«8» height=«74» src=«ref-1_1246706494-127.coolpic» v:shapes="_x0000_s1052"><img width=«11» height=«74» src=«ref-1_1246706621-142.coolpic» v:shapes="_x0000_s1053">Составим матрицу для исходной задачи:

А = <img width=«39» height=«71» src=«ref-1_1246706763-464.coolpic» v:shapes="_x0000_i1127">

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

<img width=«12» height=«52» src=«ref-1_1246707227-126.coolpic» v:shapes="_x0000_s1054"><img width=«12» height=«52» src=«ref-1_1246707353-126.coolpic» v:shapes="_x0000_s1055">АТ = <img width=«68» height=«49» src=«ref-1_1246707479-462.coolpic» v:shapes="_x0000_i1128">

Число переменных в двойственной задаче равно числу соотношений в системе (1.1) исходной задачи, т.е. равно трем.

Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений, т.е 750,807,840.

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




Z(Y) = 750Y1 + 807Y2 + 840Y3 => min.

<img width=«11» height=«70» src=«ref-1_1246707941-137.coolpic» v:shapes="_x0000_s1056">5Y1 + 4Y2 + Y3 ≥ 30

2Y1 + 5Y2 + 7Y3 ≥ 49
Y1 = 0

Y2 = 7

Y3 = 2

Z(Y) = 750·0 + 807·7+ 840·2 = 7329

Ответ: Z(Y) = F(Х) = 7329, Y1* = 0, Y2* = 7, Y3* = 2.
Транспортная задача линейного программирования
Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
Задача №2
Формулировка транспортной задачи

На три базы: А₁, А₂, А₃ поступил однородный груз в количествах: а₁, а₂, а₃, соответственно. Груз требуется перевезти в пять пунктов: b₁ в пункт В₁, b₂ в пункт В₂, b₃ в пункт В₃, b₄ в пункт В₄, b₅ в пункт В₅.

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



--PAGE_BREAK--