рефераты конспекты курсовые дипломные лекции шпоры

Раздел Программирование
/
ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СИМПЛЕКС-МЕТОД

Реферат Курсовая Конспект

Выберите учебное заведение

ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СИМПЛЕКС-МЕТОД

ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СИМПЛЕКС-МЕТОД - раздел Программирование, Методические указания по изучению методов математического программирования Общие рекомендации по использованию программного обеспечения Постановка Задачи Линейного Программирования ...

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

в стандартной форме (СЗЛП).

Найти вектор x=(x₁...,xn), что минимизирует целевую функцию

L(x)= c₁x₁ + ... + c_nx_n (2.1)

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

a₁₁x₁ + . . . + a_1n x_n = a₁₀

. . . . . . . . . . . . . . . . . . . . . . . (2.2)

a_m1x₁ + . . . + a_mnx_n = a_m0

x_j³0, j=1...,n. (2.3)

В задаче (2.1)–(2.3) будем называть матрицу A=||a_ij||, i=1...,m, j=1...,n, матрицей условий; вектор-столбец A_j=(a_1j...,amj) т, j=1...,n — j-м вектором условий; вектор A₀=(a₁₀...,am0) т— вектором ограничений.

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

Вектор x=(x₁...,xn) называется допустимым решением ЗЛП, если его компоненты удовлетворяют ограничение (2.2)–(2.3).

Ненулевое допустимое решение x — базисный (ДБР), если его положительным компонентам x_j отвечают линейно независимые векторы условий A_j. (Нулевое допустимое решение будем всегда считать базисным).

Система m линейно независимых векторов условий, что включает указанные векторы Aj, называется базисом.

Векторы базиса образуют базисную матрицу.

Изложение симплекс-метода.

Симплекс-метод (СМ) непосредственно применяется к развязыванию каноничной задачи линейного программирования (КЗЛП) и осуществляет целеустремленное перебирание допустимых базисных решений (ДБР) (вершин допустимого многогранника решений ЗЛП, что определяется ограничениями (2.2)–(2.3)), к множеству которых принадлежит оптимальное решение, если он существует; или определяет, что ЗЛП не имеет оптимального решения.

ЗЛП — каноничная, если ее ограничения (2.2) имеют каноничную форму:

x_i + a_i,m+1 x_m+1 + ... + a_inx_n = a_i0, a_i0³0, i=1...,m

то есть, матрица условий A=||a_ij||, i=1...,m, j=1...,n, заключает в себе единичную подматрицу размера m´m и вектор ограничений A₀=(a₁₀...,am0) т— неотъемлемый.

КЗЛП элементарно определяет такие основные в линейном программировании конструкции:

· некоторый ДБР — x(0)=(a₁₀...,am0,0,...,0);

· его базис — m-мерные единичные векторы (1,0...,0) т, (0,1...,0) т..., (0...,0,1) т;

· его базисную матрицу B — единичную матрицу размера m´m;

· базисные переменные — x₁...,xm.

Стандартная ЗЛП (2.1)–(2.3) сводится в общем случае к каноничной ЗЛП добавлением искусственных неотъемлемых переменных к левым частям ограничений (2.2) и введением этих же переменных с достаточно большим коэффициентом М>0 к целевой функции (2.1) (М-метод).

М-задача имеет вид:

L(x)= c₁x₁ + ... + c_nx_n + M(y₁ + ... + y_m) ® min

a₁₁x₁ + . . . + a_1n x_n + y₁ = a₁₀

. . . . . . . . . . . . . . . . . . . . . . . . . . . . ,

a_m1x₁ + . . . + a_mnx_n + y_m = a_m0

xj³0, j=1...,n, yi³0, i=1...,m

a_i0³0, i=1...,m.

Признак оптимума: Если на некотором шаге СМ симплекс - разницы (см. алгоритм) ДБР x* незначительные, то x* — оптимальное решение КЗЛП.

Условия отсутствия решения:

1. ЗЛП не имеет оптимального решения, если на каком-либо шаге хотя бы один вектор условий Aj с отрицательной оценкой Djне имеет положительных компонент;

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

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

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

1. Рассматривается ДБР x=(a10...,am0,0,...,0).

Вычисляются относительные оценки (симплекс - разницы) Dj небазисных переменных x_j, j=m+1...,n, за формулой:

Dj=c_j– (c_б, Aj)

где c_б=(c₁...,cm), Aj — вектор условий, что отвечает переменной xj (относительные оценки базисных переменных приравняются нулю).

Если для всех j=1...,n, выполняется условие Dj³0, то ДБР xявляется оптимальным решением КЗЛП. Если к тому же все искусственные переменные равняются нулю, то, отбрасывая их, получим оптимальное решение исходной ЗЛП; иначе исходная ЗЛП не имеет решений (ее допустимая область пустая).

Если существует такое j, что Dj<0, а вектор условий Aj не имеет положительных компонент, то ЗЛП не имеет оптимального решения (ее целевая функция L(x) не ограничена снизу на допустимом многограннике решений). Конец вычислений.

2. Если существуют индексы j, для которых Dj<0, а соответствующие векторы условий Aj имеют положительные компоненты, то находят k за формулой

k=argminDj

j: Dj<0

и, вычисляя для a_ik>0 отношения qi=a_i0/a_ik, определяют l, что удовлетворяет соотношение

l=argminqи.

и: a_ik>0

3. Переходят к новому ДБР, путем введения к базису вектора A_k и выведения из базиса вектора A_l. Такой переход осуществляется с помощью симплекс - превращений (элементарных превращений Жордана - Гаусса) с ведущим элементом a_lk над элементами расширенной матрицы условий (2.2). Переход к пункту 1.

Программное обеспечение.

Обучающий модуль, с помощью которого ЗЛП решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО. Геометрическая интерпретация задачи линейного программирования осуществляется модулем, который вызывается из того же самого раздела.

Задание.

Решить симплекс-методом задачи линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1-№9), а также следующие задачи.

Во всех задачах, которые предлагаются ниже, все переменные неотъемлемые.

1) x1 + x2 + x3 ® min 2) 2 x1 + x2 – x3 – x4 ® min

x1 – x4 – 2 x6 = 5 x1 + x2 + 2 x3 – x4 = 2

x2 + 2 x4 – 3 x5 + x6 = 3 2 x1 + x2 – 3 x3 + x4 = 6

x3 + 2 x4 – 5 x5 + 6 x6 = 5; x1 + x2 + x3 + x4 = 7;

3) x1 – 2x2 + 3x3 ® min 4) 2x1 – 3x2 ® max 5)) 6 x1 + 4 x2 ® min

2x1 + 3x2 + 4x3 = 1 5x1 + 2x2 ³ 10 2 x1 + x2 ³ 3

–2x1 + x2 + 3x3 = 2; x1 + 3x2 £ 12; x1 – x2 £ 1;

6) 2 x1 – 4 x2 ® min 7) 7 x1 + 5 x2 ® max 8) 3 x1 + 2 x2 ® max

8 x1 – 5 x2 £ 16 7 x1 + 5 x2 ³ 7 4 x1 + 2 x2 ³ 12

x1 + 3 x2 ³ 2 7 x1 – 5 x2 ³ 35 x1 + 2 x2 £ 10

2 x1 + 7 x2 £ 9; x1 – x2 £ 0; 2 x1 + 2 x2 = 6;

9) 4 x1 + 5 x2 + 9 x3 + 11 x4 ® max 10) 2 x1 + x2 – x3 – x4 ® min

x1 + x2 + x3 + x4 £ 15 x1 + x2 + 2 x3 – x4 = 2

7 x1 + 5 x2 + 3 x3 + 2 x4 £ 80 2 x1 + x2 – 3 x3 + x4 = 6

3 x1 + 5 x2 + 10 x3 + 15 x4 £ 60; x1 + x2 + x3 + x4 = 7;

11) 4x1 + x2 – 2x3 – x4 – x5 ® min 12) x1 + 2 x2 + 3 x3 – x4 ® max

x3 – x4 + x5 = 1 x1 + 2 x2 + 3 x3 = 15

x2 + 2x4 – x5 = 1 2 x1 + x2 – 3 x3 = 20

x1 + 2x2 + 2x5 = 4; x1 + 2 x2 + x4 = 10.

Ответы:

1) x* = (7.1; 0; 0; 1.3; 0; 0.4), L(x*)= 7.1.

2) x* = (0; 4.13; 0.25; 2.63), L(x*)= 1.25.

3) Решения нет ( D = Æ ).

4) x* = (12; 0), L(x*)= 24.

5) x* = (1.33; 0.33), L(x*)= 9.33.

6) x* = (0; 1.29), L(x*)= -5.14.

7) Решения нет (целевая функция неограниченна сверху на допустимом множестве).

8) x* = (3; 0), L(x*)= 9.

9) x* = (10.16; 0; 2.95; 0), L(x*)= 67.21.

10) x* = (0; 4.13; 0.25; 2.63), L(x*)= 1.25.

11) x* = (0; 0; 0.5; 1.5; 2), L(x*)= -4.5.

12) Решения нет ( D = Æ ).

Лабораторная работа 3.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:
Методические указания по изучению методов математического программирования Общие рекомендации по использованию программного обеспечения

СОДЕРЖАНИЕ... Общие рекомендации по использованию программного обеспечения... Элементарные преобразования матриц Метод Гаусса...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СИМПЛЕКС-МЕТОД

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Твитнуть

Все темы данного раздела:

Программного обеспечения
Программное обеспечение ПО–МО содержит диалоговые обучающие программы из линейных и нелинейных методов оптимизации (математического программирования), каждая из которых вызывается с п

Постановка задачи.
Решить систему линейных алгебраических уравнений a11x1 + . . . + a1n xn = a10 . . . . . . . . . . . . . . . . . .

МОДИФИЦИРОВАН СИМПЛЕКС-МЕТОД.
Изложение модифицированного симплекс-метода. Модифицированный симплекс-метод (МСМ) непосредственно применяется к решению КЗЛП и осуществляет целенапра

ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД
Изложение двойственного симплекс-метода. Двойственный симплекс-метод (ДСМ) непосредственно применяется к решению почти каноничной задачи линейного програм

Постановка транспортной задачи.
В каждом из пунктов Pi, i=1...,m, производится ai единиц некоторого однородного продукта, а в каждом из пунктов Qj, j=1...,n, потребляется b

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

Свойства транспортной задачи.
1. Сбалансированная транспортная задача всегда допустимая и имеет оптимальное решение. 2. Ранг матрицы А ограничений транспортной

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

Метод северо-западного угла.
Метод состоит из однотипных шагов, поэтому его формальное изложение дадим лишь для 1-го шага. Заполняем северо-западную клеточку таблицы, покладая x11 = min{a1,

Алгоритм метода потенциалов.
1. Находится исходное допустимое базисное решение (ДБР), например, с помощью одного из упомянутых выше методов. 2. В дальнейшем метод потенциалов с

Программное обеспечение.
Обучающий модуль, с помощью которого транспортная задача Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ–МО

СПОСОБНОСТЯМИ. МЕТОД ПОТЕНЦИАЛОВ
Постановка транспортной задачи с ограниченными пропускными способностями (ТЗО). В пункте Pi (i=1

Свойства ТЗО и основные теоремы.
1. Ранг сложенной из векторов Aij матрицы А, ограничений транспортной задачи равняется m+n–1, откуда выплывает, чт

Выходной ДБР ТЗО. 1 этап.
На множестве невычеркнутых клеточек транспортной таблицы находят клеточку (i1,j1) с минимальными транспортными расходами

Выходной ДБР ТЗО. II этап.
Пусть X=||xij||, i=1...,m, j=1...,n — матрица перевозок, построенная на первом этапе. Положим xi,n+1 = ai – (

Потенциалы.
Потенциалы строк ui, i=1...,m, и столбцов vj, j=1...,n, определяются как решение системы vj–ui=cij

Оценки.
Оценки Dijпеременных xij для всех небазисных клеточек вычисляются за формулой Dij=cij–vj+ui (оценки базисных переменных — нулевые). Те

Новый ДБР.
Среди всех клеточек (і,j), для присоединяется к совокупности базисных клеточек. которых не выполняется критерий оптимума, избирают клеточку с наибольшим модулем оценки Dij. Пометим та

Алгоритм метода потенциалов.
1. Строится выходной ДБР. 2. Дальше метод потенциалов состоит из однотипных шагов, на каждом из которых: i) Вычисляются потенциалы u

ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ НА СЕТИ. МЕТОД МИНТИ
Постановка задачи о кратчайшем пути на сети. На сети, что задается графом (I,U), где И — множество вершин,

МЕТОД ФОРДА-ФАЛКЕРСОНА
Постановка задачи о максимальном потоке на сети. На сети, что задается графом (I,U), где I — множество вершин,

Постановка целочисленной задачи линейного программирования.
Найти вектор x=(x1...,xn), что минимизирует целевую функцию L(x)= c1x1 + ... + cnxn (9.1)

Изложение метода Гомори-1.
Метод Гомори-1 является одним из методов отсечения, идея которых заключается в следующем. Решается вспомогательная ЗЛП (9.1)–(9.3), которую получают из исходной ЦЗЛП (9.1)–(9

Алгоритм метода Гомори-1.
1. Решаем вспомогательную ЗЛП (9.1)–(9.3). Пусть x(0) — ее оптимальное решение. Если оптимальное решение не существует, то исходная ЦЗЛП также

ПРОГРАММИРОВАНИЯ. МЕТОД ГОМОРИ-2
Постановка частично целочисленной задачи линейного программирования (ЧЦЗЛП). Найти вектор x=(x1...,xn

МЕТОД ГОМОРИ-3
Постановка целочисленной задачи линейного программирования (ЦЗЛП). Найти вектор x=(x1...,xn), что

ПРОГРАММИРОВАНИЯ. МЕТОД ДАЛЬТОНА-ЛЛЕВЕЛИНА
Постановка частично дискретной задачи линейного программирования (ЧДЗЛП). Найти вектор x=(x1...,xn

МЕТОД ВЕТВЕЙ И ГРАНИЦ.
Постановка целочисленной задачи линейного программирования (ЦЗЛП). Найти вектор x=(x1...,xn), что

Изложение метода Ленд-Дойга.
Решается вспомогательная ЗЛП (13.1)–(13.3), которая получена из исходной ЦЗЛП (13.1)–(13.4) отбрасыванием условия целочисленности переменных (13.4) (ветка 0;1

Алгоритм метода Ленд-Дойга.
1. Определяются множества D(k;r) условиями (13.2), (13.3) и дополнительными ограничениями, которые возникают в процессе разветвления

ЗАДАЧА О НАЗНАЧЕНИИ. ВЕНГЕРСКИЙ МЕТОД
Постановка задачи о назначении. Найти вектор (матрицу) X=(xij, і,j=1...,n), что минимизирует целевую функцию

ЗАДАЧА О НАЗНАЧЕНИИ. МЕТОД МАКА
Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4). Алгоритм метода Мака.

МАТРИЧНЫЕ ИГРЫ. СВЯЗЬ С ЗАДАЧЕЙ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. МЕТОД БРАУНА-РОБIНСОН
Постановка матричной игры двух лиц с нулевой суммой. Найти цену игры и оптимальные смешанные стратегии игроков для матричной игры двух лиц с нулевой суммой и заданн

Метод золотого сечения.
Метод золотого сечения (МЗС) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B]. Алгоритм мето

Метод случайного поиска.
Метод случайного поиска применяется для нахождения минимума (максимума) произвольной функции y=F(x), что задана в любой допустимой области D.

Метод дихотомии (половинного деления).
Метод дихотомии (МД) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B]. Алгоритм метода реа

КВАДРАТИЧНЫЙ СИМПЛЕКС-МЕТОД
Постановка задачи нелинейного программирования. Найти вектор x=(x1...,xn), что минимизирует (максимизирует) функцию

Градиентные методы безусловной оптимизации.
Для задачи безусловной минимизации метод заключается в вычислении последовательности приближений x[s] по правилу x[s+1]=

Метод самого быстрого спуска.
Метод самого быстрого спуска представляет собой градиентный метод, в котором величина шага r[s] выбирается по правилу F(x[s]–r

Лiтература
1. Ю.М.Ермольев, И.И.Ляшко, В.С.Михалевич, В.И.Тюптя.Математические методы исследования операций. Киев, «Высшая школа», 1979. 2. Ю.Д.Попов. Линейное и нел

Хотите получать на электронную почту самые свежие новости?

Подпишитесь на Нашу рассылку

Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail

Новости и инфо для студентов

Свежие новости

Актуальные обзоры событий

Студенческая жизнь

Реклама

Соответствующий теме материал

Похожее

Популярное

Облако тегов

Здесь

Временно

Пусто

Теги

1)	x1 + x2 + x3 ® min	2)	2 x1 + x2 – x3 – x4 ® min
	x1 – x4 – 2 x6 = 5		x1 + x2 + 2 x3 – x4 = 2
	x2 + 2 x4 – 3 x5 + x6 = 3		2 x1 + x2 – 3 x3 + x4 = 6
	x3 + 2 x4 – 5 x5 + 6 x6 = 5;		x1 + x2 + x3 + x4 = 7;

3)	x1 – 2x2 + 3x3 ® min	4)	2x1 – 3x2 ® max	5))	6 x1 + 4 x2 ® min
	2x1 + 3x2 + 4x3 = 1		5x1 + 2x2 ³ 10		2 x1 + x2 ³ 3
	–2x1 + x2 + 3x3 = 2;		x1 + 3x2 £ 12;		x1 – x2 £ 1;

6)	2 x1 – 4 x2 ® min	7)	7 x1 + 5 x2 ® max	8)	3 x1 + 2 x2 ® max
	8 x1 – 5 x2 £ 16		7 x1 + 5 x2 ³ 7		4 x1 + 2 x2 ³ 12
	x1 + 3 x2 ³ 2		7 x1 – 5 x2 ³ 35		x1 + 2 x2 £ 10
	2 x1 + 7 x2 £ 9;		x1 – x2 £ 0;		2 x1 + 2 x2 = 6;

9)	4 x1 + 5 x2 + 9 x3 + 11 x4 ® max	10)	2 x1 + x2 – x3 – x4 ® min
	x1 + x2 + x3 + x4 £ 15		x1 + x2 + 2 x3 – x4 = 2
	7 x1 + 5 x2 + 3 x3 + 2 x4 £ 80		2 x1 + x2 – 3 x3 + x4 = 6
	3 x1 + 5 x2 + 10 x3 + 15 x4 £ 60;		x1 + x2 + x3 + x4 = 7;

11)	4x1 + x2 – 2x3 – x4 – x5 ® min	12)	x1 + 2 x2 + 3 x3 – x4 ® max
	x3 – x4 + x5 = 1		x1 + 2 x2 + 3 x3 = 15
	x2 + 2x4 – x5 = 1		2 x1 + x2 – 3 x3 = 20
	x1 + 2x2 + 2x5 = 4;		x1 + 2 x2 + x4 = 10.

рефераты конспекты курсовые дипломные лекции шпоры

ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СИМПЛЕКС-МЕТОД

Методические указания по изучению методов математического программирования Общие рекомендации по использованию программного обеспечения

Что будем делать с полученным материалом:

Все темы данного раздела:

Хотите получать на электронную почту самые свежие новости?

Подпишитесь на Нашу рассылку

Новости и инфо для студентов

Реклама

Соответствующий теме материал

О Сайте