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

Размещено на http://www.allbest.ru

ТЕМА 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

1.1 Математическая модель задачи линейного программирования

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

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

Для составления математической модели необходимо:

1) выбрать переменные задачи;

2) составить систему ограничений;

3) задать целевую функцию.

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

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

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

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

Экстремальным значением называют максимальное или минимальное значение.

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

(1.1)

и удовлетворяют системе ограничений

(1.2)

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

Допустимым решением (планом) ЗЛП называется вектор , удовлетворяющий системе ограничений задачи.

Множество допустимых решений задачи образует область допустимых решений (ОДР).

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

Экстремальное значение целевой функции .

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

Составим математические модели некоторых задач линейного программирования (примеры 1.1 - 1.3).

Пример 1.1

Имеются стержни, длиной 5 м. Их необходимо разрезать на заготовки 2-х видов: заготовки А - длиной 1,5 м и заготовки В - длиной 0,8 м для производства 20 изделий. На каждое изделие требуется две длинных заготовки (А) и три коротких (В). Определить число стержней, которое необходимо разрезать каждым из возможных способов, чтобы изготовить нужное число изделий и минимизировать отходы.

Решение

Прежде всего, перебрав все возможные способы, построим карту раскроя одного стержня:

Способ	Количество заготовок А (по 1,5 м)	Количество заготовок В (по 0,8 м)	Отходы, м
I	3		0,5
II	2	2	0,4
III	1	4	0,3
IV		6	0,2

Для изготовления 20 изделий потребуется заготовок А: 202 = 40 шт. и заготовок В: 203 = 60 шт.

1) Введем переменные. Обозначим за - количество стержней, которые будут разрезаны I способом, - II способом, - III способом, - IV способом.

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

- отходы, полученные при разрезании стержней I способом, так как 5 - 31,5 = 0,5;

- отходы, полученные при разрезании стержней II способом, так как 5 - 21,5 - 20,8 = 0,4;

- отходы, полученные при разрезании стержней III способом, так как 5 - 11,5 - 40,8 = 0,3;

- отходы, полученные при разрезании стержней IV способом, так как 5 - 60,8 = 0,2.

Тогда .

Составим систему ограничений задачи.

а) Ограничение на заготовки А.

При разрезании стержней I способом получим заготовок А, стержней II способом - заготовок А, стержней III способом - заготовок А, при разрезании стержней IV способом заготовок А не образуется. Таким образом, всего получим заготовок А, что по условию задачи должно быть не менее 40, то есть .

б) Аналогично получим ограничение на заготовки В:

.

в) Составим ограничения на экономический смысл переменных. Так как количество стержней может быть только неотрицательным числом, то и - целые.

Итак, математическая модель данной задачи имеет вид:

;



Пример 1.2

Предприятие за 10 часов должно произвести 31 единицу продукции вида П₁ и 36 единиц продукции вида П₂. Для производства продукции каждого вида может быть использовано оборудование А₁ или А₂.

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

5, 3, 4, 6,

8, 7, 4, 2.

Решение

Для наглядности составим таблицу:

	Продукция П1	Продукция П2	Запас времени, ч
Оборудование А1	ед/ч усл. ден. ед/ч	ед/ч усл. ден. ед/ч	10
Оборудование А2	ед/ч усл. ден. ед/ч	ед/ч усл. ден. ед/ч	10
План производства, ед.	31	36

1) Обозначим за - время работы оборудования А_i по выпуску продукции П_j, .

2) Целевая функция будет представлять собой затраты на выпуск продукции, которые необходимо минимизировать. Так как затраты по выпуску продукции П_j на оборудование А_i составляют , то целевая функция будет иметь вид:

,

т. е. .

Составим систему ограничений.

а) Ограничение на выпуск продукции П₁.

На оборудовании А₁ будет произведено единиц продукции П₁.

На оборудовании А₂ будет произведено единиц продукции П₁.

Таким образом всего продукции П₁ будет произведено , что по условию должно быть равно 31, то есть получим ограничение , или .

б) Аналогично получим ограничение по выпуску продукции П₂: , или .

в) Ограничение на время работы оборудования А₁.

Время работы оборудования А₁ по выпуску обоих видов продукции не превышает плановый период 10 ч, следовательно, ограничение будет иметь вид: .

г) Аналогично получим ограничение на время работы оборудования А₂: .

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

Таким образом, математическая модель данной задачи будет иметь вид:

;

Пример 1.3

Предприятие может выпускать продукцию двух видов: П₁ и П₂. При этом используется три вида ресурсов: время работы оборудования, сырье и электроэнергия. Нормы расхода, запасы ресурсов и прибыль от реализации единицы продукции представлены в таблице:

Ресурсы	Нормы расхода на единицу продукции	Запас ресурса
	П1	П2
Время работы оборудования, ч	2	3	30
Сырье, кг	1	1	12
Электроэнергия, кВтч	2	1	20
Прибыль от единицы продукции, руб.	5	4

Найти оптимальный план выпуска продукции.

Решение

Введем переменные:

, - объем выпускаемой продукции П₁ и П₂ соответственно.

Целевая функция Z - прибыль от реализации всей выпущенной продукции.

Математическая модель данной задачи будет иметь вид:

;



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

1.2 Формы записи задач линейного программирования

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

Математическая модель ОЗЛП имеет вид:

где - заданные действительные числа.

Симметричной (стандартной) формой записи ЗЛП называется задача максимизации целевой функции (1.3) при ограничениях вида (1.4) и (1.7) или задача минимизации целевой функции (1.3) при ограничениях вида (1.6) и (1.7), т. е.

 или

где - заданные действительные числа.

Канонической формой записи ЗЛП называется задача минимизации или максимизации целевой функции (1.3) при ограничениях вида (1.5) и (1.7), т. е.

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

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

2) Переход от неравенства вида « » к неравенству вида « » (и наоборот) также осуществляется умножением исходного неравенства на (-1).

3) Переход от неравенства к равенству осуществляется введением дополнительной неотрицательной переменной. Так, если в исходной модели , то, вводя , получим , а если в исходной модели , то, вводя , получим , где .

4) При переходе от равенств к неравенствам можно руководствоваться следующим: любое уравнение эквивалентно системе двух неравенств:

5) Введение условия неотрицательности переменной. Пусть на переменную это условие не было наложено (т. е. может быть любого знака). Тогда вместо этой переменной можно ввести две неотрицательные переменные и , и представить , где . Это всегда возможно.

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

Пример 1.4

Пусть математическая модель задачи имеет следующий вид:

;

Записать для данной модели:

а) ОЗЛП;

б) симметричную форму,

в) каноническую форму.

Решение

а) Чтобы получить общую задачу линейного программирования, необходимо, чтобы на все переменные было наложено условие неотрицательности. Для наложения этого ограничения на переменную воспользуемся правилом 5. Введем две новые неотрицательные переменные и и представим , где и .

Тогда ОЗЛП будет иметь вид:

;

или (раскрыв скобки):

;

Обратите внимание, что в ОЗЛП число переменных на одну увеличилось.

б) Для составления симметричной формы воспользуемся полученной ОЗЛП (т. к. в симметричной форме также на все переменные должно быть наложено условие неотрицательности). Чтобы получить все ограничения вида « » (т. к. целевая функция на минимум) необходимо ограничение (1.9) умножить на (-1) (правило 2), а ограничение-равенство (1.10) заменить предварительно двумя ограничениями-неравенствами (правило 4):

откуда, умножив второе ограничение системы на (-1), получим ограничение (1.11) вида « ». Таким образом, симметричная форма будет иметь вид:

;

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

в) Для составления канонической формы воспользуемся полученной ОЗЛП (т. к. в канонической форме также на все переменные должно быть наложено условие неотрицательности). Чтобы получить все ограничения-равенства необходимо из ограничений-неравенств (1.8 - 1.9) получить эквивалентные ограничения-равенства. Согласно правилу 3 для этого от левой части ограничения (1.8) отнимем новую неотрицательную переменную , а к левой части ограничения (1.9) прибавим новую неотрицательную переменную . Таким образом, каноническая форма будет иметь вид:

;

Пример 1.5

Пусть математическая модель задачи имеет следующий вид:

;

Записать для данной модели:

а) ОЗЛП;

б) симметричную форму;

в) каноническую форму.

Решение

а) Чтобы все переменные задачи были неотрицательны, представим , где и .

Тогда ОЗЛП будет иметь вид:

;

б) Для составления симметричной формы воспользуемся полученной ОЗЛП. Симметричная форма будет иметь вид:

;

в) Для составления канонической формы воспользуемся полученной ОЗЛП. Каноническая форма будет иметь вид:

;

1.3 Геометрическая интерпретация и графический метод решения задач линейного программирования с двумя переменными

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

Пусть дана задача



где - заданные действительные числа.

Дадим геометрическую интерпретацию элементов этой задачи.

Каждое из ограничений-неравенств (1.13, 1.15, 1.16) системы задает на плоскости некоторую полуплоскость. Каждое из ограничений-равенств (1.14) системы задает на плоскости некоторую прямую. И полуплоскость и прямая - выпуклые множества. Т. к. пересечение любого числа выпуклых множеств является выпуклым множеством, то область допустимых решений (ОДР) задачи является выпуклым множеством.

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

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

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



Размещено на http://www.allbest.ru

Рисунок 1.1

Алгоритм графического метода решения ЗЛП с двумя переменными

1) Построить область допустимых решений.

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

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

4) Произвольную линию уровня, имеющую общие точки с ОДР, перемещаем параллельно самой себе пока она не займет положения опорной прямой в направлении вектора-градиента (при решении задачи на ) или в противоположном направлении (при решении задачи на ).

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

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

7) Вычислить значение целевой функции на оптимальном решении.

Пример 1.6

Решим графически ЗЛП, математическая модель которой составлена в примере 1.3.

;

Для построения ОДР задачи на плоскости изобразим граничные прямые (рисунок 1.2):

Затем определим, какую полуплоскость определяет соответствующее неравенство, подставив координаты какой-нибудь точки, не лежащей на данной прямой, например (0;0). Ограничения (1.17) означают, что ОДР лежит в I четверти системы координат . Соответствующие полуплоскости на рисунке показаны стрелками. Пересечение указанных полуплоскостей и определяет ОДР данной задачи (многоугольник OABCD).



Размещено на http://www.allbest.ru

Рисунок 1.2

Строим вектор-градиент целевой функции =(5;4).

Строим произвольную линию уровня, например , проходящую через начало координат и перемещаем ее параллельно самой себе в направлении вектора пока она не займет положения опорной прямой (рисунок 1.2). Оптимальное решение - точка С.

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

Откуда . Таким образом, . Подставив значение и в целевую функцию Z, получаем:

.

Таким образом, для того, чтобы получить максимальную прибыль в размере 56 ден. ед., необходимо запланировать выпуск 8 ед. продукции вида П₁ и 4 ед. продукции П₂.

Пример 1.7

Графическим методом решить ЗЛП:

Решение

Для построения ОДР задачи на плоскости изобразим граничные прямые (рисунок 1.3):

Размещено на http://www.allbest.ru

Рисунок 1.3

Затем определим, какую полуплоскость определяет соответствующее неравенство, подставив координаты какой-нибудь точки, не лежащей на этой прямой. Ограничения означают, что ОДР лежит в I четверти системы координат . Соответствующие полуплоскости на рисунке показаны стрелками. Пересечение указанных полуплоскостей и определяет ОДР данной задачи - это открытая многоугольная область ABCD.

Строим вектор-градиент целевой функции =(3;6). Берем произвольную линию уровня целевой функции, имеющую общие точки с ОДР (на рисунке она обозначена пунктирной линией) и перемещаем ее в направлении вектора-градиента для определения оптимального решения на . При этом линия уровня уходит в бесконечность, следовательно, на задача не имеет решения вследствие неограниченности целевой функции. Затем, для определения оптимального решения на , перемещаем линию уровня параллельно самой себе в направлении, противоположном вектору-градиенту пока она не займет положения опорной прямой.

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

Откуда . Таким образом, . .

Ответ: .

Пример 1.8

Графическим методом решить ЗЛП:



Решение

Для построения ОДР задачи на плоскости изобразим граничные прямые (рисунок 1.4):

Размещено на http://www.allbest.ru

Рисунок 1.4

Затем определим, какую полуплоскость определяет соответствующее неравенство, подставив координаты какой-нибудь точки, не лежащей на этой прямой. Ограничение-равенство - это есть сама граничная прямая. Ограничения означают, что ОДР лежит в I четверти системы координат . Соответствующие полуплоскости на рисунке показаны стрелками. Пересечение указанных полуплоскостей и прямой определяет ОДР данной задачи - это отрезок AB.

Строим вектор-градиент целевой функции =(-2;-3). На рисунке пунктирной линией обозначены опорные прямые, являющиеся линиями уровня целевой функции. Оптимальным решения на является точка А. Она лежит на пересечении прямых и . Для определения ее координат необходимо решить систему уравнений:

Откуда . Таким образом, . Подставив значение и в целевую функцию Z, получаем:

.

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

Откуда . Таким образом, . Подставив значение и в целевую функцию Z, получаем:

.

Ответ: , ;

, .

Пример 1.9

Графическим методом решить ЗЛП:

Решение

Для построения ОДР задачи на плоскости изобразим граничные прямые (рисунок 1.5):

Размещено на http://www.allbest.ru

Рисунок 1.5

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

Пример 1.10

Графическим методом решить ЗЛП:

Решение

Для построения ОДР задачи на плоскости изобразим граничные прямые (рисунок 1.6):

Затем определим, какую полуплоскость определяет соответствующее неравенство, подставив координаты какой-нибудь точки, не лежащей на этой прямой. Ограничения означают, что ОДР лежит в I четверти системы координат . Соответствующие полуплоскости на рисунке показаны стрелками. Пересечение указанных полуплоскостей и определяет ОДР данной задачи - это открытая многоугольная область ABCD.

Строим вектор-градиент целевой функции =(0;-3). Берем произвольную линию уровня целевой функции, имеющую общие точки с ОДР (на рисунке она обозначена пунктирной линией) и, для определения оптимального решения на , перемещаем линию уровня параллельно самой себе в направлении вектора-градиента пока она не займет положения опорной прямой. Такой точкой является любая точка луча CD. Следовательно, на задача имеет бесконечное множество решений - это луч CD. Для нахождения значения целевой функции на этих решениях, найдем координаты любой точки этого луча. Так, например, возьмем С(4;0) и .

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

Размещено на http://www.allbest.ru

Рисунок 1.6

Ответ: Оптимальные решения на - луч CD, .

1.4 Графический метод решения задач линейного программирования с n переменными

Графическим методом решаются ЗЛП, если в ее канонической форме записи число переменных и число линейно независимых уравнений связаны соотношением .

Алгоритм графического метода решения ЗЛП со многими переменными (n>2)

1) Записать каноническую форму ЗЛП.

2) Выбрать две свободные переменные.

3) Выразить все остальные переменные через свободные, т. е. решить систему ограничений заданной задачи.

4) Выразить целевую функцию через свободные переменные.

5) Полученную двухмерную задачу решить графическим методом.

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

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

Пример 1.11

Решим графически ЗЛП, математическая модель которой составлена в примере 1.2.

;

Решение

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

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

;

Пусть переменные и будут свободными, а все остальные переменные базисными. Выразим все базисные переменные через свободные.

Выразим целевую функцию через свободные переменные.

Учитывая условия неотрицательности базовых переменных, получим эквивалентную задачу с двумя переменными:



Или

Полученную двухмерную задачу решим графическим методом.

Для построения ОДР задачи на плоскости изобразим граничные прямые (рисунок 1.7):

Затем определим, какую полуплоскость определяет соответствующее неравенство, подставив координаты какой-нибудь точки, не лежащей на данной прямой, например (0;0). Ограничения означают, что ОДР лежит в I четверти системы координат . Соответствующие полуплоскости на рисунке показаны стрелками. Пересечение указанных полуплоскостей и определяет ОДР данной задачи - это многоугольник ABCDE.

Строим вектор-градиент целевой функции =(3;6).

Размещено на http://www.allbest.ru

Рисунок 1.7

Оптимальное решение достигается в точке E(3;0).

Перейдем к решению исходной задачи. Т. е. найдем значения базисных переменных:

Итак, решение исходной задачи: , .

Экономический смысл полученного решения задачи:

для того, чтобы затраты были минимальными и составили 52 усл. ден. ед. необходимо, чтобы оборудование А₁ выпускало 3 часа продукцию П₁, оборудование А₂ выпускало 4 часа продукцию П₁ и 6 часов продукцию П₂.

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

Пример 1.12

Решим графически ЗЛП:

;

Решение

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

Пусть переменные и будут свободными, а все остальные переменные базисными. Выразим все базисные переменные через свободные. Сделаем это последовательно. Сначала выразим, например, из второго ограничения-равенства базисную переменную и подставим это выражение всюду, где она встречается в модели:

;

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

;

Затем выразим, например, из первого ограничения-равенства базисную переменную и подставим это выражение всюду, где она встречается в модели:

;

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

 или

Полученную двухмерную задачу решим графическим методом.

Построим ОДР задачи (рисунок 1.8). Для этого в системе координат на плоскости изобразим граничные прямые:

Затем определим, какую полуплоскость определяет соответствующее неравенство, подставив координаты какой-нибудь точки, не лежащей на данной прямой, например (0;0). Ограничения означают, что ОДР лежит в I четверти системы координат . Соответствующие полуплоскости на рисунке показаны стрелками. Пересечение указанных полуплоскостей и определяет ОДР данной задачи - это треугольник ABC.

Вектор-градиент целевой функции =(7,8; 12,2). Так как нас интересует направление вектора-градиента, а не его длина, то можно изобразить вектор = (3,9; 6,1) = 0,5, который в два раза меньше вектора градиента.



Размещено на http://www.allbest.ru

Рисунок 1.8

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

Откуда . Таким образом, . Подставив значение и в целевую функцию Z, получаем:

.

Перейдем к решению исходной задачи, т.е. найдем значения базисных переменных:

,

.

Итак, решение исходной задачи:

, .

1.5 Симплексный метод решения задач линейного программирования

Симплексный метод основывается на следующем:

· ОДР ЗЛП является выпуклым множеством с конечным числом угловых точек, т. е. многогранником или многоугольным множеством;

· оптимальным решением ЗЛП является одна из угловых точек ОДР, если оптимальное решение единственно и не более двух угловых точек ОДР, если оптимальных решений бесконечное множество;

· угловые точки ОДР алгебраически представляют некоторые опорные решения системы ограничений задачи (опорные планы).

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

Алгоритм решения ЗЛП симплексным методом

Привести ЗЛП к каноническому виду с неотрицательной правой частью.

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

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

а) Если план оптимален, то задача решена.

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

в) Если пункты а и б алгоритма не выполняются, найти новый опорный план и перейти к пункту 3.

Нахождение начального опорного плана ЗЛП ( )

Пусть система ограничений ЗЛП представлена в канонической форме записи с неотрицательной правой частью, т. е.

.

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

Например, в системе ограничений:

первое и второе ограничения имеют предпочтительный вид, а третье - нет (предпочтительные переменные подчеркнуты).

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

Например, в системе ограничений:

предпочтительными (базисными) являются переменные , свободными являются переменные .

Приравниваем свободные переменные к нулю, тогда базисные переменные примут значения:

.

Получим начальный опорный план .

В случае, когда в каноническом виде с неотрицательной правой частью система ограничений ЗЛП не имеет предпочтительного вида, то начальный опорный план можно найти методом искусственного базиса или методом Жордановых исключений.

Нахождение начального опорного плана ЗЛП методом искусственного базиса

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

Пусть ЗЛП имеет каноническую форму записи с неотрицательной правой частью:

где .

Если ни одно из ограничений не имеет предпочтительной переменной, то М-задача запишется так:

Тогда начальный опорный план этой задачи:

Если некоторое уравнение системы имеет предпочтительный вид, то в него не следует вводить искусственную переменную.

Пример 1.13

Найти начальный опорный план ЗЛП методом искусственного базиса и значение целевой функции на этом плане:

;



Решение

Запишем ЗЛП в каноническом виде с неотрицательной правой частью.

;

Составим М-задачу:

;

Тогда начальный опорный план: , значение целевой функции на этом плане:

Пример 1.14

Найти начальный опорный план ЗЛП методом искусственного базиса и значение целевой функции на этом плане:

;

Решение

Запишем ЗЛП в каноническом виде с неотрицательной правой частью.

;

Составим М-задачу:

;

Тогда начальный опорный план: , значение целевой функции на этом плане:

Пример 1.15

Найти начальный опорный план ЗЛП методом искусственного базиса и значение целевой функции на этом плане:

;

Решение

Запишем ЗЛП в каноническом виде с неотрицательной правой частью.

;

где .

Составим М-задачу:

;

где .

Тогда начальный опорный план: , значение целевой функции на этом плане:

Нахождение начального опорного плана ЗЛП методом Жордановых исключений

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

Пусть ЗЛП имеет каноническую форму записи с неотрицательной правой частью ( ):

Если ни одно из ограничений не имеет предпочтительной переменной, то задача будет записана следующим образом:



где .

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

Таблица Жордана содержит столбцов, где - число переменных, - число предпочтительных (базисных) переменных и строки, где - число ограничений-равенств. В первом столбце «БП» записываются базисные (предпочтительные) переменные. Если ограничение не имеет предпочтительной переменной, то записывается «0». Второй столбец «1» - столбец свободных членов системы ограничений (1.19) а в -строке - элемент из (1.18). Остальные столбцы таблицы - «СП», в основной части которых находятся элементы из системы (1.19). В -строке в столбцах «СП» записываются коэффициенты при свободных переменных, стоящие в скобках выражения (1.18). Каждому ограничению-равенству из системы (1.19) соответствует строка основной части таблицы. Целевой функции (1.18) соответствует последняя строка таблицы.

Исходя из вида задачи (1.18-1.19) заполним таблицу Жордана (таблица 1.1).

Таблица 1.1

				СП
БП	1		…		...
0			…		...
...	...	...	…	...	....	...
0			…		...
...	...	...	…	...	...	...
0			…		...
			…		...

Преобразование таблицы называется шагом Жордановых исключений и осуществляется относительно выбранного разрешающего элемента. Разрешающий элемент выбирается среди положительных чисел основной части таблицы (которая выделена, ) по наименьшему отношению свободных членов (элементы столбца «1») к соответствующим положительным элементам столбца, выбранного разрешающим.

Пусть столбец будет разрешающим, тогда если для , то - разрешающий элемент.

Шаг Жордановых исключений осуществляется по следующим правилам:

элемент ( ноль или переменная) столбца «БП» в строке разрешающего элемента меняется местами с переменной ;

разрешающий элемент заменяется обратной величиной;

остальные элементы разрешающей строки делятся на разрешающий элемент;

остальные элементы разрешающего столбца делятся на разрешающий элемент и меняют знак на противоположный;

прочие элементы вычисляются по формуле:

 .

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

Размещено на http://www.allbest.ru

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

0-столбцы вычеркиваются.

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

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

Допустим, после некоторого числа шагов Жордановых преобразований все нули в левом столбце замещены переменными , т. е. получили таблицу 1.2.

Таблица 1.2

				СП
БП	1		…		...
			…		...
...	...	...	…	...	...	...
			…		...
...	...	...	…	...	...	...
			…		...
			…		...

Тогда компоненты начального опорного плана будут:

БП: ,…, ,…, ,

СП: .

Таким образом, начальный опорный план:

,

значение целевой функции на этом плане: .

Пример 1.16

Найти начальный опорный план ЗЛП, составленной в примере 1.2 методом Жордановых исключений и значение целевой функции на этом плане.

Решение

В примере 1.2 составлена ЗЛП:

;

Запишем ЗЛП в каноническом виде с неотрицательной правой частью.

;

Введенные дополнительные переменные и имеют экономический смысл, связанный с содержанием задачи. Здесь , - время простоя оборудования А₁ и А₂ соответственно.

Переменные , являются предпочтительными и для заполнения таблицы Жордана перепишем задачу в виде (1.18-1.19):

;

Здесь в третьем и в четвертом ограничениях предпочтительные переменные и оставлены в левой части.

Заполним таблицу Жордана (таблица 1.3).

Таблица 1.3

		СП
БП	1					отношения
0	31	5	0	4	0	31/5
0	36	0	3	0	6	-
	10	1	1	0	0	10/1
	10	0	0	1	1	-
	0	-8	-7	-4	-2

Пусть столбец будет разрешающим. Для нахождения разрешающей строки составим отношения свободных членов к соответствующим положительным элементам этого столбца. Т. к. в этом столбце только два положительных элемента «5» и «1», то отношения будут и . Поскольку , то элемент «5» и будет разрешающим. Шаг Жордановых исключений относительно найденного разрешающего элемента переводит таблицу 1.3 в таблицу 1.5. При этом в таблице 1.4 показан процесс вычисления элементов таблицы 1.5.

Таблица 1.4

				СП
БП	1	0
0
Z

Таблица 1.5

			СП
БП	1				отношения
	6,2	0	0,8	0	-
0	36	3	0	6	36/6
	3,8	1	-0,8	0	-
	10	0	1	1	10/1
Z	49,6	-7	2,4	-2

Пусть теперь разрешающим будет столбец . Найдем отношения свободных членов к соответствующим положительным элементам этого столбца. Это и (таблица 1.5). Т. к. , то вторая строка будет разрешающей. Итак, следующий разрешающий элемент будет «6», и шаг Жордановых исключений переводит таблицу 1.5 в таблицу 1.6.

Таблица 1.6

		СП
БП	1
	6,2	0	0,8
	6	0,5	0
	3,8	1	-0,8
	4	-0,5	1
Z	61,6	-6	2,4

Т. к. все нули в столбце «БП» замещены переменными, то в таблице 1.6 найден начальный опорный план. Выпишем его, приравняв свободные переменные к нулю, т. е. , а базисные переменные - к соответствующим элементам столбца «1», т. е. .

Итак, начальный опорный план: . Значение целевой функции на этом плане: .

Исследование на оптимальность опорного плана

Заполним симплексную таблицу 1.2, исходя из задачи, записанной в виде:

; (1.20)

(1.21)

где и - предпочтительные переменные.

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

Оценками называются элементы симплексной таблицы, расположенные на пересечении последней строки (Z-строки) и столбцов «СП» (элементы таблицы 1.2).

1) Если все оценки положительные при решении ЗЛП на (отрицательные при решении ЗЛП на ) - найденный в таблице план оптимальный и единственный.

2) Если все оценки неотрицательные при решении ЗЛП на (неположительные при решении ЗЛП на ), т. е. наряду с положительными при решении ЗЛП на (отрицательными при решении ЗЛП на ) оценками присутствуют нулевые, то найденный в таблице план оптимальный, но не единственный.

3) Если есть отрицательные при решении ЗЛП на (положительные при решении ЗЛП на ) оценки, а в соответствующих им столбцах

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

б) есть положительные элементы, то можно перейти к новому опорному плану, более близкому к оптимальному.

Переход к новому опорному плану

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

2) Перейти к новому плану преобразовав симплексную таблицу по алгоритму шага Жордановых исключений.

Пример 1.17

Решить симплексным методом ЗЛП, составленную в примере 1.2.

Решение

В предыдущем примере 1.16 для этой задачи был найден начальный опорный план. Для проверки его на оптимальность воспользуемся таблицей 1.6, в которой он записан. Т.к. среди оценок есть положительные оценки, то найденный опорный план не оптимален. Поскольку единственная положительная оценка находится в столбце , то он и будет разрешающим. Составим отношения свободных членов к соответствующим положительным элементам этого столбца (таблица 1.7). По наименьшему отношению выберем разрешающую строку. Т.к. , то строка будет разрешающей. На пересечении разрешающего столбца и разрешающей строки найдем разрешающий элемент «1» (таблица 1.7).

Таблица 1.7

		СП
БП	1			отношения
	6,2	0	0,8	6,2/0,8
	6	0,5	0	-
	3,8	1	-0,8	-
	4	-0,5	1	4/1
Z	61,6	-6	2,4

Шаг Жордановых исключений переводит таблицу 1.7 в таблицу 1.8, в которой будет получен новый опорный план, более близкий к оптимальному.

Таблица 1.8

		СП
БП	1
	3	0,4	-0,8
	6	0,5	0
	7	0,6	0,8
	4	-0,5	1
Z	52	-4,8	-2,4

Т. к. все оценки отрицательные, то полученный в таблице 1.8 опорный план оптимален и единственен. Выпишем его, приравняв свободные переменные к нулю, т.е. , а базисные переменные - к соответствующим элементам столбца «1», т.е. .

Итак, оптимальный план,

и .

Перейдем к решению исходной задачи (имеющей переменные ): и .

Пример 1.18

Решить симплексным методом ЗЛП примера 1.14.

Решение

Воспользуемся найденным в примере 1.14 начальным опорным планом.

Для проверки плана на оптимальность заполним симплексную таблицу 1.9, переписав М-задачу в виде (1.20-1.21):

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

Таблица 1.9

			СП
БП	1				отношения
	2	-1	4	-1	2/4
	8	0	1	2	8/1
	6	0	-3	4	-
Z	2М	-М-6	4М+4	-М-1

По наименьшему отношению выберем разрешающую строку. Т. к. , то строка будет разрешающей. На пересечении разрешающего столбца и разрешающей строки найдем разрешающий элемент «4» (таблица 1.9). Шаг Жордановых исключений переводит таблицу 1.9 в таблицу 1.10, в которой будет получен новый опорный план, более близкий к оптимальному.

Таблица 1.10

			СП
БП	1
Z	-2	-5		0

Полученный в таблице 1.10 опорный план оптимален, но не единственен, т. к. наряду с отрицательными оценками присутствует нулевая оценка. Выпишем его, приравняв свободные переменные к нулю, т. е. , а базисные переменные - к соответствующим элементам столбца «1», т.е. .

Итак, оптимальный план и . Перейдем к решению исходной задачи (имеющей переменные ):

и .

Пример 1.19

Решить симплексным методом ЗЛП:

Решение

Математическую модель задачи представим в канонической форме с неотрицательной правой частью:

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

Для проверки плана на оптимальность заполним симплексную таблицу. Для этого представим каноническую запись в виде (1.20-1.21):

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



		СП
БП	1			отношения
	2	2	-1	2/2
	4	1	0	4/1
	0	3	-1

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

Пример 1.20

Решить симплексным методом ЗЛП:

Решение

Математическую модель задачи представим в канонической форме с неотрицательной правой частью:

Найдем начальный опорный план ЗЛП методом Жордановых исключений. Для заполнения первой таблицы Жордана (таблица 1.11) представим каноническую форму записи в виде (1.18-1.19):



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

Таблица 1.11

		СП
БП	1				отношения
	2	2	1	0	2/1
0	12	3	4	-1	12/4
	5	-1	-4	0

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

Пусть столбец будет разрешающим. Для нахождения разрешающей строки составим отношения свободных членов к соответствующим положительным элементам этого столбца. Т. к. , то элемент «1» будет разрешающим. Шаг Жордановых исключений относительно найденного разрешающего элемента переводит таблицу 1.11 в таблицу 1.12.

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

Таблица 1.12

		СП
БП	1
	2	2	1	0
0	4	-5	-4	-1
	13	7	4	0

Пример 1.21

Решить симплексным методом ЗЛП:

Решение

Математическую модель задачи представим в канонической форме с неотрицательной правой частью:

где .

Найдем начальный опорный план ЗЛП методом Жордановых исключений. Для заполнения первой таблицы Жордана (таблица 1.13) представим каноническую форму записи в виде (1.18-1.19):



где .

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

Таблица 1.13

		СП
БП	1					отношения
0	3	-3	3	-1	-1	3/3
	1	-1	1	-2	0	1/1
	0	-12	12	-2	0

Т. к. только в столбце есть положительные элементы в основной части таблицы, то только он может быть разрешающим. Найдем отношения свободных членов к соответствующим положительным элементам этого столбца. Это и (таблица 1.13). Т. к. , то любая строка может быть разрешающей, но для получения начального опорного плана необходимо избавиться от нулей в столбце «БП», следовательно, целесообразно 0-строку взять разрешающей. На пересечении разрешающего столбца и разрешающей строки находим разрешающий элемент «3» и шаг Жордановых исключений переводит таблицу 1.13 в таблицу 1.14.

Таблица 1.14

		СП
БП	1
	1	-1
	0	0
	-12	0	2	4

В таблице 1.14 найден начальный опорный план: и . Этот опорный план оптимален, но не единственен, т. к. наряду с положительными оценками присутствует нулевая оценка.

Итак, оптимальный план и . Перейдем к решению исходной задачи (имеющей переменные , где ): и .

Пример 1.22

Решить симплексным методом ЗЛП:

Решение

Математическую модель задачи представим в канонической форме с неотрицательной правой частью:



Найдем начальный опорный план ЗЛП методом Жордановых исключений. Для заполнения первой таблицы Жордана (таблицы 1.15) представим каноническую форму записи в виде (1.18-1.19):

Здесь предпочтительные переменные и оставлены в левой части.

Таблица 1.15

		СП
БП	1					отношения
	6	3	2	-1	0	6/3
0	2	1	-4	0	-1	2/1
	5	1	-1	0	0	5/1
	20	8	5	-3	0

Пусть столбец будет разрешающим. Найдем отношения свободных членов к соответствующим положительным элементам этого столбца. Это , и (таблица 1.15). Т.к. минимальные отношения , то любая из этих двух строк (-строка или 0-строка) может быть разрешающей, но для получения начального опорного плана необходимо избавиться от нулей в столбце «БП», следовательно, целесообразно 0-строку взять разрешающей. На пересечении разрешающего столбца и разрешающей строки находим разрешающий элемент «1» и шаг Жордановых исключений переводит таблицу 1.15 в таблицу 1.16.

Таблица 1.16

		СП
БП	1				отношения
	0	14	-1	3	0/14
	2	-4	0	-1	-
	3	3	0	1	3/3
	4	37	-3	8

В таблице 1.16 найден начальный опорный план: и . Т. к. среди оценок есть положительные, то найденный план не оптимален. Перейдем к новому плану, более близкому к оптимальному. Выбираем разрешающий элемент в столбце с наибольшей положительной оценкой. Это будет столбец . Найдем отношения свободных членов к соответствующим положительным элементам этого столбца. Это и (таблица 1.16). Т. к. , то элемент «14» будет разрешающим. Шаг Жордановых исключений относительно найденного разрешающего элемента переводит таблицу 1.16 в таблицу 1.17.

Таблица 1.17

		СП
БП	1				отношения
	0				0:
	2				-
	3				3:
	4

Т. к. среди оценок есть положительная, то найденный план не оптимален. Перейдем к новому плану, более близкому к оптимальному. Выбираем разрешающий элемент в столбце с единственной положительной оценкой. Это будет столбец . По наименьшему отношению выбираем строку разрешающей. Тогда элемент «» будет разрешающим. Шаг Жордановых исключений относительно найденного разрешающего элемента переводит таблицу 1.17 в таблицу 1.18.

Таблица 1.18

		СП
БП	1
	0
	2
	3
	4

Т. к. все оценки отрицательные, то полученный в таблице 1.18 опорный план оптимален и единственен. Выпишем его, приравняв свободные переменные к нулю, т. е. , а базисные переменные - к соответствующим элементам столбца «1», т.е. .

Итак, оптимальный план, и .

Перейдем к решению исходной задачи (имеющей переменные ): и .

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

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

Пара двойственных ЗЛП в симметричной форме имеет следующий вид:

прямая задача	двойственная задача

Рассмотренная пара взаимно двойственных задач может быть экономически интерпретирована, например, так.

Прямая задача: сколько продукции j-го вида надо произвести, чтобы при заданных стоимостях единицы продукции , объемах имеющихся ресурсов и нормах расходов максимизировать выпуск продукции в стоимостном выражении?

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

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

прямая задача	двойственная задача

Между переменными двойственных задач существует следующее соответствие:

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

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

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

Если прямая задача не имеет решения, то и двойственная ей тоже не имеет решения.

Пример 1.23

Составить задачу, двойственную к ЗЛП, рассмотренной в примере 1.3. Дать экономическую интерпретацию прямой и двойственной задач. Из решения прямой задачи (пример 1.6) найти решение двойственной задачи.