Урок 3. Решение задачи линейного программирование в Excel симплекс-методом

Статья с подробным разбором.

Математическая модель
Каноническая форма задачи линейного программирования
Решение с помощью симплекс-таблиц в Excel
Видео

Математическая модель
Модель задачи из урока 1:
Целевая функция запишется в виде:
f = 4Х₁ + 2Х₂ +4Х₃ + 3Х₄ (мах)
Система ограничений на ресурсы:
10Х₁ + 20Х₂ +15Х₃+18Х₄≤250
0Х₁ + 5Х₂ + 8Х₃+ 7Х₄≤40
15Х₁ + 18Х₂ +12Х₃+ 20Х₄≤100
8Х₁ + 12Х₂ + 11Х₃+ 10Х₄≤80
Условия не отрицательности:
Х_j≥0 (j=1,4)

Каноническая форма задачи линейного программирования
Необходимо систему ограничительных неравенств модели привести к канонической форме.
В 1-м неравенстве (≤) вводим базисную переменную x₅. В 2-м неравенстве (≤) вводим базисную переменную x₆. В 3-м неравенстве (≤) вводим базисную переменную x₇. В 4-м неравенстве (≤) вводим базисную переменную x₈.
Получаем систему уравнений.
10x₁+20x₂+15x₃+18x₄+x₅ = 250
5x₂+8x₃+7x₄+x₆ = 40
15x₁+18x₂+12x₃+20x₄+x₇ = 100
8x₁+12x₂+11x₃+10x₄+x₈ = 80
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

10	20	15	18	1	0	0	0
0	5	8	7	0	1	0	0
15	18	12	20	0	0	1	0
8	12	11	10	0	0	0	1

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

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈
x₅	250	10	20	15	18	1	0	0	0
x₆	40	0	5	8	7	0	1	0	0
x₇	100	15	18	12	20	0	0	1	0
x₈	80	8	12	11	10	0	0	0	1
F(X0)	0	-4	-2	-4	-3	0	0	0	0

Решение с помощью симплекс-таблиц в Excel
Разрешающий столбец будет тот, у которого наименьшая оценка в строке целевой функции, в нашем случае это столбцы Х1 и Х3. Берём по порядку Х1.
Находим оценочное отношение, равное делением столбца свободных членов на соответствующий элемент разрешающего столбца.
Получим: (250/10=25; 40/0 ; 100/15=6.667; 80/8=10) = (25; ; 6.667; 10)
Затем находим наименьшее оценочное отношение.
Min (25; ; 6.667; 10) = 6.667
Оно соответствует строке с переменной Х7. Разрешающий элемент (15) находится на пересечении разрешающего столбца и разрешающей строки.

Первая симплекс-таблица

Пересчитываем следующую таблицу.

Первая итерация

Новый элемент таблицы:
НЭ = (СЭ∙РЭ - А∙В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (8), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
$D$6 – ячейка фиксируется и по строке и столбцу
С$6 - ячейка фиксируется по столбцу
$D4 - ячейка фиксируется по строке
Далее протягиваем формулу на все элементы таблицы.
Элементы, соответствующие разрешающей строке, находим делением их на разрешающий элемент.
Разрешающий столбец во второй таблице соответствует элементу Х3 (имеет отрицательную оценку в строке целевой функции), а разрешающая строка соответствует элементу Х6 (минимальное оценочное отношение. Разрешающий элемент: (8).
Получим:

Вторая симплекс-таблица

Пересчитываем следующую таблицу.

Вторая итерация

Новый элемент таблицы:
НЭ = (СЭ∙РЭ - А∙В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (8), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
$F$13 – ячейка фиксируется и по строке и столбцу
С$13 - ячейка фиксируется по столбцу
$F12 - ячейка фиксируется по строке
Далее протягиваем формулу на все элементы таблицы.
Элементы, соответствующие разрешающей строке, находим делением их на разрешающий элемент.
Получим.

Третья симплекс-таблица

Мы получили тот же результат, что и в уроке 1, где находили ответ с помощью надстройки «поиск решения».
Файл с решением:
https://t.me/smys_l/127

Заявка на услуги

Укажите наиболее удобный для ВАС способ связи
и с Вами свяжутся в ближайшее время

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