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

Задание следующее:
Решить задачу симплекс методом.
{ x1 + 2x2 +x3 + 2x4 = 16
{ 2x1 + x2 + 2x3 + x4 = 14
{ 2x1 + 2x2 - 2x3 + x4 = 4

x1,x2,x3,x4 => 0

F = 2x1+x2+x3+2x4 -> max

Из теории я поняла, что
а) задача должна быть записана в канонической форме (здесь она уже дана в канонической форме)
б) количество неизвестных должно быть больше количества уравнений (это соответствует)

решение:
Первым делом нужно найти допустимое базисное решение, которое бы максимизировала целевую функцию F, т.е необходимо найти оптимальное решение задачи.
Для это надо определить количество основных (базисных) переменных и неосновных. А вот только как это сделать, и как вычислить значения базинсных переменных через свободные я не поняла.... Количество базисных переменных обязательно должно равняться числу уравнений? и как определить какая переменная должна быть базисной а какая неосновной?
помогите пожалуйста,...)

количество неизвестных должно быть больше количества (уравнений) ограничений, пусть даже в виде неравенств.
Это вовсе необязательно.
Что же касается канонического вида задачи — в Вашем случае система не содержит базиса. Метод искусственно базиса Вы будете изучать позже. На Вашей задаче нельзя начинать изучать симплекс-метод (это вовсе не означает, что задача не решается).
Рекомендую выбрать другую задачу с ограничениями-неравенствами вида ≥, и я смогу показать Вам симплекс-метод.
Поймите, что привести задачу к каноническому виду (в виде ограничений-равенств) и решить её симплекс-методом — это не одно и то же.

Валентин, а другую задачу нет смысла выбирать, решать все-равно придется эту
Я понимаю, что привести к каноническому виду и решать симплекс-методом это не одно и то же. В моем случае для решения задачи симплекс методом дана задача уже в такой форме.

В методичке была разобрана задача как пример решения симплекс-методом. С той задачей более ли менее было все понятно, там у всех базисных переменных был коэффициент один, и с ней было проще разобраться. Какие преобразования делать в таблицах я немного поняла. А вот в этой задаче зависла на самом начале, так как на образец она совсем не похожа.....

Напишу пока кратко и своими словами. Ограничения заданы уравнениями. Уравнений 3, переменных — четыре, переменные неотрицательны. Наибольшие и наименьшие значения мы ищем в угловых точках. При этом как минимум одна переменная обратится в ноль. Если мы не приме́ним метод искусственного базиса, придётся выбирать базисные переменные наудачу. И не факт, что с первой попытки мы получим допустимое (неотрицательное) решение.
Уточните, пожалуйста, требуемый от Вас метод: применять или не применять метод искусственного базиса. Если применять, то в каком виде: одноэтапный или двухэтапный?

Честно говоря, я сама запуталась.
Тема - решение задач симплекс-методом, следуящая тема метод искусственого базиса, а затем тема про двойственность задач линейного программирования.
В контрольной на эти 3 темы есть 2 задачи:
Первая это та, которую я выложила. Задание - решить симплекс-методом
Вторая на двойственность.

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

Я лучше начну показывать с объяснениями. Пересказывать теорию — неблагодарное дело
Задача не содержит базиса. Введём искусственные базисные переменные   x₅, x₆, x₇ ≥ 0. Добавим эти переменные в целевую функцию таким образом, чтобы их ненулевые (положительные) значения ухудшали целевую функцию. Поскольку целевая функция стремится к максимуму, — добавим их в целевую функцию с коэффициентами   −M, где   M → +∞ — бесконечно большое положительное число.
В итоге получим M-задачу линейного программирования. Это и есть одноэтапный (одномоментный) метод искусственного базиса.

{1·x₁ + 2·x₂ + 1·x₃ + 2·x₄ + 1·x₅ = 16
{2·x₁ + 1·x₂ + 2·x₃ + 1·x₄ + 1·x₆ = 14
{2·x₁ + 2·x₂ − 2·x₃ + 1·x₄ + 1·x₇ = 4
{x_j ≥ 0   (j = 1, …, 7)

F = 2·x₁ + 1·x₂ + 1·x₃ + 2·x₄ − M·x₅ − M·x₆ − M·x₇ → max

Единичные коэффициенты я записал для Вашего же удобства, чтобы легче было внимательно и без ошибок заполнить симплекс-таблицу.

У меня получилась вот такая симплекс-таблица
[Вы должны быть зарегистрированы и подключены, чтобы видеть эту ссылку]

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

Симплекс-таблица составлена неверно. Она не соответствует M-задаче (одномоментному методу искусственного базиса). В частности, неверно найдено начальное значение целевой функции. Она на этом этапе должна быть равна −34·M.
Таблицы учат составлять (оформлять) по-разному, но считаются они одинаково. Например, можно включить в таблицу столбец с коэффициентами при базисных переменных. Не хватает в ней также строки с оценками Δ, либо неверно найдены сами оценки.
Покажите, пожалуйста, какого вида таблицы вам дают в учебнике или методичке. Как я всегда говорю, задачу надо не только правильно решить, но и успешно сдать, выполнив требования именно Вашего преподавателя.
И о рисунках в сообщениях. Желательно, чтобы картинки не исчезали, размещать их на фотохостингах с регистрацией. Например, пользуетесь ли Вы Яндекс-почтой постоянно? Если да — то почему бы не создать для форума специальный альбом в сервисе Яндекс-фоток?

Чтобы не объяснять на пальцах в каком виде у нас даются симплекс-таблицы, размещаю ссылку на методичку. Вы в ней поймете полюбому больше, чем я
[Вы должны быть зарегистрированы и подключены, чтобы видеть эту ссылку]

Составим симплекс-таблицу на основе M-задачи линейного программирования.

{1·x₁ + 2·x₂ + 1·x₃ + 2·x₄ + 1·x₅ = 16
{2·x₁ + 1·x₂ + 2·x₃ + 1·x₄ + 1·x₆ = 14
{2·x₁ + 2·x₂ − 2·x₃ + 1·x₄ + 1·x₇ = 4
{x_j ≥ 0   (j = 1, …, 7)

F = 2·x₁ + 1·x₂ + 1·x₃ + 2·x₄ − M·x₅ − M·x₆ − M·x₇ → max

			2	1	1	2	−M	−M	−M
Базис (Б)	Cб	b	x₁	x₂	x₃	x₄	x₅	x₆	x₇	θ
x₅	−M	16	1	2	1	2	1	0	0	16
x₆	−M	14	2	1	2	1	0	1	0	7
x₇	−M	4	2	2	−2	1	0	0	1	2 (min)
	Δ	−34·M	−5·M − 2	−5·M − 1	−1·M − 1	−4·M − 2	0	0	0
x₅	−M	14	0	1	2	³⁄₂	1	0	−½
x₆	−M	10	0	−1	4	0	0	1	−1
x₁	2	2	1	1	−1	½	0	0	½			Δ	−24·M + 4	0	1	−6·M − 3	−³⁄₂·M − 1	0	0	³⁄₂·M + 1

Симплекс-таблицу я заполнил не до конца. В частности, второй столбец и последнюю строку. До сих пор таблица понятна?

В принципе да.

Уже хорошо. Заполним второй столбец коэффициентами при базисных переменных   x₅, x₆, x₇. Я заполнил. Теперь перейдём к вычислению оценок   Δ. Опишите, как Вы будете их вычислять.

Если честно, то что такое оценки Δ я даже не представляю. В методичке ни в одном из примеров не было такой строки...

В Вашей методичке это соответствует последней строке таблицы. Мы же рассматриваем задачу посложнее — метод искусственного базиса. Как я говорил, шапку таблицы можно оформить и по-другому. И Вам будет полезно оформить потом симплекс-таблицы в соответствии с методичкой. Они даны у Вас в сокращённой форме, я же показываю в полной, так легче разобраться.
Начнём. Нужно столбец C_б скалярно умножить на соответствующий столбец коэффициентов при неизвестных в уравнениях и отнять в каждом столбце, кроме первого (нулевого) коэффициент при неизвестной в целевой функции.
Заполним нулевую ячейку:   Δ₀ = −M·16 − M·14 − M·4 = −34·M
Первая ячейка:   Δ₁ = −M·1 − M·2 − M·2 − 2 = −5·M − 2
В таблицу я дописал. Подсчитайте значения в остальных ячейках.

По аналогии заполняем:
Δ2 = −M·2 − M·1 − M·2 − 1 = −5·M − 1
Δ3 = −M·1 − M·2 + M·2 − 1 = −1·M − 1
Δ4 = −M·2 − M·1 − M·1 − 2 = −4·M − 2
Δ5 = −M·1− M·0 − M·0 − 0 = −1·M
Δ6 = −M·0− M·1 − M·0 − 0 = −1·M
Δ6 = −M·0− M·0 − M·1 − 0 = −1·M

Только я не поняла почему во втором столбце коэффициенты -М. В равентсвах они же с плюсом....

Ошибки Ваши я подчеркнул. Можете их исправить.
Во второй столбец перенесены коэффициенты при неизвестных в целевой функции. Она стремится к максимуму. С минусом коэффициенты при искусственных базисных переменных взяты, чтобы они ухудшали целевую функцию до тех пор, пока не будут выведены из базиса.

во втором столбце взяты коэффициенты при неизвестных в целевой функции - теперь понятно. Просто я решила. что это коэффициенты при добавленных переменных в уравнениях. поэтому запуталась.
[/quote]столбец Cб скалярно умножить на соответствующий столбец коэффициентов при неизвестных в уравнениях и отнять в каждом столбце, кроме первого (нулевого) коэффициент при неизвестной в целевой функции.[quote]
к примеру для х5:
коэфф при неизв. в целевой функции -1 ? Δ5 = −M·1− M·0 − M·0 + 1 = −1·M + 1, так ?
или коэфф. -0 и будет Δ5 = −M·1− M·0 − M·0 + 0 = −1·M ....

Сравните вычисление оценок в 1-4 столбцах и в 5-7, тогда поймёте свою ошибку.

Столбец Сб умножаем на соответствующий столбец коэффициентов при неизвестных в уравнениях и отнимаем в каждом столбце коэффициент при неизвестной в целевой функции
для х5, х6, х7 коэфф при неизв. в целевой функции -1
Δ5 = −M·1− M·0 − M·0 - (- 1) = −1·M + 1
Δ6 = −M·0− M·1 − M·0 - (- 1) = −1·M + 1
Δ7 = −M·0− M·0 − M·1 - (- 1) = −1·M + 1
так?

А разве коэффициенты при неизвестных   x₅, x₆, x₇   в целевой функции равны   −1?

F = 2·x₁ + 1·x₂ + 1·x₃ + 2·x₄ − M·x₅ − M·x₆ − M·x₇ → max а что не -1??
и во втором столбце были взяты кэффициенты при неизвестных в целевой функции.... -М везде было во втором столбце...
все, мозг распух я запуталась.... других вариантов у меня нет...

нет ну у меня еще есть вариант, что коэффициент - 0
Я уже раз десять сравнла вычисления во всех столбцах, ну не могу я найти ошибку....
помогите

Там коэффициенты   −M, а не   −1.

то есть получается
Δ5 = −M·1− M·0 − M·0 - (- М) = −1·M + М = 0
Δ6 = −M·0− M·1 − M·0- (- М) = −1·M + М = 0
Δ7 = −M·0− M·0 − M·1 - (- М) = −1·M + М = 0

Правильно!
Как и следовало ожидать, оценки   Δ   для базисных переменных равны нулю. Допишем их в таблицу.
Какой предпримем следующий шаг?

рискну предположить, что надо найти допустимое решение.