Some issues related with Unified State Examination in Informatics in Russian Federation: May 2018

Friday, May 25, 2018

Двойственность в Линейном Программировании и Задача 18 по Досрочному ЕГЭ Информатика 2018

Найти наибольшее А для всех х1,х2,х3 >=0
(16x1+7x2+6x3+4 > A)v(2x1-4x2+3x3<3)v(4x1+5x2-2x3<8) = 1

Используя двойстенность в ЛП задачу с многими переменными ( >= 3 )
и не более чем двумя дизъюнкциями ( 2 переменных в двойственной задаче) мы сведем к графической задаче Симплекс метода

========================================
Соответствующая задача ЛП имеет вид :-
========================================

Z = 16x1+7x2+6x3+4=> Min1

2x1-4x2+3x3 >= 3
4x1+5x2-2x3 >=8

===========================
Двойственная задача ЛП
===========================
W= 3u1 + 8u2 +4 => Max2

2u1+4u2 <= 16
-4u1+5u2 <= 7
3u1-2u2 <= 6
u1 >=0
u2 >=0

Решается графически смотри :-
http://informatics-ege.blogspot.ru/2018/05/simplex-method-and-task-18-advanced_16.html

============================================================
Теорема. (Первая основная теорема двойственности.) Если одна из двойственных задач имеет оптимальное решение, то двойственная ей задача также имеет оптимальное решение, причем экстремумы целевых функций равны.Если одна из двойственных задач не имеет оптимального решения, то другая задача также не имеет оптимального решения, причем если одна из задач не имеет оптимального решения из-за неограниченности целевой функции, то другая из-за несовместности системы ограничений.
===========================================================
Смотри также https://math.semestr.ru/simplex/lec_dvoistven.php

Необходимо найти максимальное значение целевой функции
F = 3x₁+8x₂+4 → max, при системе ограничений:
2x₁+4x₂≤16, (1)
-4x₁+5x₂≤7, (2)
3x₁-2x₂≤6, (3)
x₁ ≥ 0, (4)
x₂ ≥ 0, (5)

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

Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
2x₁+4x₂=16
-4x₁+5x₂=7
Решив систему уравнений, получим: x₁ = 2, x₂ = 3
Откуда найдем максимальное значение целевой функции:
F(X) = 3*2 + 8*3 + 4 = 34

Min1 = Max2 = 34

Смотри также
https://1cov-edu.ru/lineynoe-programmirovanie/dvoystvennaya-zadacha/reshenie/
Пример 2

Таким образом задачи из ege18-1.pdf

имеющие 2 переменные {x,y} и всего 2 дизъюнкции могут быть обобщены на R^3, R^4, .., R^n , где "n" станет числом ограничений двойственной задачи с 2-мя переменными.

Wednesday, May 23, 2018

Next Sample - Simplex Method and task 18 advanced development for several variables (more then 2)

Найти наименьшее целое А для всех x1,x2,x3 >=0
(4x1-5x2+6x3<A)v(2x1+3x2-4x3>9)v(-x1+3x2+x3>8)v(-2x1-x2+x3<5) = 1

Симплекс-метод.
Решим прямую задачу линейного программирования симплексным методом, 
с использованием симплексной таблицы.
Определим максимальное значение целевой функции 
F(X) = 4x1-5x2+6x3 при следующих условиях-ограничений.

2x1+3x2-4x3≤9
-x1+3x2+x3≤8
-2x1-x2+x3≥5

Для построения первого опорного плана систему неравенств 
приведем к системе уравнений путем введения дополнительных переменных 
(переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. 
В 2-м неравенстве смысла (≤) вводим базисную переменную x5. 
В 3-м неравенстве смысла (≥) вводим базисную переменную x6 со знаком минус.

2x1+3x2-4x3+x4 = 9
-x1+3x2+x3+x5 = 8
-2x1-x2+x3-x6 = 5

Расширенная матрица системы ограничений-равенств данной задачи:
x1 x2 x3 x4 x5 x6 
 2  3 -4  1  0  0 9
-1  3  1  0  1  0 8
-2 -1  1  0  0 -1 5

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x4.
2. В качестве базовой переменной можно выбрать x5.
3. В качестве базовой переменной можно выбрать x6.
Получаем новую матрицу:

x1 x2 x3 x4 x5 x6 B
--------------------
2  3  -4  1  0 0  9
-1 3   1  0  1 0  8
2  1  -1  0  0 1 -5

---------------------
4  -5  6  0  0 0  0
---------------------
Переобразование по Жордану-Гауссу строки целевой функции
----------------------
16 1  0  0  0  0 -30  <= Строка целевой функции

Поскольку в системе имеется единичная матрица, 
то в качестве базисных переменных принимаем X = (4,5,6).
Выразим базисные переменные через остальные:

x4 = -2x1-3x2+4x3+9
x5 = x1-3x2-x3+8
x6 = -2x1-x2+x3-5

Подставим их в целевую функцию:
F(X) = 4x1-5x2+6x3
Среди свободных членов bi имеются отрицательные значения, 
следовательно, полученный базисный план не является опорным.
Вместо переменной x6 следует ввести переменную x3.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис B   x1 x2 x3 x4 x5 x6
x4    29  -6 -1  0 1  0 -4
x5    3    1  4  0 0  1  1
x3    5   -2 -1  1 0  0 -1
F(X0) -30 16  1  0 0  0  6

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

x4 = 6x1+x2+4x6+29
x5 = -x1-4x2-x6+3
x3 = 2x1+x2+x6+5

Подставим их в целевую функцию:
F(X) = 4x1-5x2+6(2x1+x2+x6+5)

или

F(X) = 16x1+x2+6x6+30
-6x1-x2+x4-4x6=29
x1+4x2+x5+x6=3
-2x1-x2+x3-x6=5

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A =  
-6 -1 0 1 0 -4
 1  4 0 0 1  1
-2 -1 1 0 0 -1
 
Базисные переменные это переменные, которые входят только в одно уравнение 
системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x3
Полагая, что свободные переменные равны 0, получим первый опорный план:

X0 = (0,0,5,29,3,0)

Базисное решение называется допустимым, если оно неотрицательно.
Базис  B  x1 x2 x3 x4 x5 x6
x4     29 -6 -1  0  1  0 -4
x5     3   1  4  0  0  1  1
x3     5  -2 -1  1  0  0 -1
F(X0)  0 -16 -1  0  0  0 -6

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся 
отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, 
так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:

min (- , 3 : 1 , - ) = 3

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

Базис B  x1 x2 x3 x4 x5 x6 min
x4    29 -6 -1  0  1 0 -4  -
x5    3   1  4  0  0 1  1  3
x3    5  -2 -1  1  0 0 -1  -
F(X1) 0 -16 -1  0  0 0 -6 0

 4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. 
Вместо переменной x5 в план 1 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 1, 
получена в результате деления всех элементов строки x5 плана 0 н
а разрешающий элемент РЭ=1. На месте разрешающего элемента получаем 1. 
В остальных клетках столбца x1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1. 
Все остальные элементы нового плана 1, включая элементы индексной строки,
определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, 
которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), 
А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:

Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6
x4   47 0  23  0  1  6  2
x1   3  1  4   0  0  1  1
x3   11 0  7   1  0  2  1
F(X1) 48 0 63 0 0 16 10

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

Базис B   x1 x2 x3 x4 x5 x6
x4    47   0 23  0  1  6  2
x1    3    1  4  0  0  1  1
x3    11   0  7  1  0  2  1
F(X2) 48   0 63  0  0  16 10

Оптимальный план можно записать так:
x1 = 3, x2 = 0, x3 = 11
F(X) = 4•3 -5•0 + 6•11 = 78

Monday, May 21, 2018

Simplex Method and task 18 advanced development for several variables (more then 2)

Найти минимальное целое А такое,что для всех неотрицательных х1,х2,х3 
в R^3 имеет место :-

(6x1+5x2+5x3 <A)v(3x1+6x2+4x3>180)v(2x1+x2+2x3>50)v(2x1+3x2+x3>40) = 1
x1 >=0;
x2 >=0;
x3 >=0;
Общая постановка задачи :-

Смотри Википедия Симплекс Метод

Симплекс-метод.
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 6x1+5x2+5x3 при следующих условиях-ограничений.
3x1+6x2+4x3≤180
2x1+x2+2x3≤50
2x1+3x2+x3≤40
Для построения первого опорного плана систему неравенств приведем 
к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. 
В 2-м неравенстве смысла (≤) вводим базисную переменную x5. 
В 3-м неравенстве смысла (≤) вводим базисную переменную x6.

3x1+6x2+4x3+x4 = 180
2x1+x2+2x3+x5 = 50
2x1+3x2+x3+x6 = 40

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

Базисные переменные это переменные, которые входят только в одно 
уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x6
Полагая, что свободные переменные равны 0, получим первый опорный план:

X0 = (0,0,0,180,50,40)

Базисное решение называется допустимым, если оно неотрицательно.
Базис B   x1 x2 x3 x4 x5 x6
x4    180 3  6  4  1  0  0
x5    50  2  1  2  0  1  0
x6    40  2  3  1  0  0  1
F(X0) 0  -6 -5 -5  0  0  0

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке 
находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, 
так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (180 : 3 , 50 : 2 , 40 : 2 ) = 20

Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
Базис B  x1 x2 x3 x4 x5 x6 min
x4   180 3  6  4  1  0  0  60
x5   50  2  1  2  0  1  0  25
x6   40  2  3  1  0  0  1  20
F(X1) 0 -6 -5 -5  0  0  0

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. 
Вместо переменной x6 в план 1 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 1, получена
в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=2.
На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 1, включая элементы индексной строки, 
определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены 
в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (2), 
А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.




Получаем новую симплекс-таблицу:
Базис B   x1 x2   x3  x4 x5 x6
x4    120 0  3/2 5/2  1  0 -3/2
x5    10  0  -2   1   0  1 -1
x1    20  1 3/2  1/2  0  0  1/2
F(X1) 120 0  4   -2   0  0  3

 Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной 
строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, 
так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее:
min (120 : 3/2 , 10 : 1 , 20 : 1/2 ) = 10

 Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис B   x1  x2  x3 x4 x5 x6  min
x4    120  0  3/2 5/2 1 0 -3/2 48
x5    10   0  -2  1   0 1 -1   10
x1    20   1  3/2 1/2 0 0 1/2  40
F(X2) 120 0 4 -2 0 0 3 

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. 
Вместо переменной x5 в план 2 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 2, получена 
в результате деления всех элементов строки x5 плана 1 на разрешающий элемент РЭ=1. 
На месте разрешающего элемента получаем 1. В остальных клетках столбца x3 записываем нули.
Таким образом, в новом плане 2 заполнены строка x3 и столбец x3. 
Все остальные элементы нового плана 2, включая элементы индексной строки, 
определяются по правилу прямоугольника.


Получаем новую симплекс-таблицу:
Базис B  x1  x2  x3 x4 x5  x6
x4    95  0 13/2 0  1 -5/2  1
x3    10  0 -2   1  0  1   -1
x1    15  1  5/2 0  0 -1/2  1
F(X2) 140 0  0   0  0  2    1

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

Базис B  x1  x2 x3 x4  x5 x6
x4    95  0 13/2 0  1 -5/2 1
x3    10  0 -2   1  0   1 -1
x1    15  1 5/2  0  0 -1/2 1
F(X3) 140 0  0   0  0   2  1

Оптимальный план можно записать так:
x1 = 15, x2 = 0, x3 = 10
F(X) = 6•15 + 5•0 + 5•10 = 140

Next Sample - Simplex Method and task 18 advanced development for several variables (more then 2)

Simplex Method and task 18 advanced development for two variables

Симплекс-метод.
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 5x1+4x2 при следующих условиях-ограничений.
6x1+4x2≤24
x1+2x2≤6
-x1+x2≤1
x2≤2
Для построения первого опорного плана систему неравенств приведем к системе 
уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3.
В 2-м неравенстве смысла (≤) вводим базисную переменную x4. 
В 3-м неравенстве смысла (≤) вводим базисную переменную x5. 
В 4-м неравенстве смысла (≤) вводим базисную переменную x6.

6x1+4x2+x3 = 24
x1+2x2+x4 = 6
-x1+x2+x5 = 1
x2+x6 = 2

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

Базисные переменные это переменные, которые входят только в одно 
уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x3, x4, x5, x6
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,24,6,1,2)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6
x3    24 6 4 1 0 0 0
x4    6 1 2 0 1 0 0
x5    1 -1 1 0 0 1 0
x6    2 0 1 0 0 0 1
F(X0) 0 -5 -4 0 0 0 0

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной 
строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, 
так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:

min (24 : 6 , 6 : 1 , - , - ) = 4
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (6) и находится на пересечении 
ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 min
x3    24 6 4 1 0 0 0 4
x4    6 1 2 0 1 0 0 6
x5    1 -1 1 0 0 1 0 -
x6    2 0 1 0 0 0 1 -
F(X1) 0 -5 -4 0 0 0 0 

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 1 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 1, получена в результате деления 
всех элементов строки x3 плана 0 на разрешающий элемент РЭ=6. На месте 
разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1. 
Все остальные элементы нового плана 1, включая элементы индексной строки,
определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в 
вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (6), 
А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6
x1    4 1 2/3 1/6 0 0 0
x4    2 0 4/3 -1/6 1 0 0
x5    5 0 5/3 1/6 0 1 0
x6    2 0 1 0 0 0 1
F(X1) 20 0 -2/3 5/6 0 0 0

Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке 
находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2,
так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (4 : 2/3 , 2 : 4/3 , 5 : 12/3 , 2 : 1 ) =3/2

Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (11/3) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 min
x1    4 1 2/3 1/6 0 0 0 6
x4    2 0 4/3 -1/6 1 0 0 3/2
x5    5 0 5/3 1/6 0 1 0 3
x6    2 0 1 0 0 0 1 2
F(X2) 20 0 -2/3 5/6 0 0 0 

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. 
Вместо переменной x4 в план 2 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 2, получена в результате деления
всех элементов строки x4 плана 1 на разрешающий элемент РЭ=11/3.
На месте разрешающего элемента получаем 1. 
В остальных клетках столбца x2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2. 
Все остальные элементы нового плана 2, включая элементы индексной строки, 
определяются по правилу прямоугольника.

Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6
x1    3 1 0 1/4 -1/2 0 0
x2    3/2 0 1 -1/8 3/4 0 0
x5    5/2 0 0 3/8 -5/4 1 0
x6    1/2 0 0 1/8 -3/4 0 1
F(X2) 21 0 0 3/4 1/2 0 0

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

Базис B x1 x2 x3 x4 x5 x6
x1    3 1 0 1/4 -1/2 0 0
x2    3/2 0 1 -1/8 3/4 0 0
x5    5/2 0 0 3/8 -5/4 1 0
x6    1/2 0 0 1/8 -3/4 0 1
F(X3) 21 0 0 3/4 1/2 0 0

Оптимальный план можно записать так:
x1 = 3, x2 = 3/2
F(X) = 5•3 + 4•3/2 = 21

Simplex Method and task 18 advanced development for limited number of x1,x2, ,x(n)

Изложенная техника будет работать в пространсве R(n) n=3,4,5,....
Таким образом таким образом Задача 18 может легко поставлена для (x1,x2,x3)
Методу изложенному ниже не менее 50 лет, а скорее более

Решим прямую задачу линейного программирования симплексным методом
с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 5x1+4x2
при следующих условиях-ограничений.

6x1+4x2≤24
x1+2x2≤6
-x1+x2≤1
x2≤2
Для построения первого опорного плана систему неравенств приведем

к системе уравнений путем введения дополнительных переменных

(переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3.
В 2-м неравенстве смысла (≤) вводим базисную переменную x4.
В 3-м неравенстве смысла (≤) вводим базисную переменную x5.
В 4-м неравенстве смысла (≤) вводим базисную переменную x6.

6x1+4x2+x3 = 24
x1+2x2+x4 = 6
-x1+x2+x5 = 1
x2+x6 = 2

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

Базисные переменные это переменные, которые входят только в одно уравнение
системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x3, x4, x5, x6
Полагая, что свободные переменные равны 0, получим первый опорный план:

X0 = (0,0,24,6,1,2)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6
x3 24 6 4 1 0 0 0
x4 6  1 2 0 1 0 0
x5 1 -1 1 0 0 1 0
x6 2  0 1 0 0 0 1
F(X0) 0 -5 -4 0 0 0 0

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке
находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1,
так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (24 : 6 , 6 : 1 , - , - ) = 4
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (6) и находится на пересечении
ведущего столбца и ведущей строки.



Базис B x1 x2 x3 x4 x5 x6 min
x3 24 6 4 1 0 0 0 4
x4 6  1 2 0 1 0 0 6
x5 1 -1 1 0 0 1 0 -
x6 2  0 1 0 0 0 1 -
F(X1) 0 -5 -4 0 0 0 0 

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 1
войдет переменная x1.
Строка, соответствующая переменной x1 в плане 1, получена в результате
деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=6.
На месте разрешающего элемента получаем 1. В остальных клетках столбца x1
записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 1, включая элементы индексной строки,
определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые
расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (6),
А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:




Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6
x1    4 1 2/3 1/6 0 0 0
x4    2 0 4/3 -1/6 1 0 0
x5    5 0 5/3 1/6 0 1 0
x6    2 0 1 0 0 0 1
F(X1) 20 0 -2/3 5/6 0 0 0

Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся
отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2,
так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (4 : 2/3 , 2 : 4/3 , 5 : 5/3 , 2 : 1 ) = 3/2
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (4/3) и находится на пересечении ведущего
столбца и ведущей строки.


Базис B x1 x2 x3 x4 x5 x6 min
x1    4 1 2/3 1/6 0 0 0 6
x4    2 0 4/3 -1/6 1 0 0 3/2
x5    5 0 5/3 1/6 0 1 0 3
x6    2 0 1 0 0 0 1 2
F(X2) 20 0 -2/3 5/6 0 0 0 

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 2
войдет переменная x2.
Строка, соответствующая переменной x2 в плане 2, получена в результате&nbsp
деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=11/3.
На месте разрешающего элемента получаем 1. В остальных клетках столбца x2
записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 2, включая элементы индексной строки,
определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6

Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6
x1 3 1 0 1/4 -1/2 0 0
x2 3/2 0 1 -1/8 3/4 0 0
x5 5/2 0 0 3/8 -5/4 1 0
x6 1/2 0 0 1/8 -3/4 0 1
F(X2) 21 0 0 3/4 1/2 0 0
1. Проверка критерия оптимальности. Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:
Базис B x1 x2 x3 x4 x5 x6
x1 3 1 0 1/4 -1/2 0 0
x2 3/2 0 1 -1/8 3/4 0 0
x5 5/2 0 0 3/8 -5/4 1 0
x6 1/2 0 0 1/8 -3/4 0 1
F(X3) 21 0 0 3/4 1/2 0 0
Оптимальный план можно записать так: x1 = 3, x2 = 3/2 F(X) = 5•3 + 4•3/2 = 21

Wednesday, May 16, 2018

Simplex Method and task 18 advanced development

***************************************************************************
Обновление от 01.12.2019
***************************************************************************
Сейчас этот пост имеет 1573 чтений. Примерно
в 10 раз больше, чем другие посты (реально интересные)
говорит это только об одном
Из басни Крылова

Беда, коль пироги начнет печи сапожник,

А сапоги тачать пирожник,

И дело не пойдет на лад.

Да и примечено стократ,

Что кто за ремесло чужое браться любит.

Тот завсегда других упрямей и вздорней:

Он лучше дело все погубит,

. . . . . . . . .

*************************************************************************

Линейная форма на плоскости достигает обоих экстремумов на любом
выпуклом оганиченном N-угольнике,иными словами справа от А (Досрочный ЕГЭ Информатика 2016 задача 18) может быть добавлено разумное количество дизъюнкций, каждое из которых будет добавлять
полуплоскость. Отрицание к каждой из скобок будет определять полуплоскость дополняющую указанную в скобке полуплоскость до всей плоскости,а пересечение полуплоскостей (полученных отрицанием ) выпуклый N-угольник. Скобка, содержащая А определяет линейную форму максимум которой нужно определить. Он и будет совпадать с А.

Видео https://www.youtube.com/watch?v=HEoCopBfU1k

Например : При x >=0 ; y>=0 найти A(min)
(5x+4y<A)v(6x+4y>24)v(x+2y>6)v(y>2)v(y-x>1) = 1
для всех (x,y) на плоскости

Рассмотрим решение приведенного примера симплекс методом
Остается обозначить направляющий вектор целевой формы и провести прямые, перпендикулярные к нему от -infinity to +infinity.

Симплекс метод для пространства любой размерности R(n) применен в той
же ситуации. Нетрудно видет, что руками это сделать не просто даже
для модельной задачи
Simplex Method and task 18 for limited number of x1,x2, ,x(n)

Tuesday, May 15, 2018

Solution for system from BU's Stream Queue as of 15/05/2018 via Mapping Method

((x1^y1) = (x2^y2)) => (x3^y3) = 0
((x2^y2) v ¬(x3^y3)) => (x4^y4) = 0
((x3^y3) = (x4^y4)) => (x5^y5) = 0
((x4^y4) v ¬(x5^y5)) => (x6^y6) = 0

zj=xj^yJ

(z1 = z2) => z3 =0
(z2 v ¬z3) => z4 =0
(z3 = z4) => z5 =0
(z4 v ¬Z5) => z6 =0

Friday, May 11, 2018

Solution System №129 & 116 & 156 from ege23.pdf via Mapping Method as of 11/05 2018

   (x1 => y1)^((x2 v y2) => (x1=y1)) =1
   (x2 => y2)^((x3 v y3) => (x2=y2)) =1
   (x3 => y3)^((x4 v y4) => (x3=y3)) =1
   (x4 => y4)^((x5 v y5) => (x4=y4)) =1
   (x5 => y5)^((x6 v y6) => (x5=y5)) =1
   (x6 => y6)^((x7 v y7) => (x6=y6)) =1
   x7=y7

(x1 v y1)^((x1^y1) v (!x2 v !y2)) =1
(x2 v y2)^((x2^y2) v (!x3 v !y3)) =1
(x3 v y3)^((x3^y3) v (!x4 v !y4)) =1
(x4 v y4)^((x4^y4) v (!x5 v !y5)) =1
(x5 v y5)^((x5^y5) v (!x6 v !y6)) =1
x6 v y6=1

Equations (1) && (4) set values "01" and "10" of column 1 to zeros

((x1=x2)v(x3=x4))^(¬((x1=x2) => (x3=x4))) =1

((x5=x6)v(x3=x4))^(¬((x5=x6) => (x3=x4))) =1

((x5=x6)v(x7=x8))^(¬((x5=x6) => (x7=x8))) =1
((x1=x2)v(x7=x8))^(¬((x1=x2) => (x7=x8))) =1
(x9=x10)

Monday, May 7, 2018

Solution for system from BU's Stream Queue as of 07/05/2018 via Mapping Method

(x1vy1)^(x2^y2) => (x1^y1) =1
(x2vy2)^(x3^y3) => (x2^y2) =1
(x3vy3)^(x4^y4) => (x3^y3) =1
(x4vy4)^(x5^y5) => (x4^y4) =1
(x5vy5)^(x6^y6) => (x5^y5) =1
(x6vy6)^(x7^y7) => (x6^y6) =1
x7vy7=1

Thursday, May 3, 2018

Conversion decimal to binary in Pascal (fpc Fedora 27) or how much power provides recursion in Pascal

[boris@fedora27workstation PASCAL]$ cat ConvDecBin.pas
program ConvDecBin;

procedure Dec2Bin(var sbin : string; NUMBER : integer);
begin
    if NUMBER > 0 then begin
        Dec2Bin(sbin, NUMBER div 2);
        if NUMBER mod 2 = 0 then
            sbin := sbin + '0'
        else
            sbin := sbin + '1';
    end;
end;

var
j : integer;
s : string;

begin
read(j);
Dec2Bin(s,j);
writeln(s);
end.
[boris@fedora27workstation PASCAL]$ fpc -oConvDecBin.exe ConvDecBin.pas
Free Pascal Compiler version 3.0.2 [2018/03/14] for x86_64
Copyright (c) 1993-2017 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling ConvDecBin.pas
Linking ConvDecBin.exe
/usr/bin/ld: warning: link.res contains output sections; did you forget -T?
22 lines compiled, 0.1 sec
[boris@fedora27workstation PASCAL]$ ./ConvDecBin.exe
285
100011101

Tuesday, May 1, 2018

Switching fork diagrams and Mapping Metod for system per request 01/05/2018 (BU's Queue picked up)

System :-

(x1 => x2) v (x2 =>x1)^x3 =1
x2 v x3 v (x2^x3 => x4 ) =1
(x3 => x4) v (x4 =>x3)^x5 =1
x4 v x5 v (x4^x5 => x6) =1
(x5 => x6) v (x6 =>x5)^x7 =1
x6 v x7 v (x6^x7 => x8) =1