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

2. Ввод исходных данных (Рис.1). Исходные данные задачи: сведения о мощностях поставщиков поместить в ячейки F10:F13, сведения о мощностях потребителей поместить в ячейки B14:E14, сведения о транспортных затратах на перевозку единицы груза поместить в В10:Е13. Оптимальные значения матрицы неизвестных переменных (x _ij) поместить в ячейки ВЗ:Е6, оптимальное значение целевой функции – в ячейке C16.

3. Назначение целевой функции. В ячейку С16 для целевой функции ввести формулу СУММПРОИЗВ (B3:E6;B10:E13);

4. Ввод зависимостей из математической модели:

В ячейках F3:F6 ввести формулы суммирования по строкам матрицы перевозок;

В ячейках B7:E7 ввести формулы суммирования по столбцам матрицы перевозок;

Командой меню Сервис>Поиск решения запустить средство MS Excel «Поиск решения»

• В поле «Установить целевую ячейку» ввести адрес $C$16. Если перед запуском Поиска решения была выделена целевая ячейка, то в этом поле ее адрес появится автоматически. В противном случае этот адрес нужно ввести.

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

• Ввести адреса искомых переменных: в поле «Изменяя ячейки» ввести адреса ячеек искомых переменных В$3:Е$6.

Ввод ограничений и граничных условий

• Щелкнуть по кнопке «Добавить». Появится диалоговое окно Добавление ограничения

• Установить курсор мыши в поле «Ссылка на ячейку» ввести адрес ячейки левой части первого ограничения $B$7: $E$7.

• Ввести знак ограничения =

• Установить курсор мыши в поле «Ограничения» и ввести адрес ячейки для правой части первого ограничения $B$14: $E$14.

• Щелкнуть кнопку Добавить и ввести адреса ячеек для второго ограничения.

• После ввода последнего ограничения ввести ОК.

 

Ввести параметры для решения задачи ЛП.

• В окне Поиск решения щелкнуть по кнопке Параметры. Откроется диалоговое окно Параметры поиска решения.

• Включить флажок Линейная модель, что обеспечивает применение симплекс-метода.

• Включить флажок Неотрицательные значения.

• ОК.

Вычислить решение задачи.

В результате получено решение

x ₁₃ = 80 ед. груза следует перевезти от 1-го поставщика 3-му потребителю;

x ₂₁ = 200 ед. груза следует перевезти от 2-го поставщика 1-му потребителю;

x ₂₃ = 70 ед. груза следует перевезти от 2-го поставщика 3-му потребителю;

x ₂₄ = 50 ед. груза следует перевезти от 2-го поставщика 4-му потребителю;

x ₃₂ = 100 ед. груза следует перевезти от 3-го поставщика 2-му потребителю;

x ₄₁ = 50 ед. груза следует перевезти от 4-го поставщика 1-му потребителю;

x ₄₂ = 0 ед. груза следует перевезти от 4-го поставщика 2-му потребителю.

 

Общая стоимость перевозок = 3200.

 

Метод множителей Лагранжа

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

(7.1)

где g_i и h_j называются функциями ограничения. Если среди всех функций f, g_i, h_j имеется хотя бы одна нелинейная функция, то (7.1) называется задачей нелинейного программирования. В противном случае это есть задача линейного программирования. Если все эти функции дифференцируемы в Rⁿ, то (7.1) называется гладкой задачей нелинейного программирования.

Будем считать, что задача (7.1) гладкая и составим для нее так называемую функцию Лагранжа, зависящую от n+k+m переменных :

(7.2)

где - вектор множителей Лагранжа для ограничений- неравенств, а - вектор множителя Лагранжа для ограничений-равенств.

В формулировке необходимых признаков будет применяться градиент функции L по x:

.

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

1. условия стационарности:

(7.3)

2. условия дополняющей нежесткости:

(7.4)

3. условия неотрицательности:

(7.5)

причем все множители Лагранжа и одновременно не могут быть равны нулю.

С помощью условий этой теоремы можно составить следующий алгоритм решения задачи (7.1), который называется методом множителей Лагранжа:

1. убедиться в существовании экстремальных точек (теорема Вейерштрасса и ее следствие);

2. составить функцию Лагранжа (7.2);

3. выписать все необходимые условия (7.3)-(7.5);

4. вычислить все стационарные точки, то есть найти все решения уравнений (7.3);

5. определить характер экстремума стационарных точек.

Рассмотрим более простую формулировку задачи на условный экстремум.

(7.6)

, (7.7)

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

Можно указать следующий порядок решения задачи (7.6)-(7.7) методом множителей Лагранжа:

1) составить функцию Лагранжа:

(7.8)

здесь - множители Лагранжа;

2) Найти частные производные функции Лагранжа по всем переменным и приравнять их нулю. Тем самым получим систему:

(7.9)

 

Эта система состоит из m + n уравнений. Решить эту систему (если это окажется возможным) и найти таким образом все стационарные точки функции Лагранжа;

3) из стационарных точек, взятых без координат выбрать точки, в которых функция f( имеет условные локальные экстремумы при наличии ограничений (7.7). Этот выбор осуществляется, например, с применением достаточных условий локального экстремума. Часто исследование упрощается, если использовать конкретные условия задачи.

В основе метода Лагранжа решения классической задачи оптимизации (7.6)-(7.7) лежит утверждение, что если в точке имеет экстремум, то существует такой вектор , что точка является решением системы (6.13). Следовательно, решая систему (7.9), получаем множество стационарных точек, в которых функция f может иметь экстремальные значения. При этом, как правило, неизвестен способ определения точек глобального максимума или минимума. Однако, если решения системы найдены, то для определения глобального экстремума достаточно найти значения функции в соответствующих точках области определения.

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

Пример 7.1. По плану производства продукции предприятию необходимо изготовить 200 изделий. Эти изделия могут быть изготовлены двумя технологическими способами. Производственные затраты на изготовление n изделий первым способом равны 4 n+n², а для второго способа - 8 n+n². Сколько изделий надо изготовить каждым способом, чтобы общие затраты на производство продукции были бы минимальными.

Решение.

Обозначим число изделий, изготовленных первым способом через х₁, вторым способом – х_{2 .} Тогда суммарные затраты на изготовление продукции по плану составят:

f (x₁,x₂)=4x₁+x₁²+8x₂+x₂²

При этом общее число изделий должно быть равно 200, т.е.

x₁+ x₂ =200

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

f (x₁,x₂)=4x₁+x₁²+8x₂+x₂² → min

x₁+ x₂ =200

x₁ ≥ 0, x₂ ≥ 0

Для ее расчета применим метод множителей Лагранжа.

Составим функцию Лагранжа

L(x_1,x₂,λ)=4x₁+x₁²+8x₂+x₂²+ λ (200-x₁-x₂)

Найдем частные производные функции L по x₁, x₂, λ и приравняем их к нулю:

имеем систему:

Исключим из этой системы λ, например, выразим λ из первого уравнения и подставим найденное значение во второе уравнение системы, получим:

Таким образом, по необходимому условию экстремума дифференцируемой функции получим стационарную точку X(101,99) возможного условного экстремума функции f(x₁,x₂).

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

Вспомним сначала достаточные условия существования локального экстремума для случая функции двух переменных z = f(x, y.

Обозначим вторые частные производные этой функции , , в некоторой точке M ₀ через а ₁₁, a ₁₂, a ₂₂ соответственно. Тогда достаточное усло­вие локального экстремума формулируется следующим обра­зом.

ТЕОРЕМА. Пусть в точке М ₀ (х ₀, у ₀ ) возможного экстре­мума функции z = f(x, у) и в некоторой ее окрестности все вторые частные производные этой функции непрерывны. Тогда если

то функция z = f(x, у) имеет в точке М ₀ локальный экстре­мум: минимум при а ₁₁ > 0 и максимум при а ₁₁ < 0. Если же а ₁₁ а ₂₂ — a ₁₂² ≤ 0, то данная функция не имеет локального эк­стремума в точке M ₀.

В данном примере найдем частные производные второго порядка:

Проверим условие a₁₁ a₂₂ – (a₁₂)² = 4 >0.

Так a ₁₁= 2 >0, то в точке X(101,99) функция f(x₁,x₂) имеет минимум:

(ед.)

Ответ. При изготовлении 101 детали первым способом и 99 деталей вторым способом затраты на производство будут минимальными и равными 21198 денежным единицам.

 

Задания для самостоятельной работы.

Задание 1. Решение транспортной задачи

Формулировка задачи.

Имеются три пункта производства, располагающие некоторым однородным продуктом в количествах a₁, a₂ и a₃. Продукт необходимо доставить в пять пунктов конечного потребления, платежеспособный спрос в которых составляет b₁, b₂, b₃, b₄ и b₅. Затраты на транспортировку (прямую поставку) единицы продукта от пункта производства в пункт потребления приведены в таблице С, расположенной в таблице 1

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