Методы оптимизации в технико-экономических задачах
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
?аем коэффициенты таблицы, для чего воспользуемся правилами перехода от одной симплекс-таблицы к другой, которые были описаны в предыдущем разделе.
Свободные БазисныеX1X3 X5Свободные членыX2-0,59-0,88-0,240,95X4-0,038950,0210,009750,0115f-15,465425,396,7256-29,03
Проанализируем полученную симплекс-таблицу. Нижняя строка таблицы, соответствующая целевой функции, содержит отрицательный коэффициент перед x1, значит минимум функции не может быть достигнут, поскольку можно до некоторого предела увеличивать эти переменные. Значит, необходима замена базиса.
Выясним, до какого предела можно увеличивать x1:
из второго уравнения следует ограничение: x1 =0,38;
Теперь посчитаем, насколько переменная уменьшает целевую функцию, для чего подставим максимально допустимое значение в выражение для целевой функции, а остальные переменные зададим равными нулю:
1=-12,53;
То есть целесообразно ввести в базис x1, тогда x4 выводим из базиса.
Следующий шаг - составление новой симплекс-таблицы. В ней x1, x2 будут базисными переменными, а x3, x4, x5 - свободными. Пересчитаем коэффициенты таблицы, для чего воспользуемся правилами перехода от одной симплекс-таблицы к другой, которые были описаны в предыдущем разделе.
Свободные БазисныеX3X4 X5Свободные членыX10,54-25,670,250,295X2-1,198615,15-0,38750,776f17,04396,992,8596-29,17
Проанализируем полученную симплекс-таблицу. Нижняя строка таблицы, соответствующая целевой функции, не содержит отрицательных коэффициентов, значит, максимум функции достигнут. Найденное решение является оптимальным и Fmax=33,605
Следовательно, наиболее выгодная смесь сортов углей это 0,295 единиц сорта A и 0,776 единиц сорта B, сорт C покупать не выгодно.
3. Задача оптимального распределения перевозок
.1 Теоретическая часть
Разновидностью задачи линейного программирования, записанной сразу в канонической форме, является транспортная задача.
В типичной транспортной задаче предполагается наличие некоторого количества пунктов отправления А1, А2, … , Аm (это могут быть склады, базы, хранилища и др.) и некоторого количества пунктов назначения В1, В2, … , Вn (это могут быть фабрики, магазины и др.).
Задаётся количество груза, которое должно быть вывезено из каждого пункта отправления, а также количество груза, которое должно быть доставлено в каждый пункт назначения. Ещё задаётся некоторая величина, определяющая стоимость перевозки (или эквивалентная ей характеристика перевозки) из пункта Оi, в пункт Нj. Если в качестве критерия оптимальности взять минимальную стоимость перевозок всего груза, то
cij - стоимость перевозки единицы груза из i-го пункта отправления в j-ый пункт назначения;
ai - запасы груза в i-ом пункте отправления;
bj - потребности в грузе в j-ом пункте назначения;
xij - количество единиц груза, перевозимого из i-ого пункта отправления в j-ый пункт назначения.
Обычно транспортная задача бывает закрытой (суммарная потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления), то есть
Иногда данное равенство не выполняется, тогда модель транспортной задачи открытая.
В случае, если запасы груза превышают потребность в них, то есть , то вводится фиктивный(n+1)-ый пункт назначения с потребностью bn+1=и стоимостью перевозки единицы груза (или эквивалентной характеристики) принимается равной нулю, то есть сi n+1=0 при i=1..m
В случае, если потребности больше, чем запасы груза, то есть , то вводится фиктивный (m+1)-ый пункт отправления с запасом груза am+1= и стоимость перевозки единицы груза (или эквивалентной характеристики) считаются равными нулю, то есть сm+1 j при j=1..n
Задача состоит в определении такого распределения грузов, при котором суммарная стоимость перевозок была бы минимальной, то есть
> min
Ограничения:
1)наличие в каждом пункте отправления определённого количества товаров:
(i=1..m)
2)потребность у каждого пункта назначения в определённом количестве товаров:
(j=1..n)
3)xij?0 (i=1..m, j=1..n)
Количество переменных хij в задаче с m пунктами отправления и n пунктами назначения равно (m * n), а число уравнений равно (m + n). Для того, чтобы соблюдалось равенство , число линейно независимых уравнений должно быть равно (m + n - 1). Таким образом, базис будет содержать (m + n - 1) неизвестных.
Базис является невырожденным, если в нём число отличных от нуля компонент точно совпадает с (m + n - 1). Если же это число меньше нуля, то базис - вырожденный.
Существует несколько методов определения начального базиса: метод северо-западного угла, метод двойного предпочтения, метод Фогеля и др.
Метод северо-западного угла является одним из наиболее простых и распространенных методов, но он дает самый далекий от оптимального план. В этом случае начинаем заполнять таблицу с крайней левой верхней клетки (C11) наибольшим возможным объемом груза. Затем вычеркиваем соответствующую строку или столбец и заполняем ставшую крайней левой верхней свободную клетку (т.е. C12 или C21). Продолжаем до тех пор, пока полностью не определим начальный базис.
В методе двойного предпочтения следует в каждой строке отметить галочкой клетку с наименьшим тарифом, затем то же сделать для каждого столбца. Далее выбираем клетку, в которой находятся две галочки, если таких клеток оказалось несколько, то выбираем ту, у которой наименьший тариф. В эту клетку записывается максимально возможное значение. Максимально возможное значение будет равно минимальному из чисел ai и bj. Дале