Транспортная задача и задача об использовании сырья
1. Решить задачу об использовании сырья геометрическим способом и симплекс методом, дать экономическую интерпретацию.
Геометрический способ.
Пусть  количество выпускаемой продукции первого вида, тогда  количество выпускаемой продукции второго вида. Прибыль от реализации всей продукции составляет  .
Цель задачи (максимализация прибыли) запишется в виде
 
Структура всех трёх ограничений одинакова 
Перейдём из неравенств к уравнениям
Построим прямые на плоскости 
Многоугольник решений  . Для нахождения максимума функции построим начальную прямую  и вектор  . Передвигая прямую вдоль вектора  получим, что максимальное значение наша прямая принимает в точке  точке пересечения прямых  и  .
 .
Симплекс метод.
Приведём систему неравенств к системе уравнений
Целевая функция – функция прибыли
Составим симплекс таблицу:
- Первое ограничение запишем в первую строку
- Второе ограничение запишем во вторую строку
- Третье ограничение запишем в третью строку
Целевую функцию запишем в  строку
| Б |
З |
 |
 |
 |
 |
 |
|
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 |
Определим значение целевой функции
Проверим оптимальность плана
  
Подсчитаем оценки свободных клеток
План близок к оптимальному.
При дальнейшем перераспределении груза, задача входит в циклическую фазу, план не улучшается. Таким образом, полученное решение является наиболее оптимальным для нашей задачи
|
