Контрольная работа по "Логистике". 17

      Содержание  

      Задача 1 3

      Задача 2 8 

Задача №1 

      Предприятие выпускает два вида продукции и , для производства которых используют три вида сырья . На производство единицы j-го вида продукции требуется единиц i-го вида сырья. Предприятие имеет запасы каждого вида сырья, соответственно, единиц. Прибыль имеет предприятия от реализации единицы j-го вида продукции составляет с_j денежных единиц. Требуется найти план производства х_i единиц первого вида продукции, при котором суммарная выручка предприятия будет наибольшей. С этой целью:

1. Записать задачу линейного программирования
2. Решить е геометрическим способом.
3. Решить ее симплекс-методом.
4. Составить двойственную задачу и решить ее.

      РЕШЕНИЕ:

      1) Запишем данную задачу в форме задачи линейного программирования. Элементами решения будут   - количества единиц изделия , , которые необходимо произвести. Обязательность выполнения задачи запишется ограничений-неравенств: .

      Каждого трех видов сырья должно хватить, отсюда следуют три ограничения-неравенства:

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

      2) Решим эту задачу геометрически:

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

1. - решением этого неравенства является полуплоскость с границей        

точка О(0;0) – принадлежит этой полуплоскости, т.к. ее координаты удовлетворяют (1). 

2. - решением  этого неравенства является полуплоскость с границей

О(0;0) принадлежит  этой полуплоскости, т.к. ее координаты удовлетворяют (2).

3. - полуплоскость с границей  

О(0;0) принадлежит  этой полуплоскости т.к. ее координаты удовлетворяют (3).

4. - первый квадрант.

      Пусть L=0, тогда 

      Вектор  указывает направление увеличения L; в вершине А достигается максимального значения, которое найдем как пересечение прямых.

           А (95;45)

        д.ед.

      3) Решаем симплексным методом задачу.

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

      Функцию L представили в неявном виде:

      Пусть - свободные переменные, а - базисные.

      Пусть , тогда . При этом , т.е. если ни один вид продукции не производится. Все ресурсы остаются неиспользованными, а, следовательно, прибыли нет.

      Для нахождения оптимального решения необходимо одну из базисных переменных превратить в свободную.

      В последней строке таблицы среди  отрицательных значений находим  наибольшее по абсолютной величине (это (-33)). Ведущий столбец соответствует переменной . Делим свободные члены на соответствующие элементы ведущего столбца и среди частных от деления находим минимальное, т.е. .

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

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

      Остальные элементы переписываем по правилу прямоугольника.

        где  - элемент ведущего столбца, стоящий в одной строке с ;

             - элемент ведущей строки, стоящий в одной строке с .

      Получим симплексную таблицу:

      Базисные  переменные: . Свободные переменные: . Прибыль д.ед.

      Полученное  решение не является оптимальным, т.к. в последней строке есть отрицательный элемент.

      Преобразуем аналогично полученную таблицу:

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

      Предприятие получит максимальную прибыль при  выпуске  =95 единицы изделия ; и =45 единиц изделия . При этом ресурсы первого и третьего вида будут использованы полностью . По ресурсу второго вида будет остаток кг. Прибыль предприятия составит: д.ед.

      4) Двойственная задача по отношению к исходной, состоит в следующем.

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

       - функция общих затрат производства. .

      Решение этой задачи можно найти непосредственно  из последней строки симплекс-таблицы, оптимальный для прямой задачи.

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

. 

Ответ. Необходимо выпустить 95 единиц продукции типа и 45 единиц продукции типа для того чтобы получить наибольшую прибыль 4215 денежных единиц.

Задача 2 

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

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

      Решение

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

      Выбираем  северо-западную клетку . На базе имеется 250 т груза, потребность пункта составляет 120 т и может быть удовлетворена базой .

      Исключаем из рассмотрения первый столбец. 

     Исключаем первый столбец. На складе осталось 130т.

     Теперь  северо-западной клеткой является : из перевезем оставшиеся 130 т угля в пункт .

     На  базе больше нет груза, исключаем из рассмотрения первую строку.

      Аналогично  заполняем всю таблицу.

      Транспортные  расходы по этой программе равны:

       д.ед.

     Составим  вспомогательную рабочую матрицу  затрат. Она строится из исходной матрицы издержек путем переноса только тех ячеек p_ij которые соответствуют заполненным клеткам транспортной таблицы. Остальные ячейки остаются пустыми.

     Кроме того, введем вспомогательный столбец, в который внесем значения неизвестных u₁ ... u₃ (3, это m - число складов) и вспомогательную строку, в которую внесем значения неизвестных v₁ ... v₅ (5,это n - число потребителей). На рисунке они представлены желтым цветом. Эти n+m неизвестных должны для всех (i,j), соответствующих загруженым клеткам, удовлетворять линейной системе уравнений u_i+v_j=p_ij

     Эту систему всегда можно решить следующим способом: На первом шаге полагают v₅=0. Если на k-м шаге найдено значение неизвестной, то в системе всегда имеется еще не определенная неизвестная, которая однозначно может быть найдена на (k+1)-м шаге из уравнения u_i+v_j=p_ij, так как значение другой неизвестной в этом уравнении уже известно. То какую неизвестную можно найти на (k+1)-м шаге, определяют методом проб. Переменные u_i и v_j называются симплекс-множителями или потенциалами.

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

     Порядок вычисления потенциалов был следующий:

     1) пусть v₅ = 0;

     2) u₃ = p_3,5 – v₅;

     3) v₄ = p_3,4 - u₃;

     4) v₃= p_3,3 - u₃;

     5) u₂ = p_2,3 - v₃;

     6) v₂ = p_2,2 - u₂;

     7) u₁ = p_1,2 - v₂;

     8) v₁ = p_1,1 - u₁.

     Теперь  для всех свободных клеток рабочей  матрицы затрат вычислим оценки S_ij, по формуле S_ij = p_ij – u_i - v_j. Каждая такая оценка показывает на сколько изменятся общие транспортные затраты при загрузке данной клетки единицей груза. Так как среди оценок имеются отрицательные (затраты уменьшаются), то данный план можно улучшить переместив в соответствующую клетку некоторое количество продукции.

     Из  всех отрицательных оценок имеет  смысл выбрать наибольшую по модулю (-8), так как ее воздействие на общие затраты является максимальным,  она находится в ячейке а₃,b₂, в соответствующую ячейку транспортной таблицы переместим некоторое количество продукции, т.е. загрузить ее. Отметим в транспортной таблице ячейку а₃,b₂ знаком + . Кроме нее мы пометим знаками - и + другие занятые числами ячейки таким образом, что в каждой строке и каждом столбце транспортной таблицы число знаков + будет равно числу знаков - .

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

      Перераспределяем  груз по выбранному циклу:

      Так как есть отрицательные оценки, то план не оптимален.

      Перераспределим груз по циклу клетки а₃b₃: