бесплатные рефераты

Транспортная задача и задача об использовании сырья

Транспортная задача и задача об использовании сырья

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

 

75

5

3

83

4

7

50

1

5

4

5

 

Геометрический способ.

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

Цель задачи (максимализация прибыли) запишется в виде

 Транспортная задача и задача об использовании сырья  Транспортная задача и задача об использовании сырья

Структура всех трёх ограничений одинакова                                      Транспортная задача и задача об использовании сырья

 Транспортная задача и задача об использовании сырья

   Транспортная задача и задача об использовании сырья

Перейдём из неравенств к уравнениям

 Транспортная задача и задача об использовании сырья

Построим прямые на плоскости  Транспортная задача и задача об использовании сырья

 Транспортная задача и задача об использовании сырья

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

 Транспортная задача и задача об использовании сырья

 Транспортная задача и задача об использовании сырья .

Симплекс метод.

Приведём систему неравенств к системе уравнений

 Транспортная задача и задача об использовании сырья

Целевая функция – функция прибыли

 Транспортная задача и задача об использовании сырья

Составим симплекс таблицу:

   - Первое ограничение запишем в первую строку

   - Второе ограничение запишем во вторую строку

   - Третье ограничение запишем в третью строку

Целевую функцию запишем в  Транспортная задача и задача об использовании сырья  строку

 

Б

З

75

5

3

1

0

0

83

4

7

0

1

0

50

1

5

0

0

1

0

0

0

0

 

В строке  Транспортная задача и задача об использовании сырья  есть отрицательные  Транспортная задача и задача об использовании сырья  начальный план не оптимален. Найдём наименьший отрицательный элемент строки  Транспортная задача и задача об использовании сырья  Транспортная задача и задача об использовании сырья . Переменная  Транспортная задача и задача об использовании сырья  будет включена в базис. Столбец переменной  – ведущий.  Подсчитаем симплексные отношения и найдём среди них минимальное  Транспортная задача и задача об использовании сырья  третья строка ведущая, а элемент  разрешающий. Следовательно переменная  Транспортная задача и задача об использовании сырья  выйдет из базиса.

Проведём одну интеракцию метода замещения Жордано-Гаусса. Столбцы. Разрешающий элемент

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

 

Б

З

45

0

1

0

13

 Транспортная задача и задача об использовании сырья

0

0

1

10

1

0

0

50

0

0

0

1

 

В строке  Транспортная задача и задача об использовании сырья  есть отрицательные  Транспортная задача и задача об использовании сырья  план не оптимальный. Рассчитаем симплексные отношения и найдём среди них минимальное  Транспортная задача и задача об использовании сырья  вторая строка ведущая  разрешающий

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

 

Б

З

23

0

0

1

 Транспортная задача и задача об использовании сырья

5

1

0

0

9

0

1

0

65

0

0

0

 

 

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

 

Б

З

13

0

0

1

12

1

0

0

5

0

1

0

73

0

0

0

 

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

 Транспортная задача и задача об использовании сырья

 Транспортная задача и задача об использовании сырья

Оптимальный план найденный геометрическим способом и симплексным методом совпадают. Предприятию необходимо выпускать 12 единиц продукции первого вида и 5 единиц продукции второго вида. В этом случае предприятие получит прибыль  Транспортная задача и задача об использовании сырья  денежных единиц.

 

 

2. Решить транспортную задачу распределительным методом, оценивая свободные клетки по методу потенциалов.

 

 Транспортная задача и задача об использовании сырья        Транспортная задача и задача об использовании сырья

 

     Транспортная задача и задача об использовании сырья

 

60

 

50

 

85

 

75

65

8

10

6

5

65

80

4

30

3

50

5

9

35

11

25

4

4

8

10

90

5

5

5

3

85

6

 

Проверим необходимое и достаточное условие разрешимости задачи

 Транспортная задача и задача об использовании сырья

 Транспортная задача и задача об использовании сырья

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

Используя метод наименьшей стоимости заполним таблицу.

Среди тарифов наилучшим является  Транспортная задача и задача об использовании сырья  и  Транспортная задача и задача об использовании сырья . Направим например,

в клетку  Транспортная задача и задача об использовании сырья  

в клетку  Транспортная задача и задача об использовании сырья

в клетку  Транспортная задача и задача об использовании сырья

в клетку  Транспортная задача и задача об использовании сырья

в клетку  Транспортная задача и задача об использовании сырья

в клетку  Транспортная задача и задача об использовании сырья

в клетку  Транспортная задача и задача об использовании сырья

Запасы поставщиков исчерпаны, запросы потребителей удовлетворены полностью. В результате получили первый опорный план. Подсчитаем число занятых клеток таблицы их 7, а должно быть  Транспортная задача и задача об использовании сырья  опорный план не вырожденный.

Определим значение целевой функции первого опорного плана

 Транспортная задача и задача об использовании сырья

Проверим оптимальность плана.

Найдём потенциалы  Транспортная задача и задача об использовании сырья  и  Транспортная задача и задача об использовании сырья  по занятым клеткам таблицы

 Транспортная задача и задача об использовании сырья

Пусть  Транспортная задача и задача об использовании сырья , тогда:

 Транспортная задача и задача об использовании сырья

Подсчитаем оценки свободных клеток  Транспортная задача и задача об использовании сырья

 Транспортная задача и задача об использовании сырья

 Транспортная задача и задача об использовании сырья

 Транспортная задача и задача об использовании сырья

 Транспортная задача и задача об использовании сырья

 Транспортная задача и задача об использовании сырья

Первый опорный план не является оптимальным так как .

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

 Транспортная задача и задача об использовании сырья

В результате получили новый опорный план

 

       Транспортная задача и задача об использовании сырья  Транспортная задача и задача об использовании сырья

 

     Транспортная задача и задача об использовании сырья

 

60

 

50

 

85

 

75

65

8

10

6

5

65

80

4

55

3

25

5

9

35

11

 

4

25

4

8

10

90

5

5

5

3

85

6

 

Определим значение целевой функции

 Транспортная задача и задача об использовании сырья

Проверим оптимальность плана

 Транспортная задача и задача об использовании сырья           Транспортная задача и задача об использовании сырья           

Подсчитаем оценки свободных клеток

 Транспортная задача и задача об использовании сырья

 Транспортная задача и задача об использовании сырья

 Транспортная задача и задача об использовании сырья

 Транспортная задача и задача об использовании сырья

 Транспортная задача и задача об использовании сырья

План близок к оптимальному.

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

 

 

 

 

 

 

 

 



© 2010 РЕФЕРАТЫ