Графичен метод - линейното програмиране

Описание на метода

Ако има само две променливи в линейното програмиране проблем, тогава той може да бъде решен с графични методи.

Да разгледаме проблема с линейното програмиране с две променливи и.






(1.1);
(1.2)
Тук. там са произволни числа. Тази цел може да бъде или да намери максималната (макс), и определяне на минималната (мин). системата от ограничения могат да присъстват като знаци. и знаци.

Зоната за изграждане на възможни решения

Графичен метод за решаване на проблема (1), както следва.
На първо място, ние прекарваме осите и и изберете скалата. Всяка от ограниченията на системата на неравенство (1.2) определя времето на равнината, определена от съответния права линия.

Така че, първото неравенство
(1.2.1)
Той определя полуравнина, ограничена от линиите. От едната страна на тази линия. и от другата страна. В много директен. За да разберете коя страна на неравенството (1.2.1), ние избираме произволна точка не по линията. На следващо място, заместваме координатите на тази точка (1.2.1). Ако неравенството е изпълнено, половината равнина съдържа избраната точка. Ако неравенството не е изпълнено, половината равнина се намира от другата страна (не съдържащ избраната точка). Half-сянка, за които неравенството (1.2.1).

Същото се извършва за останалата част от системата на неравенство (1.2). Така че ние се сенчестата полуравнина. възможни точки разтвори площ отговарят на всички неравенства (1.2). Следователно, графично, областта на възможни решения (SDT) е пресечната точка на всички изградени от половин равнини. SDT сянка. Това е изпъкнал многоъгълник чиито лица принадлежат построен право. SDT също може да бъде неограничен изпъкнала фигура сегмент лъчи, или линия.

Тя може да възникне такъв случай, че времето на самолета няма общи точки. Тогава областта на изпълними решения е празен. Такъв проблем няма решение.

Възможно е да се опрости метод. Не може да има засенчване на всеки половин самолет, и първият за изграждане на всички преки
(2)
След това изберете произволна точка, не принадлежи на някоя от тези линии. Замести координатите на тази точка в системата на неравенство (1.2). Ако всички неравенства са изпълнени, а след това на зоната за изпълнение е ограничена вградена и включва избраната точка. Shade зоната за изпълнение на преки граници, така че да включва избраната точка.

Ако някоя условие не е изпълнено, а след това изберете друга точка. И така нататък, докато се намери точка с координати, които удовлетворяват (1.2).

Намирането на екстремум на целевата функция

Така че ние имаме сенчести места на изпълними решения (СДТ). Тя е ограничена от многоъгълно линия принадлежност конструирани прави линии и състояща се от греди (2). SDT винаги е изпъкнал. Тя може да бъде ограничена серия, а не ограничен в някои направления.

Сега ние можем да погледнем за екстремум на целевата функция
(1.1).

За да направите това, изберете произволен брой и изграждане на пряка
(3).
За по-голямо удобство по-нататък ние вярваме, че тази линия преминава през тунела за вторично разреждане. На тази линия на целевата функция е постоянна и равна. тази линия се нарича функциите на линейни нива. Тази линия разделя равнината на две половини равнини. От една полуравнина
.
От друга полуравнина
.
Това е от едната страна на линията (3) обективната функция увеличава. И колкото по-otodvinem точка от линията (3), толкова по-голяма стойност. От другата страна на линията (3) обективната функция намалява. И колкото по-otodvinem точка от линията (3) в другата посока, толкова по-малка стойност. Ако се направи линия, успоредна на линията (3), новата линия също ще насочи нивото на целевата функция, но с различна стойност.

По този начин, да се намери максималната стойност на обективната функция, е необходимо да се направи по права линия, успоредна на линия (3), максималното разстояние от него в посока на увеличаване стойности. и простиращ се през най-малко една точка на SDT. За минималната стойност на обективната функция, е необходимо да се направи по права линия, успоредна на линията (3) и максимално разстояние от него в посока на намаляване на стойностите. и простиращ се през най-малко една точка на SDT.

Ако SDT е неограничен, може да има случай, в права линия не може да побере. Това означава, че независимо от това колко сме били извадени директно от нивото на линията (3) в посока на увеличаване (намаляване). След това линията винаги ще премине през тунела за вторично разреждане. В този случай може да бъде произволно голям (малък). Затова максималната (минимум) стойността на никой. вземане на проблема не го прави.

Да разгледаме случая, когато крайната линия, успоредна на всяка линия на формата (3), преминава през един от върховете на SDT на многоъгълник. От графиката се определяме координатите на върховете. Тогава максимум (минимум) стойността на целевата функция се изчислява по формулата:






.
решение на проблема е
.

Тя може също да се срещне случаят, когато линията е успоредна на една от стените на тунела за вторично разреждане. След това линията минава през два върха на SDT полигон. И определя координатите на тези върхове. За да се определи максимална (минимална) стойност на целевата функция, е възможно да се използва някоя от тези координати на върховете:
.
Проблем има безкрайно много решения. Решението е да се намира всяка точка на отсечката между точките и. включително точките себе си и.

Пример за решаване на проблема с метод линейното програмиране графично

състояние проблем

Фирмата произвежда дрехи два модела А и Б. Използването на три вида тъкан. При производството на модел облича изисква 2 m на първия вид на тъкан, тъканта 1 m от втория вид, 2m трети тип тъкан. При производството на модел дрехи се изисква в тъканта 3 m от първи вид, т милионсекунди плат форма 2 m трети тип тъкан. Запасите от първия вид тъкан е 21 m, а вторият вид - 10 м, трети тип -. 16 m Брой един вид продукт А генерира доход 400 ден. ф един продукт тип В - 300 ден. ф

Създаване на производствения план, който осигурява на компанията най-много приходи. Проблемът, решен от графични методи.

Нека променливите и средства в размер на рокли модели А и Б, съответно. След това сумата, изразходвана от първи тип тъкан е:
(М)
Използваният обем на втория тип тъкан е:
(М)
Използваният обем от трети вид на плат ще бъде:
(М)
Тъй като количеството на произведени рокли не може да е отрицателна, а след това
и.
ще бъде направена Приходите от таксата:
(Den. Единици).

След икономическата и математическия модел на проблема е, както следва:

Ние решаваме графичния метод.
Начертайте координатна ос.

Изграждане на права линия.
Когато.
Когато.
Равен права линия през точката (0; 7) и (10,5, 0).

Изграждане на права линия.
Когато.
Когато.
Равен права линия през точката (0; 10) и (10, 0).

Изграждане на права линия.
Когато.
Когато.
Начертайте права линия през точките (0, 8) и (8, 0).

Директен и са координатни оси.

ОБЛАСТ приложими разтвори (SDT) е ограничена от линии конструирани и координатните оси. За да разберете коя страна, ние виждаме, че точката принадлежи на SDT, тъй като отговаря на системата на неравенството:

Shade зона до точката (2, 2) удари излюпени част. Получаваме четириъгълник OABC.

Изграждане на произволно ниво линия на целевата функция, например,
(А1.1).
Когато.
Когато.
Равен права линия през точката (0, 4) и (3, 0).

Освен това ние се отбележи, че тъй като коефициентите на положителните и целевата функция (400 и 300), като увеличава с ф. Права линия е успоредна на линията (A1.1) Максималното разстояние от него в посока на увеличаване. и простиращ се през най-малко една точка на четириъгълник OABC. Такава права линия минава през точка С. От изграждането определят нейните координати.
.

Това е, за да печелят най-много приходи, трябва да се направи рокли 8 Модел А. След това приходите ще достигне 3200 бърлога. ф

състояние проблем

За решаването на линейни програмни проблеми с графичните методи.

Ние решаваме графичния метод.
Начертайте координатна ос.

Изграждане на права линия.
Когато.
Когато.
Равен права линия през точките (0, 6) и (6 0).

Изграждане на права линия.
Тук.
Когато.
Когато.
Равен права линия през точката (3, 0) и (7, 2).

Изграждане на права линия.
Изграждане на права линия (х-ос).

ОБЛАСТ приложими разтвори (SDT) е ограничена конструирана права. За да разберете коя страна, ние виждаме, че точката принадлежи на SDT, тъй като отговаря на системата на неравенството:

Засенчване площ на граници конструирани прави линии до точка (4; 1) удари излюпени част. Качваме се на триъгълника ABC.

Изграждане на произволно ниво линия на целевата функция, например,
.
Когато.
Когато.
Равен права линия чрез нивото на точката (0, 6) и (4 0).
Тъй обективната функция увеличава с и. черпим линия, успоредна на ниво договорена и максималното разстояние от нея в посока на увеличаване. и разширяване чрез най-малко една точка на триъгълника AVC. Такава права линия минава през точка С. От изграждането определят нейните координати.
.

Един пример за липсата на разтвори

състояние проблем

Решете Задачата на линейното програмиране графично. Намерете максималната и минималната стойност на целевата функция.

Ние реши проблема на графичния метод.
Начертайте координатна ос.

Изграждане на права линия.
Когато.
Когато.
Начертайте права линия през точките (0, 8) и (2.667, 0).

Изграждане на права линия.
Когато.
Когато.
Равен права линия през точките (0, 3) и (6 0).

Изграждане на права линия.
Когато.
Когато.
Равен права линия през точката (3, 0) и (6, 3).

Директен и са координатни оси.

ОБЛАСТ приложими разтвори (SDT) е ограничена от линии конструирани и координатните оси. За да разберете коя страна, ние виждаме, че точката принадлежи на SDT, тъй като отговаря на системата на неравенството:

Сянка зона до точката (3, 3) се избутва в защрихованата част. Вземи неограничен домейн, ограничена от линия ABCDE счупената.

Изграждане на произволно ниво линия на целевата функция, например,
(A3.1).
Когато.
Когато.
Начертайте права линия през точките (0, 7) и (7, 0).
Тъй като коефициентите за положителен, а след това се увеличава с увеличаване и.

За да намерите максималната, което трябва да направим паралел линия, най-отдалечените в посока на увеличаване. и простиращ се през най-малко една точка на ABCDE на областта. Въпреки това, тъй като районът е неограничен от високите стойности и. че такова поведение не може да бъде прав. Каквато и да е линия, ние не са извършили, винаги ще има площта на една точка по-далечен по посока на увеличаване и. Ето защо, няма максимум. Това може да се направи произволно голям.

Търсим най-малко. Права линия е успоредна на линията (A3.1) и най-отдалечените от него в посока на намаляване. и простиращ се през най-малко една точка на ABCDE на областта. Такава права линия минава през точка С. От изграждането определят нейните координати.
.
Минималната стойност на целевата функция:

Максималната стойност не съществува.
минимална стойност
.