КП_Тишинский. 5. Решение задачи линейного программирования вручную 10

• Название: 5. Решение задачи линейного программирования вручную 10
• Анкор: КП_Тишинский.doc
• Дата: 11.04.2018
• Размер: 5.67 Mb.
• Имя файла: КП_Тишинский.doc
• Тип: Решение; #17925
• страница: 5 из 6

Решение задачи линейного программирования симплекс методом

1. 
   Приведем математическую модель задачи представленную в виде уравнений к каноническому виду.
   

Вводим дополнительные переменные: чтобы неравенства

преобразовать в равенства.

Чтобы выбрать начальный базис, вводим искусственные переменные и очень большое число M (M → ∞). Решаем М методом.

2. 
   Заполняем первую симплекс таблицу.
   

Таблица 3 Первая симлекс таблица

Сб	Б	В	4	6	0	0	0	M	M	M	Q
M		9	3	1	-1	0	0	1	0	0
M		10	1	2	0	-1	0	0	1	0
M		8	1	6	0	0	-1	0	0	1
L		Z
∆

При расчёте опорного плана используем M=1000.
;

3. 
   Рассчитываем опорный план таблицы.
   

; ; ; ; ; ; ; ; ;

Поскольку есть положительные значения ∆, то план не оптимален.

4. 
   Находим разрешающий элемент таблицы №1
   

Рисунок 5 12 Таблица №1 (нулевой шаг)

Разрешающая строка Разрешающий столбец

Разрешающий элемент

Максимальное положительное значение имеет =8994, следовательно, столбец - Разрешающий. Найдём разрешающую строку, выделив наименьший положительный элемент Q.









На пересечение разрешающего столбца и строки получаем разрешающий элемент = 6.

5. 
   Заполняем вторую симплекс таблицу.
   
   1. 
      Разрешающую строку делим на разрешающий элемент и записываем на своем месте.
      
   2. 
      Обнуляем остальные элементы разрешающего столбца
      
   3. 
      Оставшиеся элементы таблицы находим по правилу прямоугольника
      где - Разрешающий элемент.
      
      ….
      
   4. 
      Рассчитываем опорный план второй таблицы (аналогично первой).
      

Рисунок 5 13 Таблица №2 (первый шаг)
Поверяем новый план на оптимальность. Так как решение не найдено, возвращаемся к пункту 4.

При использование для расчётов табличного процессора MS Excel, с использованием маркера автозаполнения необходимо ввести следующие формулы

1. 
   Для расчета элементов разрешающей строки «=C5/$E$5». Где:
   С5 – ячейка элемента в предыдущей таблице.
   $E$5 – ячейка разрешающего элемента с абсолютной адресацией
   
2. 
   Для расчёта свободных элементов по правилу прямоугольника
   «=($E$5*E4-E$5*$E4)/$E$5». Где:
   $E$5 – ячейка разрешающего элемента с абсолютной адресацией
   E4 - ячейка элемента в предыдущей таблице
   E$5 – ячейка элемента находящегося в одном столбце с искомым элементом и в одной строке с разрешающим элементом.
   $E4 - ячейка элемента находящегося в одном столбце с разрешающим элементом и в одной строке с искомым элементом.
   

Рисунок 5 14 Решение задачи Симлекс-методом с использованием MS Excel
Опорный план, составленный по последней симплекс-таблице, является оптимальным, т.к. все значения ∆ меньше или равны нулю.

6. 
   Записываем полученный результат в ответ.
   
   Ответ: Оптимальная стоимость дневного рациона составляет 31.6 ден. ед. при приобретении 1.6 кг. корма 1-го вида, и 4.2 кг. корма 2-го вида.