1

Нужно решить ЗЛП графичиским методом, а точнее написать программу по аналогии.

Задание:

введите сюда описание изображения

При програмировании возникло несколько проблем:

После подставновки x1 и x2 некоторых значений мы получаем координаты 3 прямых + их направления. Находим точки пересечения прямых. Они и направления будут формировать ОДЗ.

После нужно провести градиент, в моем случае это будет (2;1) и от него искать максимум. Но как это сделать в программе ?

4
  • 3
    "Как найти пересечение двух прямых?" - решить систему из двух линейных уравнений с двумя неизвестными.
    – user176262
    27 фев 2017 в 17:34
  • 1
    расшифруйте кто-нибудь ЗЛП и ОДЗ
    – Grundy
    28 фев 2017 в 11:26
  • @Grundy: ОДЗ — это, видимо, область допустимых значений, а вот что означает ЗЛП, у меня версий нет.
    – VladD
    28 фев 2017 в 11:50
  • @VladD, у меня только Задача Линейного Программирования версия, но мне кажется она не совсем подходит
    – Grundy
    28 фев 2017 в 11:51

1 ответ 1

2

Графический метод решения ЗЛП основан на построении выпуклого многоугольника (симплекса), полностью лежащего в первом квадранте. Начальным приближением является весь первый квадрант, т.е. треугольник с вершинами (0,0), (Inf,0), (0, Inf), где Inf - бесконечность, которую нужно "отрезать".

Идеальный вариант для "отрезания" - неравенство вида ax1 + bx2 <= c, (a>0, b>0, c>0), которое ликвидирует обе сингулярных вершины. В данном случае такого неравенства нет, но есть первое неравенство (a1>0, c1>0), и второе неравенство, которое после умножения на "-1" даёт (b2>0, c2>0), причём точка пересечения M(x,y) соответствующих им прямых лежит в первом квадранте. Это значит, что получен симплекс с вершинами (0,0), (c1/a1,0), (x,y), (0,c2/a2). Вершины следуют в циклическом порядке против часовой стрелки, в таком же порядке их следует хранить.

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.