Главная Коллекция "Otherreferats" Экономико-математическое моделирование Симплекс-метод

Симплекс-метод

Решение задач графически и симплекс-методом. Экономическое толкование полученных решений. Решение двойственной задачи для оптимальной системы оценок ресурсов. Определение дефицитных и недефицитных ресурсов. Обоснование эффективности оптимального плана.

Рубрика	Экономико-математическое моделирование
Вид	контрольная работа
Язык	русский
Дата добавления	13.09.2015
Размер файла	226,7 K

посмотреть текст работы

скачать работу можно здесь

полная информация о работе

весь список подобных работ

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Страница:

Размещено на http://www.allbest.ru

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ОДЕССКИЙ НАЦИОНАЛЬНЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Институт: Дистанционного и заочного образования

Кафедра: Экономической кибернетики

Контрольная робота

По предмету: «Исследования операций»

Студента группы ЗОИ - 111

Пестерев Н.А.

г. Одесса - 2015

ВОПРОС № 1. СИМПЛЕКС-МЕТОД

a. Решить графически.

b. Решить задачу симплекс-методом.

c. Построить двойственную к ней и найти ее решение.

d. Дать экономическое истолкование полученных решений.

Решить графически

симплекс двойственный ресурс дефицитный

Шаг №1. Построим область допустимых решений, т.е. решим графически систему неравенств.

Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

Построим уравнение x₁+x₂ = 3 по двум точкам.

Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 3. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 3. Соединяем точку (0;3) с (3;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 * 0 + 1 * 0 - 3 ? 0, т.е. x₁+x₂ - 3? 0 в полуплоскости выше прямой.

Построим уравнение 5x₁+x₂ = 5 по двум точкам.

Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 5. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 1. Соединяем точку (0;5) с (1;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 5 * 0 + 1 * 0 - 5 ? 0, т.е. 5x₁+x₂ - 5? 0 в полуплоскости выше прямой.

Построим уравнение x₁+5x₂ = 5 по двум точкам.

Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 1. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 5. Соединяем точку (0;1) с (5;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 * 0 + 5 * 0 - 5 ? 0, т.е. x₁+5x₂ - 5? 0 в полуплоскости выше прямой.

Построим уравнение x₁ = 0.

Эта прямая проходит через точку x₁ = 0 параллельно оси OX2. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 * 0 - 0 = 0, т.е. x₁ - 0? 0 в полуплоскости на прямой.

Построим уравнение x₁ = 4.

Эта прямая проходит через точку x₁ = 4 параллельно оси OX2. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 * 0 - 4 ? 0, т.е. x₁ - 4? 0 в полуплоскости левее прямой.

Построим уравнение x₂ = 0.

Эта прямая проходит через точку x₂ = 0 параллельно оси OX1. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 * 0 - 0 = 0, т.е. x₂ - 0? 0 в полуплоскости на прямой.

Построим уравнение x₂ = 4.

Эта прямая проходит через точку x₂ = 4 параллельно оси OX1. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 * 0 - 4 ? 0, т.е. x₂ - 4? 0 в полуплоскости ниже прямой.

Шаг №2. Границы области допустимых решений.

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

Шаг №3. Рассмотрим целевую функцию задачи F = 7x₁-x₂ > min.

Построим прямую, отвечающую значению функции F = 0: F = 7x₁-x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора - точка (0; 0), конец - точка (7; -1). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (2) и (7), то ее координаты удовлетворяют уравнениям этих прямых:

5x₁+x₂=5

x₂=4

Решив систему уравнений, получим: x₁ = 0.2, x₂ = 4

Откуда найдем минимальное значение целевой функции:

F(X) = 7*0.2 - 1*4 = -2.6

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

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (?) вводим базисную переменную x₃ со знаком минус. В 2-м неравенстве смысла (?) вводим базисную переменную x₄ со знаком минус. В 3-м неравенстве смысла (?) вводим базисную переменную x₅ со знаком минус. В 4-м неравенстве смысла (?) вводим базисную переменную x₆ со знаком минус. В 5-м неравенстве смысла (?) вводим базисную переменную x₇. В 6-м неравенстве смысла (?) вводим базисную переменную x₈ со знаком минус. В 7-м неравенстве смысла (?) вводим базисную переменную x₉.

1x₁ + 1x₂-1x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ = 3

5x₁ + 1x₂ + 0x₃-1x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ = 5

1x₁ + 5x₂ + 0x₃ + 0x₄-1x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ = 5

1x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅-1x₆ + 0x₇ + 0x₈ + 0x₉ = 0

1x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 1x₇ + 0x₈ + 0x₉ = 4

0x₁ + 1x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇-1x₈ + 0x₉ = 0

0x₁ + 1x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 1x₉ = 4

Введем искусственные переменные x: в 1-м равенстве вводим переменную x₁₀; в 2-м равенстве вводим переменную x₁₁; в 3-м равенстве вводим переменную x₁₂; в 4-м равенстве вводим переменную x₁₃; в 6-м равенстве вводим переменную x₁₄;

1x₁ + 1x₂-1x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ + 1x₁₀ + 0x₁₁ + 0x₁₂ + 0x₁₃ + 0x₁₄ = 3

5x₁ + 1x₂ + 0x₃-1x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ + 0x₁₀ + 1x₁₁ + 0x₁₂ + 0x₁₃ + 0x₁₄ = 5

1x₁ + 5x₂ + 0x₃ + 0x₄-1x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ + 0x₁₀ + 0x₁₁ + 1x₁₂ + 0x₁₃ + 0x₁₄ = 5

1x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅-1x₆ + 0x₇ + 0x₈ + 0x₉ + 0x₁₀ + 0x₁₁ + 0x₁₂ + 1x₁₃ + 0x₁₄ = 0

1x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 1x₇ + 0x₈ + 0x₉ + 0x₁₀ + 0x₁₁ + 0x₁₂ + 0x₁₃ + 0x₁₄ = 4

0x₁ + 1x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇-1x₈ + 0x₉ + 0x₁₀ + 0x₁₁ + 0x₁₂ + 0x₁₃ + 1x₁₄ = 0

0x₁ + 1x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 1x₉ + 0x₁₀ + 0x₁₁ + 0x₁₂ + 0x₁₃ + 0x₁₄ = 4

Для постановки задачи на максимум целевую функцию запишем так:

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

Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.

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

Из уравнений выражаем искусственные переменные:

x₁₀ = 3-x₁-x₂+x₃

x₁₁ = 5-5x₁-x₂+x₄

x₁₂ = 5-x₁-5x₂+x₅

x₁₃ = 0-x₁+x₆

x₁₄ = 0-x₂+x₈

которые подставим в целевую функцию:

F(X) = 7x₁-x₂ - M(3-x₁-x₂+x₃) - M(5-5x₁-x₂+x₄) - M(5-x₁-5x₂+x₅) - M(0-x₁+x₆) - M(0-x₂+x₈) > max

или

F(X) = (7+8M)x₁+(-1+8M)x₂+(-M)x₃+(-M)x₄+(-M)x₅+(-M)x₆+(-M)x₈+(-13M) > max

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

1	1	-1	0	0	0	0	0	0	1	0	0	0	0
5	1	0	-1	0	0	0	0	0	0	1	0	0	0
1	5	0	0	-1	0	0	0	0	0	0	1	0	0
1	0	0	0	0	-1	0	0	0	0	0	0	1	0
1	0	0	0	0	0	1	0	0	0	0	0	0	0
0	1	0	0	0	0	0	-1	0	0	0	0	0	1
0	1	0	0	0	0	0	0	1	0	0	0	0	0

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

Экономический смысл дополнительных переменных: дополнительные переменные задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

Решим систему уравнений относительно базисных переменных: x₁₀, x₁₁, x₁₂, x₁₃, x₇, x₁₄, x₉

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,0,0,0,4,0,4,3,5,5,0,0)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₁₀	3	1	1	-1	0	0	0	0	0	0	1	0	0	0	0
x₁₁	5	5	1	0	-1	0	0	0	0	0	0	1	0	0	0
x₁₂	5	1	5	0	0	-1	0	0	0	0	0	0	1	0	0
x₁₃	0	1	0	0	0	0	-1	0	0	0	0	0	0	1	0
x₇	4	1	0	0	0	0	0	1	0	0	0	0	0	0	0
x₁₄	0	0	1	0	0	0	0	0	-1	0	0	0	0	0	1
x₉	4	0	1	0	0	0	0	0	0	1	0	0	0	0	0
F(X0)	-13M	-7-8M	1-8M	M	M	M	M	0	M	0	0	0	0	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

и из них выберем наименьшее:

Следовательно, 4-ая строка является ведущей.

Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	min
x₁₀	3	1	1	-1	0	0	0	0	0	0	1	0	0	0	0	3
x₁₁	5	5	1	0	-1	0	0	0	0	0	0	1	0	0	0	1
x₁₂	5	1	5	0	0	-1	0	0	0	0	0	0	1	0	0	5
x₁₃	0	1	0	0	0	0	-1	0	0	0	0	0	0	1	0	0
x₇	4	1	0	0	0	0	0	1	0	0	0	0	0	0	0	4
x₁₄	0	0	1	0	0	0	0	0	-1	0	0	0	0	0	1	-
x₉	4	0	1	0	0	0	0	0	0	1	0	0	0	0	0	-
F(X1)	-13M	-7-8M	1-8M	M	M	M	M	0	M	0	0	0	0	0	0	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₁₃ в план 1 войдет переменная x₁

Строка, соответствующая переменной x₁ в плане 1, получена в результате деления всех элементов строки x₁₃ плана 0 на разрешающий элемент РЭ=1

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₁ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₁ и столбец x₁.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B	x₁	x₂	x₃	x₄	x₅	x₆



0 / 1 = 0	1 / 1 = 1	0 / 1 = 0	0 / 1 = 0	0 / 1 = 0	0 / 1 = 0	-1 / 1 = -1

x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄



0 / 1 = 0	0 / 1 = 0	0 / 1 = 0	0 / 1 = 0	0 / 1 = 0	0 / 1 = 0	1 / 1 = 1	0 / 1 = 0

После преобразований получаем новую таблицу:

Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₁₀	3	0	1	-1	0	0	1	0	0	0	1	0	0	-1	0
x₁₁	5	0	1	0	-1	0	5	0	0	0	0	1	0	-5	0
x₁₂	5	0	5	0	0	-1	1	0	0	0	0	0	1	-1	0
x₁	0	1	0	0	0	0	-1	0	0	0	0	0	0	1	0
x₇	4	0	0	0	0	0	1	1	0	0	0	0	0	-1	0
x₁₄	0	0	1	0	0	0	0	0	-1	0	0	0	0	0	1
x₉	4	0	1	0	0	0	0	0	0	1	0	0	0	0	0
F(X1)	-13M	0	1-8M	M	M	M	-7-7M	0	M	0	0	0	0	7+8M	0

Итерация №1.

1. Проверка критерия оптимальности.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

Следовательно, 6-ая строка является ведущей.

Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	min
x₁₀	3	0	1	-1	0	0	1	0	0	0	1	0	0	-1	0	3
x₁₁	5	0	1	0	-1	0	5	0	0	0	0	1	0	-5	0	5
x₁₂	5	0	5	0	0	-1	1	0	0	0	0	0	1	-1	0	1
x₁	0	1	0	0	0	0	-1	0	0	0	0	0	0	1	0	-
x₇	4	0	0	0	0	0	1	1	0	0	0	0	0	-1	0	-
x₁₄	0	0	1	0	0	0	0	0	-1	0	0	0	0	0	1	0
x₉	4	0	1	0	0	0	0	0	0	1	0	0	0	0	0	4
F(X2)	-13M	0	1-8M	M	M	M	-7-7M	0	M	0	0	0	0	7+8M	0	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₁₄ в план 2 войдет переменная x₂

Строка, соответствующая переменной x₂ в плане 2, получена в результате деления всех элементов строки x₁₄ плана 1 на разрешающий элемент РЭ=1

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₂ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₂ и столбец x₂.

Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x₁	x₂	x₃	x₄	x₅	x₆





0 / 1 = 0	0 / 1 = 0	1 / 1 = 1	0 / 1 = 0	0 / 1 = 0	0 / 1 = 0	0 / 1 = 0

x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄





0 / 1 = 0	-1 / 1 = -1	0 / 1 = 0	0 / 1 = 0	0 / 1 = 0	0 / 1 = 0	0 / 1 = 0	1 / 1 = 1

После преобразований получаем новую таблицу:

Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₁₀	3	0	0	-1	0	0	1	0	1	0	1	0	0	-1	-1
x₁₁	5	0	0	0	-1	0	5	0	1	0	0	1	0	-5	-1
x₁₂	5	0	0	0	0	-1	1	0	5	0	0	0	1	-1	-5
x₁	0	1	0	0	0	0	-1	0	0	0	0	0	0	1	0
x₇	4	0	0	0	0	0	1	1	0	0	0	0	0	-1	0
x₂	0	0	1	0	0	0	0	0	-1	0	0	0	0	0	1
x₉	4	0	0	0	0	0	0	0	1	1	0	0	0	0	-1
F(X2)	-13M	0	0	M	M	M	-7-7M	0	1-7M	0	0	0	0	7+8M	-1+8M

Итерация №2.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₆, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i6

и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (5) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	min
x₁₀	3	0	0	-1	0	0	1	0	1	0	1	0	0	-1	-1	3
x₁₁	5	0	0	0	-1	0	5	0	1	0	0	1	0	-5	-1	1
x₁₂	5	0	0	0	0	-1	1	0	5	0	0	0	1	-1	-5	5
x₁	0	1	0	0	0	0	-1	0	0	0	0	0	0	1	0	-
x₇	4	0	0	0	0	0	1	1	0	0	0	0	0	-1	0	4
x₂	0	0	1	0	0	0	0	0	-1	0	0	0	0	0	1	-
x₉	4	0	0	0	0	0	0	0	1	1	0	0	0	0	-1	-
F(X3)	-13M	0	0	M	M	M	-7-7M	0	1-7M	0	0	0	0	7+8M	-1+8M	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₁₁ в план 3 войдет переменная x₆

Строка, соответствующая переменной x₆ в плане 3, получена в результате деления всех элементов строки x₁₁ плана 2 на разрешающий элемент РЭ=5

На месте разрешающего элемента в плане 3 получаем 1.

В остальных клетках столбца x₆ плана 3 записываем нули.

Таким образом, в новом плане 3 заполнены строка x₆ и столбец x₆.

Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x₁	x₂	x₃	x₄	x₅	x₆

5 / 5 = 1	0 / 5 = 0	0 / 5 = 0	0 / 5 = 0	-1 / 5 = -0.2	0 / 5 = 0	5 / 5 = 1

x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄

0 / 5 = 0	1 / 5 = 0.2	0 / 5 = 0	0 / 5 = 0	1 / 5 = 0.2	0 / 5 = 0	-5 / 5 = -1	-1 / 5 = -0.2

После преобразований получаем новую таблицу:

Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₁₀	2	0	0	-1	0.2	0	0	0	0.8	0	1	-0.2	0	0	-0.8
x₆	1	0	0	0	-0.2	0	1	0	0.2	0	0	0.2	0	-1	-0.2
x₁₂	4	0	0	0	0.2	-1	0	0	4.8	0	0	-0.2	1	0	-4.8
x₁	1	1	0	0	-0.2	0	0	0	0.2	0	0	0.2	0	0	-0.2
x₇	3	0	0	0	0.2	0	0	1	-0.2	0	0	-0.2	0	0	0.2
x₂	0	0	1	0	0	0	0	0	-1	0	0	0	0	0	1
x₉	4	0	0	0	0	0	0	0	1	1	0	0	0	0	-1
F(X3)	7-6M	0	0	M	-1.4-0.4	M	0	0	2.4-5.6M	0	0	1.4+1.4M	0	M	-2.4+6.6M

Итерация №3.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₈, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i8 и из них выберем наименьшее:

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (4.8) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	min
x₁₀	2	0	0	-1	0.2	0	0	0	0.8	0	1	-0.2	0	0	-0.8	2.5
x₆	1	0	0	0	-0.2	0	1	0	0.2	0	0	0.2	0	-1	-0.2	5
x₁₂	4	0	0	0	0.2	-1	0	0	4.8	0	0	-0.2	1	0	-4.8	0.83
x₁	1	1	0	0	-0.2	0	0	0	0.2	0	0	0.2	0	0	-0.2	5
x₇	3	0	0	0	0.2	0	0	1	-0.2	0	0	-0.2	0	0	0.2	-
x₂	0	0	1	0	0	0	0	0	-1	0	0	0	0	0	1	-
x₉	4	0	0	0	0	0	0	0	1	1	0	0	0	0	-1	4
F(X4)	7-6M	0	0	M	-1.4-0.4M	M	0	0	2.4-5.6M	0	0	1.4+1.4M	0	M	-2.4+6.6M	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₁₂ в план 4 войдет переменная x₈

Строка, соответствующая переменной x₈ в плане 4, получена в результате деления всех элементов строки x₁₂ плана 3 на разрешающий элемент РЭ=4.8

На месте разрешающего элемента в плане 4 получаем 1.

В остальных клетках столбца x₈ плана 4 записываем нули.

Таким образом, в новом плане 4 заполнены строка x₈ и столбец x₈.

Все остальные элементы нового плана 4, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x₁	x₂	x₃	x₄	x₅	x₆


4 / 4.8 = 0.83	0 / 4.8 = 0	0 / 4.8 = 0	0 / 4.8 = 0	0.2 / 4.8 = 0.0417	-1 / 4.8 = -0.21	0 / 4.8 = 0

После преобразований получаем новую таблицу:

Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₁₀	1.33	0	0	-1	0.17	0.17	0	0	0	0	1	-0.17	-0.17	0	0
x₆	0.83	0	0	0	-0.21	0.0417	1	0	0	0	0	0.21	-0.0417	-1	0
x₈	0.83	0	0	0	0.0417	-0.21	0	0	1	0	0	-0.0417	0.21	0	-1
x₁	0.83	1	0	0	-0.21	0.0417	0	0	0	0	0	0.21	-0.0417	0	0
x₇	3.17	0	0	0	0.21	-0.0417	0	1	0	0	0	-0.21	0.0417	0	0
x₂	0.83	0	1	0	0.0417	-0.21	0	0	0	0	0	-0.0417	0.21	0	0
x₉	3.17	0	0	0	-0.0417	0.21	0	0	0	1	0	0.0417	-0.21	0	0
F(X4)	5-1.33M	0	0	M	-1.5-0.17M	0.5-0.17M	0	0	0	0	0	1.5+1.17M	-0.5+1.17M	M	M

Итерация №4.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₄, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i4

и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (0.17) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	min
x₁₀	1.33	0	0	-1	0.17	0.17	0	0	0	0	1	-0.17	-0.17	0	0	8
x₆	0.83	0	0	0	-0.21	0.0417	1	0	0	0	0	0.21	-0.0417	-1	0	-
x₈	0.83	0	0	0	0.0417	-0.21	0	0	1	0	0	-0.0417	0.21	0	-1	20
x₁	0.83	1	0	0	-0.21	0.0417	0	0	0	0	0	0.21	-0.0417	0	0	-
x₇	3.17	0	0	0	0.21	-0.0417	0	1	0	0	0	-0.21	0.0417	0	0	15.2
x₂	0.83	0	1	0	0.0417	-0.21	0	0	0	0	0	-0.0417	0.21	0	0	20
x₉	3.17	0	0	0	-0.0417	0.21	0	0	0	1	0	0.0417	-0.21	0	0	-
F(X5)	5-1.33M	0	0	M	-1.5-0.17M	0.5-0.17M	0	0	0	0	0	1.5+1.17M	-0.5+1.17M	M	M	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₁₀ в план 5 войдет переменная x₄

Строка, соответствующая переменной x₄ в плане 5, получена в результате деления всех элементов строки x₁₀ плана 4 на разрешающий элемент РЭ=0.17

На месте разрешающего элемента в плане 5 получаем 1.

В остальных клетках столбца x₄ плана 5 записываем нули.

Таким образом, в новом плане 5 заполнены строка x₄ и столбец x₄.

Все остальные элементы нового плана 5, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x₁	x₂	x₃	x₄
1.33 / 0.17 = 8	0 / 0.17 = 0	0 / 0.17 = 0	-1 / 0.17 = -6	0.17 / 0.17 = 1

x₅	x₆	x₇	x₈	x₉	x₁₀
0.17 / 0.17 = 1	0 / 0.17 = 0	0 / 0.17 = 0	0 / 0.17 = 0	0 / 0.17 = 0	1 / 0.17 = 6

x₁₁	x₁₂	x₁₃	x₁₄
-0.17 / 0.17 = -1	-0.17 / 0.17 = -1	0 / 0.17 = 0	0 / 0.17 = 0

После преобразований получаем новую таблицу:

Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₄	8	0	0	-6	1	1	0	0	0	0	6	-1	-1	0	0
x₆	2.5	0	0	-1.25	0	0.25	1	0	0	0	1.25	0	-0.25	-1	0
x₈	0.5	0	0	0.25	0	-0.25	0	0	1	0	-0.25	0	0.25	0	-1
x₁	2.5	1	0	-1.25	0	0.25	0	0	0	0	1.25	0	-0.25	0	0
x₇	1.5	0	0	1.25	0	-0.25	0	1	0	0	-1.25	0	0.25	0	0
x₂	0.5	0	1	0.25	0	-0.25	0	0	0	0	-0.25	0	0.25	0	0
x₉	3.5	0	0	-0.25	0	0.25	0	0	0	1	0.25	0	-0.25	0	0
F(X5)	17	0	0	-9	0	2	0	0	0	0	9+M	M	-2+M	M	M

Итерация №5.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3

и из них выберем наименьшее:

Следовательно, 5-ая строка является ведущей.

Разрешающий элемент равен (1.25) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	min
x₄	8	0	0	-6	1	1	0	0	0	0	6	-1	-1	0	0	-
x₆	2.5	0	0	-1.25	-0	0.25	1	0	0	0	1.25	0	-0.25	-1	0	-
x₈	0.5	0	0	0.25	0	-0.25	0	0	1	0	-0.25	-0	0.25	0	-1	2
x₁	2.5	1	0	-1.25	-0	0.25	0	0	0	0	1.25	0	-0.25	0	0	-
x₇	1.5	0	0	1.25	0	-0.25	0	1	0	0	-1.25	-0	0.25	0	0	1.2
x₂	0.5	0	1	0.25	0	-0.25	0	0	0	0	-0.25	-0	0.25	0	0	2
x₉	3.5	0	0	-0.25	-0	0.25	0	0	0	1	0.25	0	-0.25	0	0	-
F(X6)	17	0	0	-9	0	2	0	0	0	0	9+M	M	-2+M	M	M	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₇ в план 6 войдет переменная x₃

Строка, соответствующая переменной x₃ в плане 6, получена в результате деления всех элементов строки x₇ плана 5 на разрешающий элемент РЭ=1.25

На месте разрешающего элемента в плане 6 получаем 1.

В остальных клетках столбца x₃ плана 6 записываем нули.

Таким образом, в новом плане 6 заполнены строка x₃ и столбец x₃.

Все остальные элементы нового плана 6, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x₁	x₂	x₃	x₄




1.5 / 1.25 = 1.2	0 / 1.25 = 0	0 / 1.25 = 0	1.25 / 1.25 = 1	0 / 1.25 = 0

x₅	x₆	x₇	x₈	x₉




-0.25 / 1.25 = -0.2	0 / 1.25 = 0	1 / 1.25 = 0.8	0 / 1.25 = 0	0 / 1.25 = 0

x₁₀	x₁₁	x₁₂	x₁₃	x₁₄




-1.25 / 1.25 = -1	-0 / 1.25 = 0	0.25 / 1.25 = 0.2	0 / 1.25 = 0	0 / 1.25 = 0

После преобразований получаем новую таблицу:

Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₄	15.2	0	0	0	1	-0.2	0	4.8	0	0	0	-1	0.2	0	0
x₆	4	0	0	0	0	0	1	1	0	0	0	0	0	-1	0
x₈	0.2	0	0	0	0	-0.2	0	-0.2	1	0	0	0	0.2	0	-1
x₁	4	1	0	0	0	0	0	1	0	0	0	0	0	0	0
x₃	1.2	0	0	1	0	-0.2	0	0.8	0	0	-1	0	0.2	0	0
x₂	0.2	0	1	0	0	-0.2	0	-0.2	0	0	0	0	0.2	0	0
x₉	3.8	0	0	0	0	0.2	0	0.2	0	1	0	0	-0.2	0	0
F(X6)	27.8	0	0	0	0	0.2	0	7.2	0	0	M	M	-0.2+M	M	M

1. Проверка критерия оптимальности.

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₄	15.2	0	0	0	1	-0.2	0	4.8	0	0	0	-1	0.2	0	0
x₆	4	0	0	0	0	0	1	1	0	0	0	0	0	-1	0
x₈	0.2	0	0	0	0	-0.2	0	-0.2	1	0	0	0	0.2	0	-1
x₁	4	1	0	0	0	0	0	1	0	0	0	0	0	0	0
x₃	1.2	0	0	1	0	-0.2	0	0.8	0	0	-1	0	0.2	0	0
x₂	0.2	0	1	0	0	-0.2	0	-0.2	0	0	0	0	0.2	0	0
x₉	3.8	0	0	0	0	0.2	0	0.2	0	1	0	0	-0.2	0	0
F(X7)	27.8	0	0	0	0	0.2	0	7.2	0	0	M	M	-0.2+M	M	M

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.

Оптимальный план можно записать так:

x₁ = 4

x₂ = 0.2

F(X) = 7 * 4 -1 * 0.2 = 27.8

Построить двойственную к ней и найти ее решение

1x₁ + 1x₂-1x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ = 3

5x₁ + 1x₂ + 0x₃-1x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ = 5

1x₁ + 5x₂ + 0x₃ + 0x₄-1x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ = 5

1x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅-1x₆ + 0x₇ + 0x₈ + 0x₉ = 0

1x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 1x₇ + 0x₈ + 0x₉ = 4

0x₁ + 1x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇-1x₈ + 0x₉ = 0

0x₁ + 1x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 1x₉ = 4

Введем искусственные переменные x: в 1-м равенстве вводим переменную x₁₀; в 2-м равенстве вводим переменную x₁₁; в 3-м равенстве вводим переменную x₁₂; в 4-м равенстве вводим переменную x₁₃; в 6-м равенстве вводим переменную x₁₄;