Ионное легирование. Задача линейного программирования (симплекс-метод)

1 2 3 4

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

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

Задача распределения ресурса на сетях

Задача определения продолжительности проекта

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

Потоковые задачи

Путь максимальной эффективности с учетом штрафов.

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

(8)

при условиях

(9)

(10)

(11)

где - заданные постоянные величины и .

Функция (8) называется целевой функцией (или линейной формой) задачи (8) – (11), а условия (9) – (11) – ограничениями данной задачи.

Стандартной (или симметричной} задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (9) и (11), где k = m и l = n.

Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (10) и (11), где k = 0 и l = п.

Совокупность чисел ,удовлетворяющих ограничениям задачи (9) – (11), называется допустимым решением (или планом).

План , при котором целевая функция задачи (8) принимает свое максимальное (минимальное) значение, называется оптимальным.

Значение целевой функции (8) при плане Х будем обозначать через . Следовательно, X^* – оптимальный план задачи, если для любого Х выполняется неравенство [соответственно ].

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

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

8.4.1.Симплекс –метод решения ЗЛП, реализация симплекс-метода с помощью таблиц

Симплекс-метод – это аналитический метод решения основной задачи линейного программирования. Пусть требуется максимизировать линейную функцию L=c₁x₁+ c₂x₂+…+ c_nx_n+c₀ при условиях (1)

где x₁, x₂,…, x_n≥0.

Выразим x₁, x₂,…, x_r (r≤m) через остальные переменные:
(2)

где b'₁≥ 0, b'₂≥ 0, …, b'_r ≥ 0.

Переменные x₁, x₂,…, x_r называются базисными, а весь набор { x₁, x₂,…, x_r } - базисом, остальные переменные называются свободными, система ограничений (2)называется системой, приведенной к единичному базису. Подставляя в линейную форму L вместо базисных переменных их выражения через свободные переменные из системы (2), получим L=γ₀+ γ_r₊₁ x_r₊₁+…+ γ_n x_n.

Теперь, полагая все свободные переменные равными нулю, найдем значения базисных переменных: x₁= b'₁, x₂= b'₂, …, x_r= b'_r. Таким образом, решение (b'₁, b'₂, …, b'_r, 0, …, 0) системы является допустимым - оно называется базисным. Для полученного базисного решения значение линейной формы L_Б=γ₀. Решение задачи при помощи симплекс-метода распадается на ряд шагов, заключающихся в том, что от данного базиса Б мы переходим к другому базису Б' с таким расчетом, чтобы значение L_Б увеличивалось или, по крайней мере, не уменьшалось, т.е. L_Б' ≥ L_Б.

Замечание. 1. Если ограничительные условия заданы неравенствами, то их можно преобразовать в равенства путем введения новых неотрицательных переменных - так называемых балансовых (выравнивающих). Так, например, в неравенстве a₁x₁+ a₂x₂+…+ a_nx_n≤b достаточно добавить в левую часть некоторую величину x_n₊₁≥0 и получится равенство a₁x₁+ a₂x₂+…+ a_nx_n+ x_n₊₁=b.

2. Если переменная x_l не подчинена условию неотрицательности, то её заменяют разностью двух неотрицательных переменных: x_l = u_l- v_l, где u_l, v_l≥0.

3. Задача минимизации функции L сводится к задаче максимизации функции ‑ L.

Симплекс-метод обычно реализуют с помощью симплекс-таблиц. Сведем систему ограничений к единичному базису:

а линейную форму L - к виду L+ γ_r₊₁ x_r₊₁+…+ γ_j x_j +…+ γ_n x_n=γ₀. (3)

В виде таблицы эти данные можно представить так:

Базисные переменные	Свободные члены	x₁	…	x_i	…	x_r	x_r+1	…	x_j	…	x_n
x₁	b₁		…		…		a_1,r+1	…	A_1j	…	a_1n
…	…	…	…	…	…	…	…	…	…	…	…
x_i	b_i		…		…		a_i,r+1	…	a_ij	…	a_in
…	…	…	…	…	…	…	…	…	…	…	…
x_r	b_r		…		…		a_r,r+1	…	a_rj	…	a_rn
L	γ₀		…		…		γ_r₊₁	…	γ_j	…	γ_n

Равенство (3) будем называть приведенным (к свободным переменным) выражением для функции L, а коэффициенты γ_j - оценками (индексами) соответствующих свободных переменных x_j.

1. Выбираем разрешающий столбец a_p из условия: оценка γ_p<0 и хотя бы один элемент a_ip>0.

2. Выбираем q -ю разрешающую строку из условия b_q / a_qp=min{b_i / a_ip} для a_ip>0.

3. Производим пересчет элементов разрешающей q -й строки по формуле a'_qk = a_qk / a_qp (k=0,1,…,n).

4. Вычисляем элементы всех остальных строк (при k≠p) по формуле a'_ik = a_ik - a'_qk ∙ a_ip (i=0,1,…,q-1,q+1,…,r).

Следует иметь в виду следующую теорему, которую мы приводим без доказательства.

Теорема. Если после выполнения очередной итерации:

1. найдется хотя бы одна отрицательная оценка и в каждом столбце с такой оценкой окажется хотя бы один положительный элемент, т.е. γ_k<0 для некоторых k, и a_ik>0 для тех же k и некоторого i, то можно улучшить решение, выполнив следующую итерацию;

2. найдется хотя бы одна отрицательная оценка, столбец которой не содержит положительных элементов, т.е. γ_k<0, a_ik<0 для какого-то k и всех i, то функция L не ограничена в области допустимых решений (L_max→ ∞);

3. все оценки окажутся неотрицательными, т.е. γ_k≥0 для всех k, то достигнуто оптимальное решение.

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления в п пунктов назначения . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i -го пункта отправления в j -й пункт назначения, через – запасы груза в i -м пункте отправления, через – потребности в грузе в j– м пункте назначения, а через – количество единиц груза, перевозимого из i -го пункта отправления в j -й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

(63)

при условиях

(64)

(65)

(66)

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

Всякое неотрицательное решение систем линейных уравнений (64) и (65), определяемое матрицей , называется планом транспортной задачи.

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

Обычно исходные данные транспортной задачи записывают в виде таблицы (см. табл. 8.1).

Таблица 8.1

Очевидно, общее наличие груза у поставщиков равно ,а общая потребность в грузе в пунктах назначения равна единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е.

(67)

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

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

В случае превышения запаса над потребностью, т. е. вводится фиктивный (n +1)–й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю: Полученная задача является транспортной задачей, для которой выполняется равенство (67).

Аналогично, при вводится фиктивный (m +1)–й пункт отправления с запасом груза и тарифы полагаются равными нулю: Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. В дальнейшем будем рассматривать закрытую модель транспортной задачи. Если же модель конкретной задачи является открытой, то, исходя из сказанного выше, перепишем таблицу условий задачи так, чтобы выполнялось равенство (67).

Число переменных в транспортной задаче с т пунктами отправления и п пунктами назначения равно пт, а число уравнений в системах (64) и (65) равно п+т. Так как мы предполагаем, что выполняется условие (67), то число линейно независимых уравнений равно п+т– 1. Следовательно, опорный план транспортной задачи может иметь не более п + т– 1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности п+т– 1, то план является невырожденным, а если меньше – то вырожденным.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями: