Решение транспортной задачи с помощью средства MS Excel «Поиск решения»

УТВЕРЖДАЮ

 

Директор КФ СПб ГУП

________________/В.К. Подлесский/

^{подпись расшифровка подписи}

“___” ____________________ 2014г.

 

Методы оптимальных решений. Часть 2

Методические указания и задания для контрольных работ

Направление: Экономика

Форма обучения: заочная

Кафедра ЕСТЕСТВЕННО-НАУЧНЫХ ДИСЦИПЛИН

 

 

 

Красноярск 2014

 

 

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

Божков А.Р. – Красноярск: СПб ГУП (Красноярский филиал), 2014. – 13 с.

Составитель: к.ф.-м.н. Божков А.Р.

 

 

 

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

Постановки задачи

 

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

Постановка транспортной задачи. Некоторый однородный продукт, сосредоточенный у т поставщиков A_i, в количестве a_i (i = 1,..., т)единиц, необходимо доставить n потребителям B_j в количестве b_j (j = 1, ..., п)единиц.

Известна стоимость C_ij перевозки единицы груза от i -го поставщика к j -му потребителю.

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

Сформулируем экономико-математическую модель транспортной задачи.

Обозначим через X_ij количество единиц груза, запланированных к перевозке от i -го поставщика к j -му потребителю. Так как от i -ro поставщика к j -му потребителю запланировано к перевозке x_ij единиц груза, то стоимость перевозки составит C_ijX_ij. Стоимость всего плана выразится двойной суммой

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

а) все грузы должны быть перевезены, т.е.

б) все потребности должны быть удовлетворены, т.е.

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

(1)

при ограничениях (2)

(3)

(4)

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

Кроме того, предположим, что имеет место баланс производства-потребления:

(5)

Транспортная задача имеет п + т уравнений с т x п неизвестными.

Матрицу X= (X_ij) _mn , удовлетворяющую условиям (2)–(4), называют планом перевозок транспортной задачи, а X_ij называются перевозками.

План X*, при котором целевая функция (1) обращается в минимум, называется оптимальным.

Следует отметить, что m+n ограничений (3) – (4) линейно зависимы и одним из них можно пренебречь. Соответственно, опорный план транспортной задачи может содержать не более m+n–1 положительных компонент. Опорные планы, в которых положительных составляющих меньше m+n–1, называются вырожденными.

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

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

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.

Таблица 1

№ варианта	a1	a2	a3	b1	b2	b3	b4	b5	Таблица C
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

 

Задание 2. Нелинейные задачи условной оптимизации

 

Задача 1. По плану производства продукции предприятию необходимо изготовить d изделий. Эти изделия могут быть изготовлены двумя технологическими способами. Производственные затраты на изготовление n изделий первым способом равны , а для второго способа . Сколько изделий надо изготовить каждым способом, чтобы общие затраты на производство продукции были бы минимальными? Исходные данные приведены в таблице.

Таблица

№ варианта	a	b	d		№ вариант	a	b	d

 

 

Задача 2. Фирма реализует товар двумя способами: через магазин и через торговых агентов. При реализации товара в количестве x единиц через магазин расходы на реализацию составляют R₁(x), а при продаже товара в количестве y единиц через торговых агентов расходы составляют R₂(y). Требуется, используя принцип Лагранжа, составить план реализации товара, минимизирующий общие расходы, если

R₁(x) = x ² – k x +400, R₂(y) = y ² – m y +25

и общее число предназначенных для продажи товаров составляет 63 единицы.

 

Таблица

№ варианта	k	m			№ вариант	k	m

 

 

Литература

1. Соловьев В. И. Методы оптимальных решений: Учебное пособие. М.: Финансовый

Университет, 2012. 364 с.

2. Окунева Е.О., Моисеев С.И.. Методы оптимальных решений –Воронеж: ВФ МГЭИ, 2013. – 139 с.

3. Конюховский П. В. Математические методы исследования операций в экономике. — СПб: Питер, 2000.—208 с

4. Математические методы моделирования экономических систем/ Е.В. Бережная, В.И. Бережной. —М.: Финансы и статистика, 2006. – 432 с.

УТВЕРЖДАЮ

 

Директор КФ СПб ГУП

________________/В.К. Подлесский/

^{подпись расшифровка подписи}

“___” ____________________ 2014г.

 

Методы оптимальных решений. Часть 2

Методические указания и задания для контрольных работ

Направление: Экономика

Форма обучения: заочная

Кафедра ЕСТЕСТВЕННО-НАУЧНЫХ ДИСЦИПЛИН

 

 

 

Красноярск 2014

 

 

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

Божков А.Р. – Красноярск: СПб ГУП (Красноярский филиал), 2014. – 13 с.

Составитель: к.ф.-м.н. Божков А.Р.

 

 

 

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

Постановки задачи

 

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

Постановка транспортной задачи. Некоторый однородный продукт, сосредоточенный у т поставщиков A_i, в количестве a_i (i = 1,..., т)единиц, необходимо доставить n потребителям B_j в количестве b_j (j = 1, ..., п)единиц.

Известна стоимость C_ij перевозки единицы груза от i -го поставщика к j -му потребителю.

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

Сформулируем экономико-математическую модель транспортной задачи.

Обозначим через X_ij количество единиц груза, запланированных к перевозке от i -го поставщика к j -му потребителю. Так как от i -ro поставщика к j -му потребителю запланировано к перевозке x_ij единиц груза, то стоимость перевозки составит C_ijX_ij. Стоимость всего плана выразится двойной суммой

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

а) все грузы должны быть перевезены, т.е.

б) все потребности должны быть удовлетворены, т.е.

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

(1)

при ограничениях (2)

(3)

(4)

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

Кроме того, предположим, что имеет место баланс производства-потребления:

(5)

Транспортная задача имеет п + т уравнений с т x п неизвестными.

Матрицу X= (X_ij) _mn , удовлетворяющую условиям (2)–(4), называют планом перевозок транспортной задачи, а X_ij называются перевозками.

План X*, при котором целевая функция (1) обращается в минимум, называется оптимальным.

Следует отметить, что m+n ограничений (3) – (4) линейно зависимы и одним из них можно пренебречь. Соответственно, опорный план транспортной задачи может содержать не более m+n–1 положительных компонент. Опорные планы, в которых положительных составляющих меньше m+n–1, называются вырожденными.

Решение транспортной задачи с помощью средства MS Excel «Поиск решения»

 

В следующей таблице приведены исходные данные транспортной задачи:

внутри прямоугольника заданы удельные транспортные затраты на перевозку единицы груза (c _ij), справа указаны мощности поставщиков (a _i), a снизу – мощности потребителей (b _j). Найти оптимальный план закрепления поставщиков за потребителями (x _ij).

 

					Мощности поставщиков
Мощности потребителей					a b

 

В данной задаче суммарные запасы равны суммарным потребностям

т.е. данная транспортная задача является закрытой.

Ввод условий задачи состоит из следующих основных шагов:

1. Создание формы для ввода условий задачи.

2. Ввод исходных данных.

3. Назначение целевой функции.

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

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

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

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