Нахождение оптимального решения с помощью задач

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ЭКОНОМИЧЕСКОГО РАЗВИТИЯ И ТОРГОВЛИ РОССИЙСКОЙ ФЕДЕРАЦИИ

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТОРГОВО-ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ

КОНТРОЛЬНАЯ РАБОТА

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

г. Иркутск - 2008

Задание 1

Выпуск продукции фирмы задается производственной функцией типа Кобба-Дугласа y=A • Kб • Lв. Чтобы увеличить выпуск продукции на k %, надо увеличить фонды на m % или численность рабочих на n %. В фирме работают L человек, один работник за месяц производит продукции на D рублей. Основные фонды оцениваются в K рублей. Написать производственную функцию.

k (%)	m (%)	n (%)	L (чел.)	D (тыс. руб.)	К (млрд. руб.)
2	6	8	81	50	1

Решение:

Параметр в - это эластичность выпуска по труду, а параметр б - эластичность выпуска по фондам.

Поэтому ,.

Следовательно, функция Кобба?Дугласа имеет вид:

y=A • K1/3 • L1/4.

Подставляя данные производства, получим:

1 (работник) • D (продукция в рублях на одного работника) • L (всего работников) = 1 • 5 • 104 • 81 = A • K1/3 • L1/4 = A • (1•106)1/3 • 811/4, то есть 5 • 104 • 813/4 = A • 102, откуда

А = 5 • 102 • 813/4 = 135 • 102 = 13 500.

A = 13 500

Следовательно, производственная функция имеет вид:

y=13500 • K1/3 • L1/4.

Задание 2

Функция спроса на товар X имеет вид QDX = a + b • PX + c • PY, где PX - цена товара X; PY - цена товара Y. Определить коэффициент прямой и перекрестной эластичности спроса по цене. Дать экономическую интерпретацию полученных результатов.

PX (у.е.	PY (у.е.)	a	b	c
1	3	5	? 2	? 1,2

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

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

Определим сначала объем спроса на товар X:

QDX = 5 ? 2 • 1 ? 1,2 • 3 = ? 0,6

Перекрестная эластичность:

Так как EXY > 0, то речь идет о взаимозаменяемых товарах.

Прямая эластичность:

Следовательно, при уменьшении цены товара X на 1 % при неизменяемой цене товара Y спрос на товар X увеличится на .

Задание 3

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

a) графическим способом;

б) симплексным методом.

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

1. Математическая модель задачи.

Z = ? x1 + 2 • x2 > min

x1 + 3 · x2 ? 6

? x1 + 2 • x2 ? 1

x1 + x2 ? 5

3 • x1 ? x2 ? 6

x1 ? 0, x2 ? 0

2) ГРАФИЧЕСКИЙ СПОСОБ

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

При этом x1 ? 0, x2, ? 0, т.е. все решения будут располагаться в I-й четверти.

L1: ? x1 + 3 · x2 = 6 (x1 = 0, x2 = 2; x2 = 3, x1 = 1)

L2: ? x1 + 2 • x2 = 1 (x1 = 3, x2 = 2; x2 = 5, x1 = 9)

L3: x1 + x2 = 5 (x1 = 0, x2 = 5; x2 = 3, x1 = 2)

L4: 3 • x1 ? x2 = 6 (x1 = 2, x2 = 0; x2 = 3, x1 = 3)

Прямые L1, L2, L3, L4 образуют многоугольник ABCED, который является границей множества планов. Линейная функция достигает своего минимального (максимального) значения в угловой точке (вершине) многогранника решений. Требуется найти минимум функции Z на многоугольнике допустимых планов. (Замечание: построив область АВCED, закрасим ее для выразительности каким-либо цветом)

Направление возрастания функции нескольких переменных ( в данном случае - двух) указывает вектор-градиент: grad Z, компонентами которого являются частные производные от функции Z по x1 и x2. Целевая функция:

Z = ? x1 + 2 • x2 >

? Z / ? x1 = ?1; ? Z / ? x2 = 2. То есть, grad Z = n = {?1; 2}

Изобразим вектор n на графике. Строим прямую нулевого уровня функции Z:

Z = ? x1 + 2 • x2 = 0 (x1 = 0, x2 = 0; x1 = 4, x2 = 2)

(Она образует на плоскости семейство параллельных прямых, на каждой их которых функция Z принимает постоянное значение. И вектор n - это вектор нормали к прямой нулевого уровня.)

Для нахождения оптимального плана будем «передвигать» линию нулевого уровня функции Z (x1, x2 ) параллельно самой себе в направлении, указанном вектором grad Z до точки ее «первой встречи» с многоугольником ABCED, которая и является оптимальным планом задачи. Здесь это точка D пересечения прямых L2, L4:

L2: ? x1 + 2 • x2 = 1

L4: 3 • x1 ? x2 = 6

Решая систему этих двух уравнений находим координаты точки D:

D (2,6; 1,8), то есть x*1 = 2,6 и x*2 = 1,8

Таким образом, минимум функции:

Z min = ? x*1 + 2 • x*2 = ? 2,6+ 2 • 1,8 = 1

3) РЕШЕНИЕ ЗАДАЧИ С ПОМОЩЬЮ ПАКЕТА MS EXCEL И НАДСТРОЙКИ «ПОИСК РЕШЕНИЯ»

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

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

Алгоритмы симплексного метода и метода «branch-and-bound» для решения линейных и целочисленных задач с ограничениями разработаны Джоном Уотсоном (John Watson) и Деном Филстра (Dan Fylstra) из Frontline Systems, Inc.

Подготовка приложения и решение:

Переменные
x1	x2
2,6	1,8
Функция цели		1

3) СИМПЛЕКС - МЕТОД

Идея симплекс-метода заключается в последовательном улучшении первоначального плана путем упорядоченного перехода от одного опорного плана к другому и завершается нахождением оптимального плана. Симплекс-методом решаются только канонические задачи линейного программирования. Решение канонической задачи существенно облегчается применением так называемых симплекс-таблиц. Всякую каноническую задачу можно написать условно в виде таблицы. Таблица заполняется следующим образом: первые m строк содержат в условной форме уравнения системы ограничений, разрешенные относительно базисных переменных. В последней строке записана целевая функция, эта строка называется L - строкой. В столбцах записаны свободные переменные и свободные члены.

Условие оптимальности плана: ЗЛП на максимум, то в L - строке не должно быть отрицательных элементов, если ЗЛП на минимум, то в L - строке не должно быть положительных элементов.

1). Исходную ЗЛП приводим к каноническому виду путем введения базисных переменных. Для этого в системе (1) знаки неравенства заменим на знаки равенства. При этом, если знак неравенства ?, то в левой части неравенства необходимо добавить неотрицательную переменную xi, если знак ?, то в левой части неравенства необходимо вычесть некоторую неотрицательную величину xj . В результате преобразований будем иметь:

Z = б · x1 + в · x2 > min Z = ? x1 + 2 • x2 > min

a1 · x1 + b1 · x2 + x3 = c1 x1 + 3 · x2 ? x3 = 6

a2 · x1 + b2 · x2 + x4 = c2 ? x1 + 2 • x2 + x4 = 1

a3 · x1 + b3 · x2 + x5 = c3 x1 + x2 + x5 = 5

a4 · x1 + b4 · x2 + x6 = c4 3 • x1 ? x2 ? x6 = 6

x1 ? 0, x2, ? 0, x3 ? 0, x4, ? 0, x5 , x6 ? 0

Переменные x1, x2 будем считать свободными, а переменные x3 , x4, x5 - базисными.

2) Базисные переменные выражаем через свободные:

x3 = ? 6 + x1 + 3 · x2

x4 = 1 + x1 ? 2 • x2

x5 = 5 - x1 ? x2

x6 = ? 6 + 3 • x1 ? x2

3) Строим начальный план, полагая свободные переменные равными нулю, тогда базисные переменные будут равны свободным членам: X0 = (0; 0; ? 6; 1; 5; ? 6)

4) Строим первую симплекс-таблицу

Св. пер.	- x 1	- x 2	Свободные члены (c I )	Симплексные отношения
Баз. пер.
x 3	- 1	- 3	? 6	6
x 4	- 1	2	1	-1
x 5	1	1	5	5
x6	- 3	1	? 6	2= min (+)
L - строка	1 Max (+)	- 2	0

5). Проверяем план на оптимальность. Задача на минимум, т.е. если в L - строке есть положительные члены, то план не оптимален. Улучшаем план.

6. Улучшение плана. Строим вторую симплекс-таблицу, элементы которой пересчитываем по соответствующим формулам.

а) выбор разрешающего столбца (отмечен вертикальной стрелкой): для этого в L - строке выбираем максимальный по абсолютной величине из отрицательных элементов, если задача на максимум, или, максимальный из положительных элементов, если задача на минимум. Пусть это будет столбец с номером s;

б) выбор разрешающей строки (отмечена горизонтальной стрелкой): выбираем строку с минимальным симплексным отношением (это отношение свободных членов к положительным элементам разрешающего столбца) Пусть это будет строка с номером r;

в) выбор разрешающего элемента (отмечен кружком или цветом): элемент стоящий на пересечении разрешающих строки и столбца. Пусть это будет элемент a rs

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

Из базиса новой симплекс-таблицы выводим переменную x3 и вводим переменную x1 (это так для данного случая!).

г) Новая таблица:

· элемент ведущей ячейки делим на ведущий элемент;

· элементы ведущей строки делим на ведущий элемент; К КАЖДОЙ ИЗ ОСТАЛЬНЫХ СТРОК ПРИБАВЛЯЕМ ВНОВЬ ПОЛУЧЕННУЮ, УМНОЖЕННУЮ НА ТАКОЕ ЧИСЛО, ЧТОБЫ В КЛЕТКАХ ДЛЯ ВЕДУЩЕГО СТОЛБЦА ПРЕДЫДУЩЕЙ СИМПЛЕКС-ТАБЛИЦЫ ПОЯВИЛИСЬ НУЛИ, И ПИШЕМ ПРЕОБРАЗОВАННЫЕ СТРОКИ НА МЕСТО ПРЕЖНИХ ! или делаем как ниже:

· элементы ведущего столбца делим на ведущий элемент, умноженный на (-1);

· остальные элементы пересчитываем по правилу прямоугольника:

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

Св. пер.	? x 6	? x 2	Свободные члены (c I )	Симплексные отношения
Баз. пер.
x 3	0	- 2	? 12
x4	0	4	- 5
x 5	0	0	11
x1	- 1/3	- 1/3	2
L - строка	0	- 3	6
Св. пер.	? x 6	? x 2	Свободные члены (c I )	Симплексные отношения
Баз. пер.
x 3	1/3	- 8/3	? 6
x4	1/3	5/3	1
x 5	-1/3	2/3	5
x1	- 1/3	- 1/3	2
L - строка	-1/3	- 5/3	0

В L-строке нет положительных элементов, но мы не можем принять получаемый план, так как не перенесена в базисные переменная x2, поэтому в качестве решения принимаем результат, полученный графическим методом и проверенный методом «Поиск решения».

Ответ: X*1 = 2,6 и X*2 = 1,8; Z min = 1

Задание 4

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

a1 + b1 • x1 + c1 • x12 д.е., а при изготовлении x2 изделий вторым способом они составляют a2 + b2 • x2 + c2 • x22 д.е. Определить, сколько изделий каждым из способов следует изготовить так, чтобы общие затраты на производство продукции были минимальными.

Решить задачу:

a) графическим способом;

b) используя метод множителей Лагранжа.

N	a1	b1	c1	a2	b2	c2
32	8	4	4	3	20	6

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

Математическая постановка задачи состоит в определении минимального значения функции f (x) = (x1, x2, …, xn). Здесь:

f (x) = a1 + b1 • x1 + c1 • x12 + a2 + b2 • x2 + c2 • x22 = 8 + 4 • x1 + 4 • x12 + 3 + 20 • x2 + 6 • x22 =

При условиях:

qi (x1, x2, …, xn) = bi (i = 1,…, m)

x1 + x2 = N = 32; x1 , x2 ? 0

1) Сначала найдем решение задачи, используя ее геометрическую интерпретацию (графическим способом). Областью допустимых решений исходной задачи является отрезок прямой АВ: x1 + x2 = N = 32, а линиями уровня - эллипсы с центром в точке E(? 1/2; ? 5/3).

(Линией уровня называется прямая, на которой целевая функция Z(X) задачи принимает постоянное значение. Уравнение линии уровня в данном случае имеет вид: f(x)=(x1, x2, …, xn)=const. Все линии уровня параллельны между собой. Полагаем: f (x) = 8 + 4 • x1 + 4 • x12 + 3 + 20 • x2 + 6 • x22 = 0 (линия нулевого уровня). Переписываем f(x) в виде: f(x)=4 • [x1 + (1/2)]2 + 6 • [x2 + (5/3)]2 ? (20/3) = 0 (то есть, выделяем полные квадраты) и получаем: f(x)=4 • [x1 + (1/2)]2 + 6 • [x2 + (5/3)]2 = (20/3) или:



или:

(*)

То есть получили эллипс с центром в точке E (? 1/2; ? 5/3) и полуосями:

a = - большая полуось; ? малая полуось.)

Проводя из точки Е эллипсы с разными полуосями, видим, что минимальное значение целевая функция принимает в точке D. Чтобы найти координаты этой точки, воспользуемся тем, что угловой коэффициент к эллипсу f (x)=4 • [x1 + (1/2)]2 + 6 • [x2 + (5/3)]2 ? (20/3) = Const в точке D совпадает с угловым коэффициентом прямой x1+ x2 = N = 32, и, следовательно, равен ? 1. Рассматривая х2 как неявную функцию от х1 и дифференцируя уравнение эллипса, имеем:

Приравнивая полученное выражение числу ?1, получаем одно из уравнений для определения координат точки D. Присоединяя к нему уравнение прямой, на которой лежит точка D, имеем систему:

2 • x1 ? 3 • x2 = 4,

x1 + x2 = 32,

откуда x1* = 20; x2* = 12.

Это означает, что если фирма изготовит 20 изделий 1-м технологическим способом и 12 изделия 2-м способом, то общие затраты будут минимальными и составят :

f (x) = 8 + 4 • 20 + 4 • 202 + 3 + 20 • 12 + 6 • 122 = 2795 (д.е)

2) Решим задачу, используя метод множителей Лагранжа.

Найдем минимальное значение функции f(x) при условии x1+x2 = N = 32, то есть без учета требования неотрицательности переменных. Для этого введем набор переменных л1, л2, …, лm, называемых множителями Лагранжа и составим функцию Лагранжа:

F(x1, x2, …, xn, л1, л2, …, лm= f (x1, x2, …, xn) +

В нашем случае функция Лагранжа принимает вид:

F(x) = 4 • x1 + 4 • x12 + 20 • x2 + 6 • x22 + 11 + л • (32 ? x1 ? x2)

Найдем частные производные

(j = 1, …, n) и (i = 1, …, m)

И приравняем их нулю (необходимое условие экстремума). Получим систему n+m уравнений:

(j = 1, …, n)

(i = 1, …, m)

с n+m неизвестными x1, x2, …, xn, л1, л2, …, лm. Всякое решение данной системы уравнений определяет точку X=( x1* x2* …, xn*), в которой может иметь место экстремум функции f (x1, x2, …, xn).

Вычисляем частные производные функции Лагранжа по x1, x2, л1 и приравниваем их к нулю: {F(x)=4•x1 + 4•x12 +20•x2 + 6•x22 + 11 + л • (32 ? x1 ? x2)}

, ,

Перенося в правые части первых двух уравнений л, и приравнивая их левые части, получим: 4 + 8 • x1 = 20 + 12 • x2, или 2 • x1 ? 3 • x2 = 4.

Решая последнее уравнение совместно с уравнением x1 + x2 = 32, находим: x1* = 20 и x2* = 12, то есть получили координаты точки D, удовлетворяющей условиям неотрицательности переменных. Эта точка является подозрительной на экстремум.

Найдем достаточное условие экстремума функции двух переменных х1 и х2. Пусть в точке D0 (x1*, x2*) возможного экстремума и некоторой ее окрестности функция f (x1, x2) имеет частные производные второго порядка. Положим

, где

Тогда:

а) если то в точке D0 функция имеет локальный экстремум, причем при а11 < 0 - локальный максимум, при а11 > 0 - локальный минимум;

b) если то в точке D0 экстремума не существует;

c) если то в точке D0 функция может иметь экстремум, но может и не иметь его (необходимо дальнейшее исследование).

Найдем вторые частные производные как

{;}:



Тогда

а11 > 0. Отсюда следует, что в точке D функция имеет условный минимум. Этот результат и был получен выше при решении задачи графическим способом.

Следует отметить, что такой же результат мы получим и в том случае, если исследование на условный экстремум функции f(x) сведем к исследованию на безусловный экстремум функции f1(x), полученной из f(x) в результате ее преобразований. А именно: из уравнения связи x1 + x2 = 32 найдем x2 = 32 ? x1 и подставим в выражение для функции f(x), то получим функцию одной переменной х1:

f1 (x) = 8+4•x1 +4•x12 +3+20•x2 +6•x22 = 11 + 4 • x1 + 4 • x12 + 20 • (32 ? x1) + 6 • (32 ? x1)2

Найдем стационарную точку этой функции из уравнения , отсюда x1* = 20; x2* = 12. Так же, как и выше, устанавливаем, что в данной точке функция имеет минимальное значение. (Действительно,

Задание 5

В хозяйстве имеются четыре марки тракторов А1, А2, А3, А4, с помощью которых требуется в определенные агротехнические сроки выполнить работу в трех отделениях хозяйства В1, В2, В3, отличающихся условиями производства работ. Например, по твердости и влажности почвы, по условиям снабжения горюче-смазочными материалами и так далее. Тракторы каждой из четырех марок могут выполнить работу объемом а1=400, а2=550, а3=700, а4=350. На каждом из трех отделений хозяйств требуется выполнить работу объемом b1=500, b2=850, b3=600 условных гектаров соответственно. Расходы на выполнение работ каждой маркой тракторов на каждом отделении в рублях на гектар составляют cij, где i = 1,2,3, j = 1,2,3,4.

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

Решение:

I) Математическая модель.

Условием задана классическая ТЗ.

Здесь известен транспортный тариф cij ? (dij ) - «транспортный тариф» (условное понимание стоимости единицы груза - себестоимость, расстояние, тариф, время, расход топлива или электроэнергии и др.), xij - количество груза, которое поставщик Ai (i = 1, …, m) отправляет потребителю Bj (j = 1, …, n). Предполагается, что суммарные запасы груза у поставщиков равны суммарным потребностям потребителей:

? ai= ? bj

Это условие называется условием баланса. Если для ТЗ условие баланса выполняется, то модель ТЗ называется закрытой. Если нет - модель ТЗ открытая. При выполнении условия баланса ТЗ всегда имеет решение.

По своему смыслу величины xij должны удовлетворять следующим ограничениям:

· из пункта Ai все запасы должны быть вывезены (ограничение по ресурсам):

? xij = ai (i = 1, …, m);

· заявки потребителей Bi должны быть выполнены (ограничение по потребностям):

? xij = bj (j = 1, …, n).

Затраты на перевозку xij единиц груза из пункта поставки Ai в пункт потребления Bj составляют сij • xij единиц; общие затраты всех перевозок xij равны сумме всех таких затрат: L = ? ? сij • xij > min.

Таким образом, математическая модель ТЗ имеет вид:

m n

L = ? ? сij • xij > min

i j

? xij = ai (i = 1, …, m)

? xij = bj (j = 1, …, n).

xij ? 0 i = 1, …, m, j = 1, …, n

Данные ТЗ можно представить в виде таблицы:

Марки тракторов	Отделения	Запасы (возможности)
	В1	В2	В3
А1	d11 x11	d12 x12	d13 x13	a1
А2	d21 x21	d22 x22	d23 x23	a2
А3	d31 x31	d32 x32	d33 x33	a3
А4	d41 x41	d42 x42	d43 x43	a2
Потребности (требуемый объем работ)	b1	b2	b3	? ai= ? bj (условие баланса для закрытой модели)

Процедура решения ТЗ в построении опорных планов (опорный план - план, удовлетворяющий системе ограничений и условию неотрицательности), их последовательном улучшении и проверки на оптимальность.

Существует несколько методов построения первоначального опорного плана ТЗ. В данной задаче мы используем только два: метод северо-западного угла и метод наименьшей стоимости. Затем выбираем лучший план.

II) Метод северо-западного угла. Назначение перевозок назначаем с левой верхней клетки (северо-западный угол). Сравнивая ресурсы поставщика и потребности потребителя, назначаем максимально возможную перевозку. Если ресурсов поставщика недостаточно, то переходим к следующему поставщику. Если ресурсов у поставщика достаточно, то назначив нужную перевозку первому потребителю, переходим к следующему потребителю.

Марки тракторов	Отделения	Запасы (возможности)
	В1	В2	В3
А1	d11=5 x11=100	d12=2 x12=	d13=8 x13=	a1=100 100.0.K
А2	d21=1 x21=50	d22=3 x22=	d23=5 x23=	a2=50 50.0.K
А3	d31=3 x31=50	d32=4 x32=100	d33=1 x33=	a3=150 150.100.0.K
А4	d41=4 x41=	d42=8 x42=50	d43=6 x43=50	a2=100 100.50.0.K
Потребности (требуемый объем работ)	b1=200 200.100.50.0 K	b2=150 150.50.0.K	b3=50 50.0.K	? ai= ? bj (условие баланса для закрытой модели)

При назначении перевозок для удобства записываем остаток ресурсов (потребностей); если ресурсы закончились или потребности удовлетворены, то ставим букву «К» (конец). Если при назначении перевозки одновременно закончились запасы ресурсов у поставщика и удовлетворены потребности потребителя, то из «игры» выводим только одного участника, другому оставляем нуль запасов или нуль потребностей.

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

В опорном плане число назначенных перевозок должно быть равно

m + n ?1, где:

m - число поставщиков A i (i = 1,…, m)

n - число потребителей B j (j = 1,…, n)

В опорном плане должно быть не более r = m + n - 1 переменных Xij, отличных от нуля. Если таких переменных r, то такой план называют невырожденным, в противном случае - вырожденным.

В данном случае число назначенных перевозок m + n - 1 = 3 + 5 -1 = 7, а число r = 7, т.е. начальный план x11=100; x21=50; x31= 50; x32=100; x42=50; x43=50 - - невырожденный. (При этом условие баланса ? ai= ? bj (400= 400) выполняется, т.е. модель ТЗ - закрытая.). При таком плане суммарные расходы на производство работ, производимых во всех отделениях, равны:

L = d11 · x11 + d21 · x21 + d31 · x31 + d32 · x32 + d42 · x42 + d43 · x43 = 5 · 100 + 1 · 50 + 3 · 50 + 4 · 100 + 8 · 50 + 6 · 50 = 500 + 50 + 150 + 400 + 400 + 300 = 3 800 (руб.)

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

Марки тракторов	Отделения	Запасы (возможности)
	В1	В2	В3
А1	d11=5 x11=	d12=2 x12=100	d13=8 x13=	a1=100 100.0.K
А2	d21=1 x21=50	d22=3 x22=	d23=5 x23=	a2=50 50.0.K
А3	d31=3 x31=150	d32=4 x32=	d33=1 x33=	a3=150 150.0.K
А4	d41=4 x41=	d42=8 x42=50	d43=6 x43=50	a2=100 100.50.0.K
Потребности (требуемый объем работ)	b1=200 200.150.0 K	b2=150 150.50.0.K	b3=50 50.0.K	? ai= ? bj (условие баланса для закрытой модели)

Начальный план:

x21, x31, x12, x42, x43

При таком начальном плане транспортные издержки:

L = d21 · x21 + d31 · x31 + d12 · x12 + d42 · x42 + d43 · x43 = 1 · 50 + 3 · 150 + 2 · 100 + 8 · 50 + 6 · 50 = 50 + 450 + 200 + 400 + 300 = 1200 (руб.)

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

IV) Метод потенциалов. Потенциалами называются условные числа ui и vj приписанные определенным образом каждому поставщику и потребителю.

Условие оптимальности плана:

Сумма потенциалов поставщика и потребителя равна тарифной ставке для занятых клеток; сумма потенциалов поставщика и потребителя не превышает тарифную ставку для свободных клеток:

ui + vj = cij (здесь: cij ? dij ), xij ? 0

ui + vj = cij (здесь: cij ? dij ), xij = 0

Опорный план должен быть невырожденным.

1). Рассмотрим начальный план, полученный методом наименьшей стоимости (как лучший).

2). Рассмотрим потенциалы поставщиков и потребителей, используя первое условие оптимальности плана: ui + vj = cij

Используя первое условие оптимальности плана, составим систему линейных уравнений для определения потенциалов:

u1 + v2 = 2

u2 + v1 = 1

u3 + v1 = 3

u4 + v2 = 8

u4 + v3 = 6

Система уравнений содержит 5 уравнений и 6 неизвестных, т.е. она имеет множество решений. Так как нужно одно решение, то любой из неизвестных задаем значение и вычисляем остальные неизвестные. Пусть u1 = 0, тогда

V2 = 5, v2 = 2, v1 = 0, u2 = 1, u3 = -2, u4 = 3, v3 = 3

3) Проверяем условие оптимальности для свободных клеток. При невыполнении второго условия оптимальности плана в клетку заносим нарушение ui + vj - cij со знаком «+». (такие клетки называются потенциальными.). В результате проверки получили одну потенциальную клетку. Таким образом, начальный план не оптимален.

V j Поставщики	0	5	3
U i Потребители	В1	В2	В3
0	А1	d11=5		d13=8
1	А2	_	d22=3 +3 +	d23=5
-2	А3		d32=4	d33=1
3	А4	d41=4 +	_

4) Улучшение плана.

· среди все потенциальных клеток выбираем клетку с наибольшим нарушением;

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

· вершины контура поочередно помечаем знаками “+” и “- “, начиная с клетки, для которой построен контур;

· среди клеток, помеченных знаком “-“ , выбираем наименьшую перевозку.

Здесь: q = min (100; 50) = 50.

На эту величину увеличиваем перевозки в клетках, помеченных знаком “+”, и уменьшаем в клетках, помеченных знаком “-“.

В результате переназначения освобождается одна клетка и имеем план:.

Марки тракторов	Отделения	Запасы (возможности)
	В1	В2	В3
А1	d11=5 x11=	d12=2 x12=100	d13=8 x13=	a1=100 100.0.K
А2	d21=1 x21=	d22=3 x22=50	d23=5 x23=	a2=50 50.0.K
А3	d31=3 x31=150	d32=4 x32=	d33=1 x33=	a3=150 150.0.K
А4	d41=4 x41=50	d42=8 x42=	d43=6 x43=50	a2=100 100.50.0.K
Потребности (требуемый объем работ)	b1=200 200.150.0 K	b2=150 150.50.0.K	b3=50 50.0.K	? ai= ? bj (условие баланса для закрытой модели)

5). Вновь полученный план проверяем на оптимальность.

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

x12, x22, x31, x41, x43

При таком начальном плане суммарные расходы:

L = 2 · 100 + 3 · 50 + 3 · 150 + 4 · 50 + 6 · 50 = 200 +<...