Решение задач симплекс-методом

Здравствуйте!
Дана матрица:
2 3 1 0 0 | 6
4 5 0 1 0 | 8
1 2 0 0 1 | 4
-2 -2 0 0 0 | -12

В нижней строке коэффициенты при целевой функции и значении целевой функции.
x1=0 так как 1-й коэф. целевой функции отрицательный
x2=0 так как 2-й коэф. целевой функции отрицательный
x3=6 так как 3-й коэф. целевой функции равен нулю, идём вверх по столбцу пока не встретим 1.

Подскажите, пожалуйста, как найти x3, если в третьем столбце не было бы 1?

0

Впечатление такое, что вы написали середину решения: х3, х4 и х5 явно дополнительные переменные, судя по присоединённой к исходной системе единичной матрице. Целевая функция должна принимать или максимальное, или минимальное значение. У вас уже написано -12, не ясно откуда взятое.
Напишите исходную систему в виде неравенств и нужно минимизировать или максимизировать целевую функцию?

0

Это пример 2.4 из учебника В.П.Агальцова математические методы в программировании
Найти максимум целевой функции:
Fx=2*x1+4*x2+2*x3
ограничения:
x2+2*x3=>4
2*x1+3*x2+x3=6;
2*x1+2*x2<=4
xj=>0, j=1,2,3
Добавление фиктивных переменных:
0*x1+1*x2+2*x3-1*x4+0*x5=4;
2*x1+3*x2+1*x3+0*x4+0*x5=6;
2*x1+2*x2+0*x3+0*x4+1*x5=4
2*x1+4*x2+2*x3+0*x4+0*x5
Матричная модель:
0 1 2 -1 0 | 4
2 3 1 0 0 | 6
2 2 0 0 1 | 4
2 4 2 0 0
Ведущий элемент 3:
0 1 2 -1 0 | 4
2/3 1 1/3 0 0 | 6
2 2 0 0 1 | 4
2 4 2 0 0
Проводим итерацию:
-2/3 0 5/3 -1 0 | 2
2/3 1 1/3 0 0 | 2
2/3 0 -2/3 0 1 | 0
-2/3 0 2/3 0 0 -8
Ведущий элемент 5/3:
-2/5 0 1 -3/5 0 | 6/5
2/3 1 1/3 0 0 | 2
2/3 0 -2/3 0 1 | 0
-2/3 0 2/3 0 0 -8
Проводим итерацию:
-2/5 0 1 -3/5 0 | 6/5
4/5 1 0 1/5 0 | 8/5
2/5 0 0 -2/5 1 | 4/5
-2/5 0 0 2/5 0 -44/5
Ведущий элемент 1/5:
-2/5 0 1 -3/5 0 | 6/5
4 5 0 1 0 | 8
2/5 0 0 -2/5 1 | 4/5
-2/5 0 0 2/5 0 -44/5
Проводим итерацию:
2 3 1 0 0 | 6
4 5 0 1 0 | 8
14/5 2 0 0 1 | 4
-2 -2 0 0 0 -12
Ответ:
X(0;0;6).

В конце примера 2.3 написано:
"Найденное решение записывается следующим образом: отрицательным коэффициентам в векторе решения соответствуют нулевые значения, а нулевым значениям-значения свободных членов (b) в строках, содержащих единицу."

Но, что делать если в строке нет единиц или их больше одной?
Например:
2 3 0 0 0 | 6
4 5 0 1 0 | 8
14/5 2 0 0 1 | 4
-2 -2 0 0 0 -12
или:
2 3 1 0 0 | 6
4 5 1 1 0 | 8
14/5 2 0 0 1 | 4
-2 -2 0 0 0 -12

0

Сообщение от HitGirl Добавление фиктивных переменных:

Уже не то: суммарное количество переменных у вас должно быть 7, а не 5, чтобы последние три столбца образовывали единичную матрицу.Хотя, может вам рассказывали по-другому... Ответ у меня такой же:

Вложения

Симплекс.xlsx (13.6 Кб, 6 просмотров)

0

jogano, можете дать какую-нибудь литературу, где есть описание этого метода?
Я по excel-файлу не могу разобраться.

0

И.Я.Бирман "Оптимальное программирование", М-1968 г. Да, раритет... Но по ней я составил макрос на VBA, который и делает симплекс-таблицы. А самая верхняя таблица в том эксель-файле делается руками. На листе обозначение "M-" означает вес переменной в целевой функции , и такая запись означает, что в задаче на максимум этой переменная точно НЕ должно быть в ответе.

0

Похоже этой книги нет в продаже. Можете, пожалуйста, пояснить своё решение?

Сообщение от jogano На листе обозначение "M-" означает вес переменной в целевой функции

Почему над x7 стоит 0, а не M-? Как найти M-> и альфу?

0

Сообщение от HitGirl Почему над x7 стоит 0, а не M-? Как найти M-> и альфу?

3-е неравенство вашей исходной системы это неравенство "<=", значит, чтобы сделать из него равенство, нужно к левой части что-то прибавлять (дополнительную переменную), которая может входить (и в итоге входит со значением Х7=4) в ответ. Но так как в целевая функция от неё не зависит, то её вес в целевой функции равен 0.

Весь процесс долго описывать.

0

Сообщение от HitGirl можете дать какую-нибудь литературу

Литература по численным методам
Название: Основы линейного программирования
Автор: Банди Б.
Издательство: М.: Радио и связь
Год : 1989

(есть в электронном виде)

0

Спасибо за ответы!

0