Линейное программирование

              Рис.3

Перпендикулярно вектору нужно построить одну из линий уровня. Так как задача на максиму, то перемещаем линию уровня в направлении вектора до опорной прямой. Опорной прямой является прямая, проходящая через точку пересечения граничных прямых L1 и L2 , то есть через точку C= L1 ∩ L2 . Для определения координат точки С нужно решить систему уравнений:

x1+x2 170

2x1+ 3x2 438

Получаем х1 = 120, х2 = 50. Это и будет оптимальное решение данной задачи, которому соответствует максимальное значение целевой функции

max F(X) = 22 · 120 + 15 · 50 = 2640+750=3390.

Ответ : F(X)= 3390  , при x1=120 , x2=50

2.2 Симплексный аналитический метод

Решение. Пусть х1 и х2 —  количество изделий А1 и А2, запланированных к производству.

Выполняются следующие неравенства:

x1+x2 170

2x1+ 3x2 438

  2x1+x2≤290             

x10 x20

Целевая функция, выражающая прибыль предприятия, имеет вид F = 22х1 + 15х2.

Итак, задача сводится  к нахождению максимума функции

F = 22х1 + 15х2      мах

Для того, чтобы свести систему ограничений-неравенств к системе уравнений нужно прибавить к левой части каждого неравенства добавочные неотрицательные переменные х3 , х4, х5.

Система примет вид:

   x1+x2+x3=170

   2x1+ 3x2+x4=438              (2.1)

  2 x1+x2+x5=290                                                                       

     xi0 ( i=1,2,3,4,5)

Далее нужно найти базисное решение. Пусть в качестве базисных переменных будут добавочные переменные х3 , х4, х5. Свободные переменные х1 и х2 равными нулю. Базисное решение (0; 0; 170; 438; 290). Данное базисное решение оказалось допустимым, следовательно, применении первого этапа симплексного метода не нужен.

I ш а г. Базисные переменные:  х3 , х4, х5 ; свободные  переменные: х1, х2. В системе (2.1) базисные переменные выразим через свободные.

x3=170-x1-x2                   (2.2)

         x4=438-2x1-3x2

x5=290-2x1-x2

F = 2х1 + 3х2.

При x1 = х2 = 0 имеем х3 = 170, х4 = 438, x5 = 290,  что дает базисное решение (0; 0; 170; 438; 290). При этом базисном решении значение линейной формы: F -2х1 - 3х2 = 0.

Из линейной формы видно, что ее значение возрастает при увеличении значений переменных х1 и х2. А значит, эти переменные невыгодно считать свободными, их нужно перевести в число базисных переменных.

Значение х1 необходимо сделать как можно большим, так как это соответствует конечной цели — максимизации F.

Далее, х1= min {170/1; 438/2; 290/2} = 145. Следовательно, х4= 0 и х4 переходит в число свободных переменных, a x3 и х5 останутся положительными.

II ш а г. Базисные переменные: х1, x3, х4 ; свободные переменные: х2 , х5. Выразим базисные переменные и линейную форму через свободные. В системе (2.2) нужно взять то уравнение, из которого получено минимальное значение отношения свободного члена к коэффициенту при х1. Далее х1= 119 — 1/3х2 –1/3x4 .

x3= 25 –0,5x2+ 0,5x5              (2.3)

x4= 148 –2х2 +0,5x5

x1= 145 –0,5x2 +0,5x5

F = 3190 +4х2 –11х5.

При x2 = х5 = 0 имеем F = 3190. Для того, чтобы увеличить функцию F нужно ввести переменную х2 в число базисных, так как эта переменная с положительным коэффициентом.

х2 = min {50; 74; 290} = 50. Тогда х3 =0 и х3 переходит в число свободных переменных.

III шаг. Базисные переменные: х1, х2, х4; свободные переменные: x3, х5. Выразим основные переменные и линейную форму через свободные. Из последнего уравнения системы (1.3) (выделено) имеем x3= 25 –0,5x2+ 0,5x5

Далее нужно подставит это выражение в остальные уравнения и в линейную форму, получится:

x2 =50 –2x3+x5              (2.4)

x1 =120 +x3 –x5

x4 =48+4x3 +0,5x5

F = 22(120+х3-х5)+(50-2х3+х5)=3390-8х3-7х5.

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

Следовательно, на  III шаге задача решении и критерий оптимальности достигнут. Оптимальное решение: (120;50;0;48;0), при котором Fmаx=3390.Следовательно, для получения наибольшей прибыли, равной 3390 ден. ед., из данных запасов сырья  завод должен изготовить 120 изделия А1 и 50- А2.

2.3 Симплексные таблицы

F = 22х1 + 15х2      мах

x1+x2 170

2x1+ 3x2 438

  2x1+x2≤290             

  x10 x20

Решение. Нужно привести задачу к каноническому виду. Для сведения системы ограничений-неравенств к системе уравнений прибавим к левой части каждого неравенства добавочные неотрицательные переменные х3 , х4 , х5 . В целевую функцию переменные  х3 , х4 , х5 входит с коэффициентом 0 (т.е. не входит).

Система примет вид:

   x1+x2+x3=170

   2x1+ 3x2+x4=438

   2 x1+x2+x5=290

     xi0 ( i=1,2,3,4,5)

F = 22х1 + 15х2+0x3+0x4+0x5      мах

Линейная функция: F – 22х1 – 15х2 =0

Далее нужно заполнить первую симплексную таблицу (табл.3.1), в которой переменные х3 , х4 , х5 базисные. Последняя строка заполняется коэффициентами линейной функции с противоположным знаком.

Таблица 3.1

Нужно проверить критерий оптимальности. В последней строке имеются отрицательные коэффициенты. Нужно выбрать наибольший (-22). Первый столбец является разрешающим, переменная х1 перейдёт в базисные переменные. Оценочные отношения и х1=min(170/1;438/2; 290/2)=145 . Вторая  строка является разрешающей. На пересечении разрешающей строки и столбца стоит разрешающий элемент а31= 2.

Далее следует построение таблицы 3.2. Базисные переменные : х1 , х3 , х4 .

Расставляем нули и единицы. Нужно сделать так, чтобы в клетке, где разрешающий элемент стояла единица, а в остальных клетках по столбцу х1- нули. В последней строке против всех основных переменных нужно поставить ноль. Вторую  строку можно получить путем деления на разрешающий элемент а31=2. По правилу прямоугольника нужно заполнить остальные клетки таблицы.

Таблица 3.2

Критерий оптимальности не выполнен. Теперь второй столбец разрешающий. х2 переходит в базисные переменные. min(25/0.5; 148/2; 145/1)=50. Первая строка является разрешающей и разрешающий элемент – а12 .

Симплексная таблица примет вид (табл. 3.3):

Таблица 3.3

Критерий оптимальности выполнен, значит Fmax=3390, оптимальное базисное решение (120; 50; 0; 48;0).

План выпуска продукции, включающий изготовление 120 изделий  А1 и 50 изделий А2, является оптимальным. При данном плане выпуска изделий полностью используется сырье I и II видов и остается неиспользованным 48 ед сырья II вида, а стоимость производимой продукции равна  3390 ден ед.

2.4 Двойственная задача

Задача 2: На 3 базы А1,  А2, А3 поступил однородный груз в количествах: а1,  а2, а3 . Соответственно груз требуется перевести в 5 пунктов: b1 в пункт В1, b2   в пункт В2, b3 в пункт В3, b4 в пункт В4, b5 в пункт В5.

Спланировать перевозки так, чтобы общая их стоимость была минимальной.

F(X)=22x1+15x2→ max,

  x1+x2 170

2x1+ 3x2 438

2x1+  x2 ≤ 290

   x10 x20

Z(Y)=170y1+438y2+290y3→min

y1+2y2+2y3≥22

y1+3y2+  y3 ≥15

yi≥0 i=1,2,3

Z(Y)=600y1+357y2+600y3→min

3y1+3y2+y3–y4= 42

4y1+y2+5y3–y5=26

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

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

175+165+180=520, 90+120+110+130+70=520, суммарные запасы поставщиков совпадают с запросами потребителей, следовательно, задача с правильным балансом.

Таблица 1