Область допустимых решений задачи линейного программирования имеет вид – 1. Задачи линейного программирования

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

1.1 Основные определения и понятия

Общая задача линейного программирования (ОЗЛП) формулируется следующим образом – найти переменные задачи x₁, x₂, …, x_n, которые обеспечивают экстремум целевой функции

(1.1)

Допустимым решением (планом) задачи линейного программирования (ЗЛП) называется любой n-мерный вектор X=(x₁, x₂, …, x_n), удовлетворяющий системе ограничений равенств и неравенств. Множество допустимых решений задачи образует область допустимых решений D.

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

Каноническая задача линейного программирования (КЗЛП) имеет вид

(1.2)

Она отличается от ОЗЛП тем, что её система ограничений является системой только уравнений и все переменные неотрицательные.

Приведение ОЗЛП к каноническому виду ЗЛП:

— чтобы заменить исходную задачу минимизации на задачу максимизации (или наоборот задачу максимизации на задачу минимизации) достаточно целевую функцию умножить на «-1» и искать максимум (минимум) полученной функции;

— если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных x_n+1 ≥ 0 они преобразуются в равенства:

неравенство a_i1x₁+…+a_inx_n ≥ b_i заменяется на равенство a_i1x₁+…+a_inx_n + x_n+1 = b_i ,

неравенство a_i1x₁+…+a_inx_n ≤ b_i заменяется на равенство a_i1x₁+…+a_inx_n + x_n+1 = b_i ;

— если некоторая переменная x_k не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательны-ми переменными: x_k = x‘_k – x”_k , где x‘_k ≥ 0. x”_k ≥ 0.

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

ЗЛП с двумя неизвестными имеет вид:

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

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

Областью решения неравенства a_i1x₁+a_i2x₂ ≤ b_i является одна из двух полуплоскостей, на которые прямая a_i1x₁+a_i2x₂ = b_i, соответствующая этому неравенству, делит координатную плоскость. Чтобы определить, какая из двух полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на разделяющей прямой подставить в неравенство:

— если неравенство справедливо, то областью решений является полуплоскость, содержащая эту точку;

— если неравенство не справедливо, то областью решений является полуплоскость, не содержащая эту точку.

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

Линией уровня называется прямая с₁x₁+с₂x₂ = l, где l=const, на которой целевая функция задачи принимает постоянное значение. Все линии уровня параллельны между собой.

Градиент целевой функции

grad Z(X) задает вектор нормали C = (c₁, c₂) линий уровня. Целевая функция на линиях уровня возрастает, если линии уровня перемещать в направлении их нормали, и убывает – в противоположном направлении.

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

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

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

1. Построить ОДР.

2. Построить вектор нормали C = (c₁, c₂) и линию уровня с₁x₁+с₂x₂ = 0, проходящую через начало координат и перпендикулярную вектору С.

3. Передвигать линию уровня до опорной прямой в направлении вектора С в задаче на max, или в противоположном направлении – в задаче на min.

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

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

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

Симплекс-метод решения ЗЛП

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

— ОДР задачи линейного программирования является выпуклым множеством с конечным числом угловых точек;

— Оптимальным решением ЗЛП является одна из угловых точек ОДР. Угловые точки ОДР алгебраически представляют некоторые базисные (опорные) решения системы ограничений ЗЛП.

Базисным (опорным) решением ЗЛП называется такое допустимое решение X₀ =( x₁₀, x₂₀, …, x_m0, 0,…0), для которого векторы условий (столбцы коэффициентов при неизвестных в системе ограничений) линейно независимы.

Ненулевые координаты

x₁₀, x₂₀, …, x_m0 решения X₀ называются базисными переменными, оставшиеся координаты решения X₀ — свободными переменными. Число отличных от нуля координат опорного решения не может быть больше ранга r системы ограничений ЗЛП (числа линейно независимых уравнений в системе ограничений ЗЛП). Далее считаем, что система ограничений ЗЛП состоит из линейно независимых уравнений, т.е. r = m.

Смысл симплекс-метода заключается в целенаправленном переходе от одного опорного решения ЗЛП к другому (т.е. от одной угловой точки ОДР к другой) в направлении экстремума и состоит в последовательности этапов:

— найти начальное опорное решение;

— осуществить переход от одного опорного решения к другому;

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

Алгоритм выполнения Симплекс-метода ЗЛП

Алгоритм симплекс-метода осуществляет переход от одного опорного решения ЗЛП к другому в направлении экстремума целевой функции.

Пусть ЗЛП задана в каноническом виде (1.2) и выполнено условие

b_i≥ 0, i=1,2,…,m, (1.3)

соотношение (1.3) всегда можно выполнить, домножив соответствующее уравнение на «-1» в случае отрицательности b_i. Также считаем, что система уравнений в ограничениях задачи (1.2) линейно независима и имеет ранг

r = m. При этом вектор опорного решения имеет m ненулевых координат.

Пусть исходная задача (1.2), (1.3) приведена к виду, где базисные переменные x₁, x₂, …, x_mвыражены через свободные переменные x_m+1, x _m+2, …, x_n

(1.4)

На основе этих соотношений построим таблицу 1

Таблица 1.

Таблица 1 называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменениями содержания этой таблицы.

Алгоритм симплекс-метода:

1. В последней строке Z симплекс-таблицы в задаче на min находят наименьший положительный элемент (в задаче на max — наименьший отрицательный элемент), не считая свободного члена. Столбец, ответствующий этому элементу, называется разрешающим.

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

3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

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

5. После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Симплекс — таблица преобразуется следующим образом (таблица 2):

Таблица 2

6. Элемент таблицы 2, соответствующий разрешающему элементу таблицы 1, равен обратной величине разрешающего элемента.

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

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

9. Остальные элементы вычисляются по правилу прямоугольника: мысленно вычерчиваем прямоугольник в таблице 1, одна вершина которого совпадает с разрешающим элементом (Рэ), а другая – с элементом, который мы ищем; обозначим элемент в новой таблице 2 через (Нэ), а элемент, стоящий на этом же месте в старой таблице 1 – через (Сэ). Остальные две вершины А и В дополняют фигуру до прямоугольника. Тогда искомый элемент Нэ из таблицы 2 равен Нэ = Сэ – А*В/Рэ.

10. Критерий оптимальности. Как только получится таблица, у которой в последней строке в задаче на min все элементы отрицательны (в задаче на max все элементы положительны), считается, что экстремум найден. Оптимальное значение целевой функции равно свободному члену в строке Z, а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные полагаются равными нулю.

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

Метод искусственного базиса решения ЗЛП

Алгоритм симплекс-метода применим, если выделено какое-либо опорное решение ЗЛП, т. е, исходная ЗЛП (1.2) приведена к виду (1.4). Метод искусственного базиса предлагает процедуру построения такого опорного решения.

Метод искусственного базиса основан на введении искусственных базисных переменных y₁, y₂,…, y_m , с помощью которых система ограничений ЗЛП (2.2)

(1.5)

может быть преобразована к виду

(1.6)

Системы (1.5) и (1.6) будут эквивалентны в том случае, если все y_i будут равны нулю. Как и раньше мы считаем, что все b_i ≥ 0. Для того чтобы у_i были равны 0, мы должны преобразовать задачу таким образом, чтобы все искусственные базисные переменные y_i перешли в свободные переменные. Такой переход можно сделать алгоритмом симплекс метода относительно дополнительной целевой функции

F(y) = y₁ + y₂ + … + y_m = d₀ – (d₁ x₁+ d ₂ x ₂+…+d _nx _n ). (2.7)

Исходная симплекс таблица для данного метода имеет вид

Сначала симплекс таблица преобразуется относительно целевой функции F(y) до получения опорного решения. Опорное решение найдено, когда выполнен следующий критерий: F(y) = 0 и все искусственные переменные у_i переведены в свободные переменные. Затем из симплекс таблицы вычеркивается строка для F(y) и столбцы для у_i и решают задачу для исходной целевой функции Z(x) до получения оптимального решения.

Рекомендуется вводить минимум искусственных переменных.

studfiles.net

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

Описание метода

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

Рассмотрим задачу линейного программирования с двумя переменными и :
(1.1)   ;
(1.2)  
Здесь , есть произвольные числа. Задача может быть как на нахождение максимума (max), так и на нахождение минимума (min). В системе ограничений могут присутствовать как знаки , так и знаки .

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

Графический метод решения задачи (1) следующий.
Вначале мы проводим оси координат и и выбираем масштаб. Каждое из неравенств системы ограничений (1.2) определяет полуплоскость, ограниченную соответствующей прямой.

Так, первое неравенство
(1.2.1)  
определяет полуплоскость, ограниченную прямой . С одной стороны от этой прямой , а с другой стороны . На самой прямой . Чтобы узнать, с какой стороны выполняется неравенство (1.2.1), мы выбираем произвольную точку, не лежащую на прямой. Далее подставляем координаты этой точки в (1.2.1). Если неравенство выполняется, то полуплоскость содержит выбранную точку. Если неравенство не выполняется, то полуплоскость расположена с другой стороны (не содержит выбранную точку). Заштриховываем полуплоскость, для которой выполняется неравенство (1.2.1).

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

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

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

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

Нахождение экстремума целевой функции

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

Теперь мы можем искать экстремум целевой функции
(1.1)   .

Для этого выбираем любое число и строим прямую
(3)   .
Для удобства дальнейшего изложения считаем, что эта прямая проходит через ОДР. На этой прямой целевая функция постоянна и равна . такая прямая называется линией уровня функции . Эта прямая разбивает плоскость на две полуплоскости. На одной полуплоскости
.
На другой полуплоскости
.
То есть с одной стороны от прямой (3) целевая функция возрастает. И чем дальше мы отодвинем точку от прямой (3), тем больше будет значение . С другой стороны от прямой (3) целевая функция убывает. И чем дальше мы отодвинем точку от прямой (3) в другую сторону, тем меньше будет значение . Если мы проведем прямую, параллельную прямой (3), то новая прямая также будет линией уровня целевой функции, но с другим значением .

Таким образом, чтобы найти максимальное значение целевой функции, надо провести прямую, параллельную прямой (3), максимально удаленную от нее в сторону возрастания значений , и проходящую хотя бы через одну точку ОДР. Чтобы найти минимальное значение целевой функции, надо провести прямую, параллельную прямой (3) и максимально удаленную от нее в сторону убывания значений , и проходящую хотя бы через одну точку ОДР.

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

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

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

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

Условие задачи

Фирма выпускает платья двух моделей А и В. При этом используется ткань трех видов. На изготовление одного платья модели А требуется 2 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. На изготовление одного платья модели В требуется 3 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. Запасы ткани первого вида составляют 21 м, второго вида — 10 м, третьего вида — 16 м. Выпуск одного изделия типа А приносит доход 400 ден. ед., одного изделия типа В — 300 ден. ед.

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

Решение

Пусть переменные и означают количество произведенных платьев моделей А и В, соответственно. Тогда количество израсходованной ткани первого вида составит:
(м)
Количество израсходованной ткани второго вида составит:
(м)
Количество израсходованной ткани третьего вида составит:
(м)
Поскольку произведенное количество платьев не может быть отрицательным, то
  и   .
Доход от произведенных платьев составит:
(ден. ед.)

Тогда экономико-математическая модель задачи имеет вид:

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

Строим прямую .
При .
При .
Проводим прямую через точки (0; 7) и (10,5; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 10) и (10; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (8; 0).

Прямые и являются осями координат.

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

Заштриховываем область, чтобы точка (2; 2) попала в заштрихованную часть. Получаем четырехугольник OABC.

Строим произвольную линию уровня целевой функции, например,
(П1.1)   .
При .
При .
Проводим прямую через точки (0; 4) и (3; 0).

Далее замечаем, что поскольку коэффициенты при и целевой функции положительны (400 и 300), то она возрастает при увеличении и . Проводим прямую, параллельную прямой (П1.1), максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку четырехугольника OABC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

Решение задачи: ;

Ответ

.
То есть, для получения наибольшего дохода, необходимо изготовить 8 платьев модели А. Доход при этом составит 3200 ден. ед.

Пример 2

Условие задачи

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

Решение

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

Строим прямую .
При .
При .
Проводим прямую через точки (0; 6) и (6; 0).

Строим прямую .
Отсюда .
При .
При .
Проводим прямую через точки (3; 0) и (7; 2).

Строим прямую .
Строим прямую   (ось абсцисс).

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

Заштриховываем область по границам построенных прямых, чтобы точка (4; 1) попала в заштрихованную часть. Получаем треугольник ABC.

Строим произвольную линию уровня целевой функции, например,
.
При .
При .
Проводим прямую линию уровня через точки (0; 6) и (4; 0).
Поскольку целевая функция увеличивается при увеличении и , то проводим прямую, параллельную линии уровня и максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку треугольника АВC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

Решение задачи: ;

Ответ

.

Пример отсутствия решения

Условие задачи

Решить графически задачу линейного программирования. Найти максимальное и минимальное значение целевой функции.

Решение

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

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (2,667; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 3) и (6; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (3; 0) и (6; 3).

Прямые и являются осями координат.

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

Заштриховываем область, чтобы точка (3; 3) попала в заштрихованную часть. Получаем неограниченную область, ограниченную ломаной ABCDE.

Строим произвольную линию уровня целевой функции, например,
(П3.1)   .
При .
При .
Проводим прямую через точки (0; 7) и (7; 0).
Поскольку коэффициенты при и положительны, то возрастает при увеличении и .

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

Ищем минимум. Проводим прямую, параллельную прямой (П3.1) и максимально удаленную от нее в сторону убывания , и проходящую хотя бы через одну точку области ABCDE. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.
Минимальное значение целевой функции:

Ответ

Максимального значения не существует.
Минимальное значение
.

Автор: Олег Одинцов.     Опубликовано: 08-08-2016

1cov-edu.ru

Задача линейного программирования решается графическим способом, если в задаче — КиберПедия

-: одна переменная

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

-: три переменные

-: четыре переменные

 

I:

S: Если область допустимых решений задачи ЛП состоит из единственной точки, то целевая функция в ней

-: принимает постоянное отрицательное значение

-: принимает нулевое значение

-: не ограничена

+: достигает одновременно и максимального и минимального значений

I:

S: При решении ЗЛП на линия уров­ня при движении в направлении гра­диента выходит из множества допу­стимых планов в точке пересечения прямых и . Тогда оптимальным будет план

-: (3,1)

+: (1,3)

-: (1,2)

-: (2,0)

I:

S: При решении ЗЛП на линия уров­ня при движении в направлении гра­диента выходит из множества допу­стимых планов в точке пересечения прямых и . Тогда оптимальным будет план

-: (8,6)

-: (6,8)

-: (5,4)

+: (4,5)

I:

S: При решении ЗЛП на линия уров­ня при движении в направлении гра­диента выходит из множества допу­стимых планов в точке пересечения прямых и . Тогда оптимальным будет план

-: (4,1)

-: (3,2)

+: (2,3)

-: (1,4)

I:

S: Решением ЗЛП на являет­ся точка.

 

 

-: F

-: E

-: D

-: B

+: A

I:

S: Решением ЗЛП на являет­ся точка.

 

 

-: F

+: E

-: D

-: B

-: A

I:

S: Решением ЗЛП на являет­ся точка.

 

 

-: F

-: E

-: D

+: B

-: A

I:

S: Решением ЗЛП на являет­ся точка.

 

 

+: F

-: E

-: D

-: B

-: A

I:

S: Решением ЗЛП на являет­ся точка.

 

 

-: F

-: E

+: D

-: B

-: A

I:

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

*2

Тогда максимальное значение функ­ции равно

-: 26

-: 28

+: 30

-: 24

I:

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

Тогда максимальное значение функ­ции равно

-: 26

-: 28

+: 30

-: 24

I:

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

Тогда максимальное значение функ­ции равно

-: 26

-: 32

+: 30

-: 24

I:

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

Тогда максимальное значение функ­ции равно

-: 11

-: 14

-: 10

+: 13

I:

S: В случае решения задачи ЛП на минимум линию уровня Z = Z₀ перемещают:

-: в градиентном направлении

+: в антиградиентом направлении

-: в произвольном направлении

-: в направлении, перпендикулярном вектору – градиенту

I:

S: Область допустимых планов это

-: линия соответствующая конкретному значению целевой функции

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

-: область, образуемая пересечением осей координат и линии соответствующей конкретному значению целевой функции

-: любая линия параллельная оси абсцисс

I:

S: Линия уровня целевой функции это

+: линия, соответствующая конкретному значению целевой функции

-: любая линия, параллельная оси абсцисс

-: любая линия, перпендикулярная оси абсцисс

-: любая линия, параллельная оси ординат

I:

S: Вектор-градиент целевой функции проходит

+: через начало координат

-: перпендикулярно оси абсцисс

-: перпендикулярно оси ординат

-: через точку максимума

I:

S: Вектор-градиент целевой функции проходит

+: через точку с координатами ,где -коэффициенты целевой функции

-: параллельно оси абсцисс

-: перпендикулярно оси ординат

-: через точку минимума

I:

S: Оптимуму задачи соответствует

-: любое положение линии уровня в области допустимых планов

-: положение линии уровня, проходящей через точку ,где — коэффициенты целевой функции

-: любое положение линии уровня вне области допустимых планов

+: крайнее положение линии уровня в области допустимых планов

I:

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

-: имеет единственное решение

+: не имеет решения

-: имеет несколько решений

-: имеет бесконечно много решений

I:

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

-: всегда имеет решение

+: не всегда имеет решение

-: не имеет решения

-: имеет бесконечно много решений

I:

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

+: имеет решение

-: не имеет решения

-: имеет несколько решений

-: имеет бесконечно много решений

I:

S: Симплекс-метод предназначен для решения

-: системы нелинейных уравнений

+: задачи линейного программирования

-: системы трансцендентных уравнений

— задачи динамического программирования

I:

S: Если область допустимых планов не пуста и ограничена, то допустимый план находится

-: на границе области допустимых планов

-: внутри границ области допустимых планов

+: в любой точке (внутри и на границе области допустимых планов)

-: вне границ области допустимых планов

I:

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

Тогда максимальное значение функции равно

-: 11

+: 13

-: 10

-: 15

I:

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

Тогда минимальное значение функции равно

-: 1

-: 3

+: 2

-: 0

 

I:

S: Если область допустимых планов не пуста и ограничена, то оптимальный план находится

-: вне границ области допустимых планов

+: на границе области допустимых планов

-: внутри границ области допустимых планов

-: в любой точке (внутри и на границе области допустимых планов)

I:

S: Если область допустимых планов не пуста и ограничена и существует единственный оптимальный план, то он находится

-: на одной из границ области допустимых планов

+: в одной из вершин области допустимых планов

-: внутри границ области допустимых планов

-: вне границ области допустимых планов

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

-: вне границ области допустимых планов

+: на одной из границ области допустимых планов

-: в одной из вершин области допустимых планов

-: внутри границ области допустимых планов

I:

S: Связанным называется ограничение, определяемое

-: строгим неравенством

-: нестрогим неравенством

+: равенством

I:

S: Целевая функция: , ограничения: <=3; <=2; >=0; >=0. Координаты плана, максимизирующего

-:

-:

+:

-:

I:

S: Целевая функция: , ограничения: <=2; <=3; >=0; >=0. Координаты плана, максимизирующего

+:

-:

-:

-:

I:

S: Целевая функция: , ограничения: <=3; <=3; >=0; >=0. Координаты плана, максимизирующего

-:

-:

-:

+:

I:

S: Целевая функция: , ограничения: <=3; <=3; >=0; >=0. Координаты плана, максимизирующего

-:

+:

-:

-:

I:

S: Целевая функция: , ограничения: <=3; <=3; >=0; >=0. Координаты плана, максимизирующего

-:

-:

-:

+: имеется множество оптимальных планов

 

cyberpedia.su

3 — Стр 26

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

будет открытой, если …

,

,

,

,

ЗАДАНИЕ N 8 сообщить об ошибке

Тема: Линейное программирование: графическое задание области допустимых решений

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

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

B

D

A

C

Решение:

Построим линию уровня и градиент целевой функции

ЗАДАНИЕ N 14 сообщить об ошибке

Тема: Функции спроса и предложения

Даны функции спроса по цене , предложения

, и «точка» равновесия	. Если
значение параметра уменьшится, то …

равновесная цена спроса-предложенияувеличится, а равновесный объем уменьшится

равновесная цена и равновесный объемспроса-предложенияувеличатся

равновесная цена спроса-предложенияуменьшится, а равновесный объем увеличится

равновесная цена и равновесный объемспроса-предложенияуменьшатся

ЗАДАНИЕ N 15 сообщить об ошибке

Тема: Теоремы сложения и умножения вероятностей

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

. Тогда вероятность того, что в течение часа потребует вмешательства наладчика только один станок, равна …

0,329

0,1

0,45

0,003

Решение:

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

станок), (вмешательства наладчика потребует только один станок). Тогда

.

Учитывая, что, получаем

ЗАДАНИЕ N 16 сообщить об ошибке

Тема: Определение вероятности

Из урны, в которой находятся 6 белых шаров и 4 черных шара, вынимают одновременно 4 шара. Тогда вероятность того, что среди отобранных 3 шара будут белыми, равна …

Решение:

Для вычисления события (среди отобранных шаров три шара будут белыми)

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

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

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

Следовательно,

ЗАДАНИЕ N 17 сообщить об ошибке

Тема: Законы распределения вероятностей дискретных случайных величин

Решение:
Если функция		интегрируема на	,	и	, то
		.
Определим наименьшее и наибольшее значения функции					на
отрезке	. Для этого вычислим производную				и
решим уравнение		. Тогда		. Вычислив
	,	и		,
получаем наименьшее значение			, а наибольшее –		.
Следовательно,				, или
		.

ЗАДАНИЕ N 20 сообщить об ошибке

Тема: Приложения дифференциального исчисления ФОП

Минимум функции равен …

0

ЗАДАНИЕ N 21 сообщить об ошибке

Тема: Основные методы интегрирования

Множество первообразных функции имеет вид …

Решение:

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

.

ЗАДАНИЕ N 22 сообщить об ошибке

Тема: Область определения функции

Область определения функции имеет вид …

ЗАДАНИЕ N 23 сообщить об ошибке

Тема: Производные первого порядка

Производная функции равна …

studfiles.net

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

⇐ ПредыдущаяСтр 7 из 8Следующая ⇒

Х₂

 

 

 

 

 

3 6 Х₁

Тогда минимальное значение функции Z=X₁+2X₂ равно

1) 11

2) 13

3) 4

4) 10.

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

Х₁

 

 

 

 

 

0 3 Х₁

 

Тогда максимальное значение функции Z=2X₁ −X₂ равно

1) 0

2) 6

3) 9

4) 12.

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

Х₁

 

 

 

 

 

0 3 Х₁

Тогда минимальное значение функции Z=2X₁−X₂ равно

1) -3

2) -6

3) 0

4) 6.

 

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

Х₂

 

 

 

3

 

 

5 7 Х₁

Тогда максимальное значение функции Z=X₁−3X₂ равно

1) 12

2) 4

3) -4

4) -9.

 

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

Х₂

 

 

 

3

 

 

5 7 Х₁

Тогда минимальное значение функции Z=X₁−3X₂ равно

1) 17

2) -4

3) -17

4) -24.

 

107. Максимальное значение целевой функции Z=2X₁+X₂ при ограничениях

Х₁+Х₂≤6

Х₁≤4

Х₁≥0, Х₂≥0 равно…

 

1)10

2) 11

3) 6

4) 12.

 

108. Минимальное значение целевой функции Z=2X₁+X₂ при ограничениях

Х₁+Х₂≤6

Х₁≤4

Х₁≥0, Х₂≥0 равно…

 

1) 4

2) 6

3) 0

4) -3.

 

109. Максимальное значение целевой функции Z=X₁−3X₂ при ограничениях

Х₁+Х₂≤6

Х₁≤4

Х₁≥0, Х₂≥0 равно…

 

1)18

2) 12

3) 4

4) 0.

 

110. Минимальное значение целевой функции Z=X₁−3X₂ при ограничениях

Х₁+Х₂≤6

Х₁≤4

Х₁≥0, Х₂≥0 равно…

 

1)-24

2) -18

3) 0

4) 4.

111. Максимальное значение целевой функции Z=2X₁+X₂ при ограничениях

Х₁+Х₂≤4

Х₂≤3

Х₁≥0, Х₂≥0 равно…

1) 3

2) 5

3) 8

4) 10.

 

112. Минимальное значение целевой функции Z=X₁−3X₂ при ограничениях

Х₁+Х₂≤4

Х₂≤3

Х₁≥0, Х₂≥0 равно…

1) 0

2) -9

3) -12

4) 4.

 

113. Максимальное значение целевой функции Z=X₁−3X₂ при ограничениях

Х₁+Х₂≤4

Х₂≤3

Х₁≥0, Х₂≥0 равно…

1) 0

2) 4

3) 8

4) -8.

 

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

будет закрытой если

1) а=40 b=40

2) а=40 b=30

3) а=40 b=20

4) а=40 b=10.

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

 

будет закрытой если

1) а=40 b=50

2) а=40 b=40

3) а=40 b=30

4) а=40 b=20.

 

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

 

будет закрытой если

1) а=30 b=40

2) а=30 b=30

3) а=30 b=20

4) а=30 b=10.

 

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

 

будет закрытой если

1) а=20 b=30

2) а=20 b=20

3) а=20 b=10

4) а=20 b=0.

 

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

 

будет закрытой если

1) а=60 b=40

2) а=60 b=30

3) а=60 b=20

4) а=60 b=10.

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

будет закрытой если

1) а=20 b=30

2) а=30 b=30

3) а=40 b=30

4) а=50 b=30.

 

Для сетевого графика

5 7

 

 

8 1

 

длина критического пути равна

1) 10

2) 9

3) 31

4) 12.

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

1) Система ограничений не имеет решения, то есть несовместна.

2) Числовые коэффициенты ограничений отличны от нуля.

3) Система ограничений содержит только ограничения типа «=» и единичные числовые коэффициенты.

4) Система ограничений задачи, решаемой распределительным методом, содержит ограничения типа «≤» и «≥».

 

В чем отличие общего и канонического вида линейной модели?

1) Каноническая форма модели содержит только ограничения типа «≥».

2) Каноническая форма модели содержит только ограничения типа «≤».

3) нет правильного ответа.

4) Каноническая форма модели содержит только ограничения типа строгое равенство.

Как выбирается разрешающий столбец при решении задачи симплексным методом на максимум?

1) В строке целевой функции выбирается наибольший положительный коэффициент.

2) В строке целевой функции выбирается наибольший по модулю отрицательный коэффициент.

3) В строке целевой функции выбирается наименьший по модулю коэффициент.

4) Нет правильного ответа.

Сколько занятых клеток должно быть в таблице транспортной задачи при расчете потенциалов?

1) m

2) n−m

3) m+n+1

4) m+n−1.

Область допустимых решений в графическом методе – это

1) Множество точек, обеспечивающих максимум целевой функции.

2) Множество точек, на плоскости, координаты которых удовлетворяют системе ограничений модели.

3) Множество точек, обеспечивающих минимум целевой функции.

4) Оптимальное решение задачи.

Для сетевого графика, изображенного на рисунке,

8 7 5

 

 

10 3

 

 

длина критического пути равна…

1) 15

2) 17

3) 13

4) 18.

Для сетевого графика, изображенного на рисунке,

8 10

 

 

10 3

 

 

длина критического пути равна…

1) 18

2) 17

3) 13

4) 25.

Для сетевого графика, изображенного на рисунке,

3 4

 

 

5 7

 

длина критического пути равна…

1) 10

2) 9

3) 31

4) 12.

 

Что является показателем достижения максимума при решении задачи симплексным методом?

1) Нет правильного ответа.

2) Отсутствие положительных коэффициентов в строке целевой функции симплексной таблицы.

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

4) Нулевая строка целевой функции.

 

Что является показателем достижения минимума при решении задачи симплексным методом?

1) Нет правильного ответа.

2) Отсутствие положительных коэффициентов в строке целевой функции симплексной таблицы.

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

4) Нулевая строка целевой функции.

 

Рекомендуемые страницы:

lektsia.com

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

Поиск Лекций

---

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

Выберите один ответ:

 

 

 

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

Выберите один ответ:

 

 

 

В какой точке выделенного многоугольника достигается экстремум ?

Выберите один ответ:

(3;4)

В любой точке отрезка АВ

(6;0)

(0;4)

Максимальное значение целевой функции при ограничениях равно …

Выберите один ответ:

Для ограничения вида верным будет

Выберите один ответ:

Транспортная задача будет закрытой, если …

Выберите один ответ:

a=50, b=30

a=50, b=50

a=50, b=40

a=50, b=20

Ограниченность целевой функции в допустимой области является …

Выберите один ответ:

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

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

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

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

План задачи линейного программирования, соответствующий вершине допустимой области, называется …

Выберите один ответ:

невырожденным планом

вырожденным планом

основным планом

опорным планом

В какой точке выделенного многоугольника достигается экстремум ?

Выберите один ответ:

(0;4)

(6;0)

(3;4)

В любой точке отрезка АВ

Если опорный план задачи линейного программирования имеет ровно m отличных от нуля компонент (где m – число ограничений в задаче), то он называется …

Выберите один ответ:

основным планом

вырожденным планом

каноническим планом

невырожденным планом

Множество всех планов задачи линейного программирования называется …

Выберите один ответ:

оптимальным планом

допустимой областью

решением задачи

критической областью

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

Тогда максимальное значение функции равно …

Выберите один ответ:

Суммарные затраты на перевозку для опорного плана, содержащегося в транспортной таблице равны …

Выберите один ответ:

Минимальное значение целевой функции при ограничениях равно …

Выберите один ответ:

Для ограничения вида верными будут

Выберите один или несколько ответов:

 

 

 

В какой точке выделенного многоугольника достигается экстремум ?

Выберите один ответ:

(0;4)

В любой точке отрезка АВ

(6;0)

(3;4)

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

 

 

Выберите один ответ:

2 и 3

1 и 2

Опорный план транспортной задачи

составленный методом северо-западного угла, равен …

Выберите один ответ:

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

 

 

Выберите один ответ:

1 и 2

2 и 3

1 и 3

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

Выберите один ответ:

неравенств

и равенств, и неравенств

равенств

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

Выберите один ответ:

 

Для целевой функции справедливым будет выражение …

Выберите один ответ:

 

В результате применения метода потенциалов при решении транспортной задачи получена оценочная матрица

Это означает, что проверяемый опорный план является …

Выберите один или несколько ответов:

Не оптимальным

Оптимальным

Не единственным

Единственным

 

 

Максимальное значение целевой функции при ограничениях равно …

Выберите один ответ:

 

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

Тогда максимальное значение функции равно …

Выберите один ответ:

Опорный план транспортной задачи

является __________

Выберите один ответ:

Невырожденным

Вырожденным

Неполным

Полным

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

Выберите один ответ:

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

Выберите один ответ:

 

Суммарные затраты на перевозку для опорного плана, содержащегося в транспортной таблице …

Выберите один ответ:

 

Рекомендуемые страницы:

poisk-ru.ru

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

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

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

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

(1)

(2)

(3)

где A-mxn-матрица, rank(A)=m, b− неотрицательный вектор столбец длины m (b∈ R^m, b≥0), c − вектор строка длины n (c∈Rⁿ), x − вектор столбец длины n (x∈Rⁿ).

Определение 1. Допустимым планом или планом задачи линейного программирования (1)−(3) называется вектор , удовлетворяющим ограничениям (2)−(3).

Определение 2. Опорным планом задачи линейного программирования (1)−(3) называется план , если среди соотношений (2)−(3), которым он удовлетворяет как точным равенствам, имеется n линейно независимых.

Из определения 2 следует, что понятие опорный план совпадает с понятием вершины выпуклого многогранного множества, определяемого условиями (2)−(3).

Определение 3. Опорный план задачи линейного программирования (1)−(3) называется невырожденным , если число его положительных компонент в точности равен m.

Определение 4. Задача линейного программирования называется невырожденным , если все ее опорные планы невырождены.

Определение 5. Целевой функцией задачи линейного программирования (1)−(3) называется линейная функция cx, которую нужно максимизировать (в данном случае) на заданном выпуклом многогранном множестве (2)−(3).

Определение 6. Оптимальное решение или оптимальный план − это допустимый план, при котором целевая функция достигает своего максимума (в данном случае) на заданном выпуклом многогранном множестве (2)−(3).

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

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

Начнем рассмотрение метода со второго этапа. Мы будем предполагать, что ЗЛП невырождена (Определение 4).

Симплекс метод

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

где

Очевидно, что является опорным планом ЗЛП (4)-(6). Действительно, x⁰ удовлетворяет уравнениям (5)-(6), и ровно m координат вектора x⁰ положительны, а остальные нули.

Запишем ЗЛП (4)-(6) в векторном виде:

(4′)

(5′)

(6′)

где E−единичная матрица порядка m×m,

Разделим x на базисные и свободные компоненты (базисные компоненты − это положительные компоненты вектора, а свободные компоненты − это нулевые компоненты):

(7)

где

,.

(7′)

Тогда (5′) можно записать так:

.

(8)

или

.

(9)

Отсюда

(10)

Представим c в виде объединения базисных и свободных компонент:

,

(11)

где

,.

Тогда, учитывая (7), (10) и (11), получим

Обозначим

.

(12′)

Тогда (12) можно записать так:

.

(12»)

В выражении (12) ничего не изменится, если к правой части добавить нулевой элемент:

где − нулевая вектор-строка длины m.

Обозначим

.

(14)

Выражение (14) эквивалентно следующему выражению:

(14′)

или

,.

(14»)

Тогда (13) можно записать так:

.

(15)

или

Заметим, что первые m элементы вектора Δ и последние n−m элементы вектора x нулевые (;).

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

Учитывая (7′) перезапишем (5) следующим образом:

(17)

где −p-ый элемент вектора x, которую нужно ввести в базис (т.е сделать положительным).

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

Другими словами нужно решить систему линейных неравенств

(18)

Из (18) следует

Тогда

,.

(19)

Подставляя в (18), получим:

.

(20)

Тогда при имеем

а при имеем

.

Из вышеизложенного можно сформулировать следующие теоремы:

Теорема 1 (признак оптимальности опорного плана). Опорный план задачи (4)-(6) является оптимальным, если для любого j (j=1,…,n).

Теорема 2. Если для некоторого j=k, и среди чисел (i=1,…,m) нет положительных, целевая функция (4) задачи (4)-(6) не ограничена на множестве (5)-(6).

Теорема 3. Если опорный план x задачи (4)-(6) не вырожден и для некоторого j=k, и среди чисел (i=1,…,m) есть положительные, то существует опорный план x’ такой, что cx’ >cx.

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

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

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

Далее рассматривают элементы , . Если среди них нет отрицательных элементов, то данный план является оптимальным (Теорема 1).

Пусть . Тогда рассматривают . Если среди них нет положительных элементов, то задача неограничена сверху, т.е. неразрешима (теорема 2).

Пусть среди есть положительные элементы. Тогда вычисляют для всех тех i, для которых

Тогда из базиса выходит k-я переменная, а в базис входит p— я переменная, значение которой равно .

Далее делают исключение Гаусса для столбца p выбирая в качестве ведущего элемента . Т.е. обнуляются все элементы данного столбца, кроме . Для этого нужно сложить строку i со строкой k, умноженной на . Затем строку k делят на . В результате получают следующую симплекс таблицу:

Здесь

,

,

,

.

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

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

Метод искусственного базиса

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

Пусть требуется найти максимум функции

(21)

при условиях

(22)

(23)

где и среди векторов

нет mединичных и линейно независимых.

Определение 7. Задача, состоящая в определении максимального значения функции

(24)

при условиях

где M − некоторое достаточно больное положительное число (конкретное значение обычно не задается), называется расширенной задачей по отношению к (21)−(23).

Расширенная задача (24)−(26) имеет опорный план

,

(27)

где первы n элементы нули. Переменные называются искусственными. Векторы столбцы

(28)

образуют так называемый искусственный базис m-мерного векторного пространства.

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

Теорема 4. Если в оптимальном плане расширенной задачи (24)−(26) значения искусственных переменных , то является оптимальным планом задачи (21)−(23).

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

Значение целевой функции при опорном плане (27):

Значения вычисляются из выражения (14»):

Замечаем, что F(X) и состоят из двух независимых частей, одна из которых зависим от M, а другая − нет.

После вычисления F(X) и их значения, а также исходные данные расширенной задачи заносят в симплекс таблицу, как было показано выше. Разность заключается лишь в том, что данная таблица содержит на одну строку больше, чем обычная симплекс таблица. При этом в (m+1)-ю строку помещают коэффициенты, не содержащие M, а в (m+2)-ю строку − коэффициенты при M.

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

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

Если же не все искусственные переменные исключены из базиса и элемент m+2 строки, столбца x₀ отрицателен, то исходная задача не имеет решения.

Если же не все искусственные переменные исключены из базиса и элемент m+2 строки, столбца x₀ равен нулю, то опорный план исходной задачи является вырожденным и базис содержит минимум один из векторов искусственного базиса.

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

Если в ходе итераций m+2 строка больше не содержит отрицательных элементов, то итерационный процесс продолжают с m+1 строкой, до тех пор, пока не найден оптимальный план расширенной задачи или не выявлен неразрешимость задачи.

Таким образом, процесс нахождения решения задачи линейного программирования (21)−(23) методом искусственного базиса включает следующие основные этапы:

• Составляют расширенную задачу (24)−(26).
• Находят опорный план расширенной задачи.
• Используя симплекс метод исключают искусственные векторы из базиса. В результате находят опорный план исходной задачи или фиксируют ее неразрешимость.
• Используя найденный опорный план ЗЛП (21)−(23), или находят оптимальный план исходной задачи, или устанавливают ее неразрешимость.

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

 

matworld.ru