Линейным программированием называется раздел математики, в котором изучаются методы нахождения минимума или максимума линейной функции конечного числа переменных, при условии, что переменные удовлетворяют конечному числу ограничений, имеющих вид линейных уравнений или линейных неравенств.

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

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

принимает минимальное значение на множестве точек, координаты которых удовлетворяют системе ограничений

Как известно, упорядоченная совокупность значений n переменных , , … представляется точкой n-мерного пространства . В дальнейшем эту точку будем обозначать Х =( , , … ).

В матричном виде задачу линейного программирования можно сформулировать так:

, A – матрица размера ,

Точка Х =( , , … ), удовлетворяющая всем условиям, называется допустимой точкой . Множество всех допустимых точек называется допустимой областью .

Оптимальным решением (оптимальным планом) задачи линейного программирования называется решение Х =( , , … ), принадлежащее допустимой области и при котором линейная функция Q принимает оптимальное (максимальное или минимальное) значение.

Теорема . Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

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

Точка Х называется выпуклой линейной комбинацией точек если выполняются условия

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

Теорема . Если ЗЛП имеет оптимальное решение, то целевая функция принимает максимальное (минимальное) значение в одной из вершин многогранника решений. Если целевая функция принимает максимальное (минимальное) значение более чем в одной точке, то она принимает это значение в любой точке, являющейся выпуклой линейной комбинацией этих точек.

Среди множества решений системы m линейных уравнений, описывающих многогранник решений, выделяют так называемые базисные решения.

Базисным решением системы m линейных уравнений с n переменными называется решение, в котором все n-m неосновных переменных равны нулю. В задачах линейного программирования такие решения называют допустимыми базисными решениями (опорными планами).

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

Из приведенных теорем вытекает важное следствие:

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

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

Общая задача линейного программирования (ОЗЛП) формулируется следующим образом – найти переменные задачи x 1 , x 2 , ..., x n , которые обеспечивают экстремум целевой функции

Допустимым решением (планом) задачи линейного программирования (ЗЛП) называется любой n -мерный вектор X =(x 1 , x 2 , ..., x n), удовлетворяющий системе ограничений равенств и неравенств. Множество допустимых решений задачи образует область допустимых решений D .

Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение, при котором целевая функция Z (X ) достигает экстремума.

Каноническая задача линейного программирования (КЗЛП) имеет вид

(1.2)

Она отличается от ОЗЛП тем, что её система ограничений является системой только уравнений и все переменные неотрицательные.

Приведение ОЗЛП к каноническому виду ЗЛП:

Чтобы заменить исходную задачу минимизации на задачу максимизации (или наоборот задачу максимизации на задачу минимизации) достаточно целевую функцию умножить на «-1» и искать максимум (минимум) полученной функции;

Если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных x n +1 ≥ 0 они преобразуются в равенства:

неравенство a i 1 x 1 +…+a in x n ≥ b i заменяется на равенство a i 1 x 1 +…+a in x n + x n +1 = b i ,

неравенство a i 1 x 1 +…+a in x n ≤ b i заменяется на равенство a i 1 x 1 +…+a in x n + x n +1 = b i ;

Если некоторая переменная x k не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательны-ми переменными: x k = x " k – x ” k , где x " k ≥ 0. x ” k ≥ 0.

Графический метод решения ЗЛП с двумя неизвестными

ЗЛП с двумя неизвестными имеет вид:

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

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

Областью решения неравенства a i 1 x 1 +a i 2 x 2 ≤ b i является одна из двух полуплоскостей, на которые прямая a i 1 x 1 +a i 2 x 2 = b i , соответствующая этому неравенству, делит координатную плоскость. Чтобы определить, какая из двух полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на разделяющей прямой подставить в неравенство:

Если неравенство справедливо, то областью решений является полуплоскость, содержащая эту точку;

Если неравенство не справедливо, то областью решений является полуплоскость, не содержащая эту точку.

Для нахождения среди допустимых решений оптимального используются линии уровня.

Линией уровня называется прямая с 1 x 1 +с 2 x 2 = l , где l = const, на которой целевая функция задачи принимает постоянное значение. Все линии уровня параллельны между собой.

Градиент целевой функции grad Z (X ) задает вектор нормали C = (c 1 , c 2) линий уровня. Целевая функция на линиях уровня возрастает, если линии уровня перемещать в направлении их нормали, и убывает – в противоположном направлении.

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

Оптимальное решение ЗЛП лежит на опорной прямой в угловой точке многоугольника ОДР. ЗЛП имеет единственное решение, если опорная прямая проходит через одну угловую точку ОДР, бесконечное множество решений, если опорная прямая проходит через ребро многоугольника ОДР. ЗЛП не имеет решения, если ОДР является пустым множеством (когда система ограничений несовместна) и если ОДР неограниченна в направлении экстремума (целевая функция неограниченна).

Алгоритм графического метода решения ЗЛП с двумя неизвестными:

Построить ОДР.

Построить вектор нормали C = (c 1 , c 2) и линию уровня с 1 x 1 +с 2 x 2 = 0, проходящую через начало координат и перпендикулярную вектору С .

Передвигать линию уровня до опорной прямой в направлении вектора С в задаче на max, или в противоположном направлении – в задаче на min.

Если при перемещении линии уровня в направлении экстремума ОДР уходит в бесконечность, то ЗЛП не имеет решения ввиду неограниченности целевой функции.

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

Вычислить значение целевой функции в точке экстремума.

Симплекс-метод решения ЗЛП

Симплекс-метод основывается на следующих положениях:

ОДР задачи линейного программирования является выпуклым множеством с конечным числом угловых точек;

Оптимальным решением ЗЛП является одна из угловых точек ОДР. Угловые точки ОДР алгебраически представляют некоторые базисные (опорные) решения системы ограничений ЗЛП.

Базисным (опорным) решением ЗЛП называется такое допустимое решение X 0 =( x 10 , x 20 , ..., x m 0 , 0,…0), для которого векторы условий (столбцы коэффициентов при неизвестных в системе ограничений) линейно независимы.

Ненулевые координаты x 10 , x 20 , ..., x m 0 решения X 0 называются базисными переменными, оставшиеся координаты решения X 0 - свободными переменными. Число отличных от нуля координат опорного решения не может быть больше ранга r системы ограничений ЗЛП (числа линейно независимых уравнений в системе ограничений ЗЛП). Далее считаем, что система ограничений ЗЛП состоит из линейно независимых уравнений, т.е. r = m .

Смысл симплекс-метода заключается в целенаправленном переходе от одного опорного решения ЗЛП к другому (т.е. от одной угловой точки ОДР к другой) в направлении экстремума и состоит в последовательности этапов:

Найти начальное опорное решение;

Осуществить переход от одного опорного решения к другому;

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

Алгоритм выполнения Симплекс-метода ЗЛП

Алгоритм симплекс-метода осуществляет переход от одного опорного решения ЗЛП к другому в направлении экстремума целевой функции.

Пусть ЗЛП задана в каноническом виде (1.2) и выполнено условие

b i ≥ 0, i =1,2,…,m , (1.3)

соотношение (1.3) всегда можно выполнить, домножив соответствующее уравнение на «-1» в случае отрицательности b i . Также считаем, что система уравнений в ограничениях задачи (1.2) линейно независима и имеет ранг r = m . При этом вектор опорного решения имеет m ненулевых координат.

Пусть исходная задача (1.2), (1.3) приведена к виду, где базисные переменные x 1 , x 2 , ..., x m выражены через свободные переменные x m + 1 , x m + 2 , ..., x n

(1.4)

На основе этих соотношений построим таблицу 1

Таблица 1.

Таблица 1 называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменениями содержания этой таблицы.

Алгоритм с имплекс-метода :

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

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

3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

4. Если имеется несколько одинаковых по величине симплекс - отношений, то выбирают любое из них. То же самое относится к положительным элементам последней строки симлекс - таблицы.

5. После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Симплекс - таблица преобразуется следующим образом (таблица 2):

Таблица 2

6. Элемент таблицы 2, соответствующий разрешающему элементу таблицы 1, равен обратной величине разрешающего элемента.

7. Элементы строки таблицы 2, соответствующие элементам разрешающей строки таблицы 1, получаются путем деления соответствующих элементов таблицы 1 на разрешающий элемент.

8. Элементы столбца таблицы 2, соответствующие элементам раз­решающего столбца таблицы 1, получаются путем деления соответствующих элементов таблицы 1 на разрешающий элемент и берутся с противоположным знаком.

9. Остальные элементы вычисляются по правилу прямоугольника : мысленно вычерчиваем прямоугольник в таблице 1, одна вершина которого совпадает с разрешающим элементом (Рэ), а другая – с элементом, который мы ищем; обозначим элемент в новой таблице 2 через (Нэ), а элемент, стоящий на этом же месте в старой таблице 1 – через (Сэ). Остальные две вершины А и В дополняют фигуру до прямоугольника. Тогда искомый элемент Нэ из таблицы 2 равен Нэ = Сэ – А*В/Рэ.

10. Критерий оптимальности. Как только получится таблица, у которой в последней строке в задаче на min все элементы отрицательны (в задаче на max все элементы положительны), считается, что экстремум найден. Оптимальное значение целевой функции равно свободному члену в строке Z, а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные полагаются равными нулю.

11.Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается).

Метод искусственного базиса решения ЗЛП

Алгоритм симплекс-метода применим, если выделено какое-либо опорное решение ЗЛП, т. е, исходная ЗЛП (1.2) приведена к виду (1.4). Метод искусственного базиса предлагает процедуру построения такого опорного решения.

Метод искусственного базисаоснован на введении искусственных базисных переменных y 1 , y 2 ,…, y m , с помощью которых система ограничений ЗЛП (2.2)

(1.5)

может быть преобразована к виду

(1.6)

Системы (1.5) и (1.6) будут эквивалентны в том случае, если все y i будут равны нулю. Как и раньше мы считаем, что все b i ≥ 0. Для того чтобы у i были равны 0, мы должны преобразовать задачу таким образом, чтобы все искусственные базисные переменные y i перешли в свободные переменные. Такой переход можно сделать алгоритмом симплекс метода относительно дополнительной целевой функции

F (y ) = y 1 + y 2 + ... + y m = d 0 – (d 1 x 1 + d 2 x 2 +…+d n x n). (2.7)

Исходная симплекс таблица для данного метода имеет вид

Сначала симплекс таблица преобразуется относительно целевой функции F (y ) до получения опорного решения. Опорное решение найдено, когда выполнен следующий критерий: F (y ) = 0 и все искусственные переменные у i переведены в свободные переменные. Затем из симплекс таблицы вычеркивается строка для F (y ) и столбцы для у i и решают задачу для исходной целевой функции Z (x ) до получения оптимального решения.

Это решения руководителя, которые обеспечивают максимальную степень достижения цели управления. Другими словами, оптимальные решения - это наилучшие компромиссы, найденные в результате тщательного анализа и сравнения всех альтернатив. Хорошо известно, что любое управленческое решение кроме полезного эффекта имеет и негативные последствия. Поиск разумного или наилучшего компромисса между ними и составляет суть процесса принятия решения.
При этом каждой альтернативе явно или неявно приписывается некоторая полезность, которая субъективно оценивается человеком исходя из его системы предпочтений, и означает степень предпочтительности данной альтернативы с учетом всех возможных последствий. Поэтому поиск оптимальных решений соответствует классической концепции максимизации полезности, которая требует исследования всего множества альтернатив, их оценивания и выбора наи-лучшей, даже если удовлетворительное решение уже давно найдено. Такой подход имеет смысл, если ожидаемый эффект оправдывает затраты ресурсов и времени на поиск самого решения.
Наряду с рассмотренными выше существуют и другие признаки классификации управленческих решений. Например, по признаку инновационности рассматривают рутинные, селективные, адаптационные и инновационные решения.
По уровню творческого вклада некоторые авторы выделяют решения 4 уровней: рутинные, селективные, адаптивные и инновационные.
Уровень первый: рутинный. Рутинные решения - это хорошо известные способы действий для разрешения возникшей проблемы. Они представляют собой лишь стандартную реакцию на типовую ситуацию и по сути своей решениями не являются. Эти решения представляют собой часть обычной рутины. Здесь руководитель ведет себя в соответствии с имеющейся программой, почти как автомат, распознающий ситуации и поступающий по заранее заданной программе. Трудности здесь могут возникнуть, если руководитель не обладает чутьем, неверно трактует имеющиеся указания на ту или иную ситуацию, действует нелогично, принимает ошибочные решения, или проявляет нерешительность, или вовсе не может обеспечить эффективные действия в нужное время. Руководитель, правильно воспринимающий ситуацию, делающий верные выводы и разумно действующий, добивается того, чего от него ждут. На этом уровне не требуется творческого подхода, поскольку все процедуры заранее предписаны.
Уровень второй: селективный. Селективные решения предполагают выбор одной альтернативы из определенного набора способов действий. В этом случае предполагается, что множество альтернатив задано и хорошо известно лицу, принимающему решение. От него требуется всего лишь выбрать одну из них. На этом уровне требуется доля инициативы и свободы действий, однако в определенных границах. Здесь руководитель оценивает достоинства целого круга возможных решений и старается выбрать из некоторого числа хорошо отработанных альтернативных наборов действий те, которые лучше всего под-
ходят к данной проблеме. Результативность зависит от способности руководителя выбрать направление действий с максимальной вероятностью, что оно окажется приемлемым, экономичным и эффективным.
Уровень третий: адаптационный. Адаптивные решения принимаются в условиях, когда ситуация изменяется и поэтому требуется некоторая модификация известных вариантов с учетом особенностей новой ситуации. На этом уровне встречаются дополнительные трудности, так как здесь руководитель должен выработать творческое решение, которое в определенном смысле может быть абсолютно новым. Обычно здесь имеются набор проверенных возможностей и некоторые новые идеи. Успех руководителя зависит от его личной инициативности и способности сделать прорыв в неизвестное. Подобные решения дают ответ на проблемы, которые могли существовать и ранее, но в иной конкретной форме. Руководитель ищет новое решение известной проблемы.
Уровенъ четвертый: инновационный. Наиболее сложными являются инновационные решения, которые принимаются в условиях, когда проблема не может быть решена с помощью известных способов действий или их модификаций и требует разработки принципиально новых решений, не используемых ранее. Эти проблемы наиболее сложны и требуют наибольшего внимания среди всех, с которыми сталкивается менеджер. Для того чтобы добиться удовлетворительного результата, они требуют совершенно нового подхода. Зачастую такой проблемой может быть та, которую плохо поняли ранее, и для ее решения требуются абсолютно новые представления и методы. Руководителю необходимо найти способы принимать совершенно неожиданные и непредсказуемые проблемы, решение которых зачастую требует развития в себе способности мыслить на новый манер. Наиболее современные и трудные проблемы могут потребовать для их решения создавать новые приемы и технологии.
Виды решений по уровню творческого вклада менеджера
Таблица 1.2 Уровень творческого вклада Вид
решения Необходимые профессиональные умения менеджеров Первый Рутинный Неукоснительное следование про-цедуре
Разумная оценка ситуации
Гуманное лидерство
Контроль/мотивация В табл. 1.2 объединяются четыре уровня принятия решений и ключевые навыки, требующиеся соответствующему руководителю. Руководителям, работающим над принятием решений высокого уровня, требуются навыки и более низкого уровня. Например, менеджеру, работающему на уровне 3 (адаптационные решения), требуются навыки не только этого уровня, но также и уровней 1 и 2.
Окончание табл. 1.2 Уровень творческого вклада Вид
решения Необходимые профессиональные умения менеджеров Второй Селективный Установление целей
Планирование
Анализ/развитие
Анализ информации Третий Адаптационный Идентификация проблемы
Систематизированное решение про-блем
Создание рабочих групп
Анализ возможного риска Четвертый Инновационный Творческое управление
Стратегическое планирование
Системное развитие
По масштабу изменений, вносимых в организацию, управленческие решения могут быть разделены на ситуационные и реорганизационные.

Еще по теме Оптимальные решения:

1. Территориальный подход при решении природоохранных проблем
2. 3.1. Место и роль экономического анализа в управлении предприятием. Экономический анализ как база обоснования и принятия управленческих решений

Следует отметить, что методы решения задач линейного программирования относятся не к экономике, а к математике и вычислительной технике. При этом экономисту нужно обеспечить максимально комфортные условия диалога с соответствующим программным обеспечением. В свою очередь такие условия могут обеспечивать только динамично развивающиеся и интерактивные среды разработки, имеющие в своём арсенале набор необходимых для решения таких задач библиотек. Одной из каких сред разработки программного обеспечения безусловно является Python.

Постановка задачи

В публикациях рассматривались решения прямых задач оптимизации методом линейного программирования и был предложен обоснованный выбор решателя scipy. optimize.

Однако известно , что каждой задаче линейного программирования соответствует так называемая выделенная(двойственная)задача. В ней по сравнению с прямой задачей строки переходят в столбцы, неравенства меняют знак, вместо максимума ищется минимум (или наоборот, вместо минимума - максимум). Задача, двойственная к двойственной - эта сама исходная задача.

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

Оптимальные значения стоимости материала и труда будут оцениваться по их вкладу в целевую функцию. В результате будут получены «объективно обусловленные оценки» сырья и рабочей силы, которые не совпадают с рыночными ценами.

Решение прямой задачи о оптимальной производственной программе

Учитывая высокий уровень математической подготовки подавляющего большинства пользователей данного ресурса не стану приводить балансовые уравнения с верхними и нижними ограничениями и введением для перехода к равенствам дополнительных переменных. Поэтому сразу приведу обозначения используемых в решении переменных:
N – количество видов производимых изделий;
m– количество видов используемого сырья;
b_ub - вектор имеющихся ресурсов размерности m;
A_ub – матрица размерности m×N, каждый элемент которой является расходом ресурса вида i на производство единицы изделия вида j;
с - вектор прибыли от производства единицы изделия каждого вида;
x – искомые объёмы производимых изделий каждого вида (оптимальный план производства) обеспечивающие максимальную прибыль.

Функция цели
maxF(x)=c×x

Ограничения
A×x≤b

Численные значения переменных:
N=5; m=4; b_ub = ; A_ub = [, , ,]; c = .

Задачи
1.Найти x для обеспечения максимальной прибыли
2. Найти использованные ресурсы при выполнении п.1
3. Найти остатки ресурсов (если они есть) при выполнении п.1

Для определения максимума (по умолчанию определяется минимум коэффициенты целевой функции нужно записать с отрицательным знаком c = [-25, -35,-25,-40,-30] и проигнорировать знак минус перед прибылью.

Используемые при выводе результатов обозначения:
x – массив значений переменных, доставляющих минимум (максимум) целевой функции;
slack – значения дополнительных переменных. Каждая переменная соответствует ограничению-неравенству. Нулевое значение переменной означает, что соответствующее ограничение активно;
success – True, если функции удалось найти оптимальное решение;
status – статус решения:
0 – поиск оптимального решения завершился успешно;
1 – достигнут лимит на число итераций;
2 – задача не имеет решений;
3 – целевая функция не ограничена.
nit – количество произведенных итераций.

Листинг решения прямой задачи оптимизации

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog # загрузка библиотеки ЛП c = [-25, -35,-25,-40,-30] # список коэффициентов функции цели b_ub = # список объёмов ресурсов A_ub = [, # матрица удельных значений ресурсов , , ] d=linprog(c, A_ub, b_ub) # поиск решения for key,val in d.items(): print(key,val) # вывод решения if key=="x": q=#использованные ресурсы print("A_ub*x",q) q1= scipy.array(b_ub)-scipy.array(q) #остатки ресурсов print("b_ub-A_ub*x", q1)

Результаты решения задачи
nit 3
status 0

success True
x [ 0. 0. 18.18181818 22.72727273 150. ]
A_ub*x
b_ub-A_ub*x [ 0. 0. 0. 90.90909091]
fun -5863.63636364
slack [ 0. 0. 0. 90.90909091]

Выводы

1. Найден оптимальный план по видам продукции
2. Найдено фактическое использование ресурсов
3. Найден остаток не использованного четвёртого вида ресурса [ 0. 0 0.0 0.0 90.909]
4. Нет необходимости в вычислениях по п.3, так как тот же результат выводить в переменной slack

Решение двойственной задачи о оптимальной производственной программе

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

Введём новое назначение искомой переменной x как некоторой «теневой» цены, определяющей ценность данного ресурса в отношении прибыли от реализации выпускаемой продукции.

C – вектор имеющихся ресурсов;
b_ub – вектор прибыли от производства единицы изделия каждого вида;
A_ub_T– транспонированная матрица A_ub.

Функция цели
minF(x)=c×x

Ограничения
A_ub_T ×x≥ b_ub

Численные значения и соотношения для переменных:
с = ; A_ub_T transpose(A_ub); b_ub = .

Задача:
Найти x показывающий ценность для производителя каждого вида ресурсов.

Особенности решения с библиотекой scipy. optimize
Для замены ограничений сверху на ограничения с низу необходимо умножить на минус единицу обе части ограничения – A_ub_T ×x≥ b_ub… Для этого исходные данные записать в виде: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).

Листинг решения двойственной задачи оптимизации

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog A_ub = [, , , ] c= b_ub = [-25, -35,-25,-40,-30] A_ub_T =-scipy.transpose(A_ub) d=linprog(c, A_ub_T, b_ub) for key,val in d.items(): print(key,val)

Результаты решения задачи
nit 7
message Optimization terminated successfully.
fun 5863.63636364
x [ 2.27272727 1.81818182 6.36363636 0. ]
slack [ 5.45454545 2.27272727 0. 0. 0. ]
status 0
success True

Выводы

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

Результаты сравнения прямой и двойственной задачи

1. Двойственная задача расширяет возможности планирования выпуска продукции, но средствами scipy. optimize решается за вдвое большее чем прямая количество итераций.
2. Переменная slack выводит информацию об активности ограничений в виде неравенств, что может быть использовано, например, для анализа остатков сырья.
3. Прямая задача является задачей максимизации, а двойственная - задачей минимизации, и наоборот.
4. Коэффициенты функции цели в прямой задаче являются ограничениями в двойственной задаче.
5. Ограничения в прямой задаче становятся коэффициентами функции цели в двойственной.
6. Знаки неравенств в ограничениях меняются на противоположные.
7. Матрица системы равенств транспонируется.

Ссылки

Дайте понятие проблемы

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

Что понимается под критериями выбора?

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

Какое решение можно считать оптимальным?

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