Двойственность в Линейном Программировании и Задача 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-мя переменными.