Оптимальное управление в экономике. Матвейкин В.Г - 19 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

требителю (или столбцу) – некоторое число
,
j
v
называемое потенциалом потребителя )1,( n=jB
j
, записы-
вают под таблицей. Числа
ji
vu и
выбирают так, чтобы в любой базисной клетке их сумма равнялась тарифу,
т.е.
. = +
ijji
cvu
Так как количество всех потенциалов
ji
vu и
– составляет m + п, а занятых клеток m + п – 1, то
для определения чисел
ji
vu и
– придется решать систему из m + п – 1 уравнений с m + п неизвестными. По-
этому одному из неизвестных потенциалов придают произвольное значение. Тогда остальные определяются
однозначно.
6. Для проверки оптимальности плана просматривают свободные клетки, для которых определяют оцен-
ки
ij
∆
– разность между тарифом клетки и суммой потенциалов строки и столбца, т.е.
)(
jiijij
vuс +−=∆
. Эко-
номически оценка показывает, на сколько денежных единиц изменятся транспортные издержки от загрузки
данной клетки единицей груза. Если все оценки неотрицательные, т.е.
0≥∆
ij
, то план оптимальный и остается
подсчитать транспортные расходы. Иначе переходят к п. 7.
7. Из отрицательных оценок
)0( ≤∆
ij
выбирают минимальную. Пусть это будет
ik
∆ . Тогда клетку (l, k)
вводят в число базисных, т.е. строят цикл по загруженным клеткам с началом в этой клетке и перераспределяют
поставки так, чтобы баланс цикла сохранился. Для этого вершинам цикла приписывают чередующиеся знаки
"+" и "–" (свободной клетке (l, k) приписывают положительный знак "+"). В "минусовых" клетках отыскивают
наименьший груз w, т.е.
stij
xxw == min , который и "перемещается" по клеткам замкнутого цикла, т.е. прибав-
ляется к перевозкам x
ij
– в клетках со знаком "+" (включая свободную) и вычитается из перевозок x
ij
в клетках
со знаком "–". Следовательно, клетка (s, t) станет свободной и переменная x
st
уйдет из базиса. Значение осталь-
ных базисных переменных переписываются. Таким образом, получают новую транспортную таблицу с улуч-
шенным планом, для которого транспортные издержки изменятся на величину
stlk
x
∆
. Переходят к пункту 4.
Замечания.
1. При сдвиге по циклу вместо одной может освободиться сразу несколько клеток (вырожденная задача).
Свободной оставляют только одну (с наибольшим тарифом), а в остальные освободившиеся клетки вписывают
нули и считают их загруженными.
2. Если все оценки
0>∆
ij
, то оптимальный план единственный. Если существует хотя бы одна оценка
0=∆
ij
, то задача имеет множество оптимальных планов, которое представляет собой выпуклую линейную
комбинацию оптимальных решений. Другие оптимальные планы можно получить, загружая по очереди клетки
с нулевыми оценками.
4. ВАРИАНТЫ КОНТРОЛЬНЫХ РАБОТ
4.1. ЗАДАЧА ОБ ОПТИМАЛЬНОМ РАСПРЕДЕЛЕНИИ
ПРОИЗВОДСТВЕННЫХ РЕСУРСОВ
Условия задачи
Есть три вида станков: А1, А2, А3. На этих станках последовательно обрабатываются детали трех видов:
В1, В2, В3. Известно сколько часов каждая деталь изготавливается на каждом станке, сколько может прорабо-
тать каждый станок и какая прибыль может быть получена при продаже одной детали каждого типа. Данные
приведены в таблице. Требуется найти оптимальный план работы станков, т.е. установить, сколько деталей и
каких видов надо выпустить, чтобы получить максимальную прибыль.
Задание 1: Построить математическую модель задачи; привести математическую модель задачи к кано-
ническому виду; найти начальный опорный план задачи; решить задачу графическим способом; (если это не-
возможно – обосновать почему); решить задачу симплекс методом.

Страницы