Условие задачи

💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Условие задачи

Сформулированная задача имеет вполне определенный экономический смысл. Допустим, некоторая фирма, занимающаяся выпуском металлоизделий, планирует производство двух видов продукции, например, оконных решеток и металлических дверей. Для выпуска этой продукции необходимы ресурсы четырех видов, например, металлический уголок двух видов (типоразмеров), пруток и листовой металл. Фирма располагает запасами ресурсов названных видов (правые части системы ограничений): 18 погонных метров уголка первого вида, 16 погонных метров уголка второго вида, 5 квадратных метров листового материала и 21 погонный метр прутка. Необходимо составить такой план выпуска продукции (количество решеток x и дверей x ) из имеющихся ресурсов, который обеспечил бы получение фирме максимальной выручки.

Неравенства системы ограничений отражают условия баланса ресурсов. Так, первое неравенство показывает, что количество уголка первого вида, пошедшего в производство, не может превышать его запаса (т.е. 18 погонных метров). Коэффициенты при переменных x и x имеют следующий смысл: 1 – количество погонных метров уголка первого вида, идущее на выпуск одной оконной решетки; 3 - количество погонных метров того же уголка для выпуска одной металлической двери. Сумма в левой части неравенства показывает затраты уголка на производство продукции обоих видов.

Значение целевой функции F равно выручке предприятия от реализации произведенной продукции. Коэффициенты при переменных имеют смысл: 2 (например, 2 тысячи рублей) – выручка от реализации одной решетки; 3 – выручка от реализации одной двери.

Рассмотрим алгоритм реализации симплексного метода. Он включает следующие действия.

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

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

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

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

Преобразуем неравенства системы ограничений в уравнения:

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

Этому правилу удовлетворяют дополнительные переменные x , x , x , x . В соответствии с этим переменные разделятся на две группы.

Выразим основные переменные через неосновные

Положив неосновные переменные равными нулю, т.е. x = 0, x = 0, получим базисное решение Х = (0; 0; 18; 16; 5; 21), которое соответствует вершине О(0; 0) многогранника на рис. 1. В связи с тем, что решение является допустимым, оно может быть и оптимальным. Выразим целевую функцию через неосновные переменные. Правило выбора основных переменных на первом шаге решения обеспечивает первоначальное выражение целевой функции F =2x x . Значение целевой функции в этом случае равно нулю.

Однако перевод любой из неосновных переменных в основные может привести к увеличению значения функции F, т.к. коэффициенты при этих переменных положительны. Возникает вопрос, какую из двух переменных следует переводить в основные. Можно высказать предположение (но не более того), что перевод переменной x в основные приведет к более сильному увеличению значения F в связи с большим значением коэффициента в выражении целевой функции. Этот перевод должен привести к получению нового базисного решения, в котором количество основных и неосновных переменных так же как на первом шаге должно быть равно 4 и 2, соответственно.

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

Отсюда следует: (x 6; x 16; x 5). Каждое уравнение системы (4), кроме последнего, определяет максимально возможное значение x , при котором значение соответствующей основной переменной остается неотрицательным. Последнее уравнение не накладывает ограничений на значение x , т.к. при любом значении переменной x x = 21, т.е. неотрицательно. Условно этот факт фиксируется записью x

Очевидно, что сохранение неотрицательности всех переменных возможно, если не нарушится ни одна из полученных во всех уравнениях границ. Отсюда следует, что x = min(6; 16; 5; ) = 5. С учетом дополнительного условия (2) интервал допустимых значений включает 0 x 5. Однако мы заинтересованы в максимально возможном увеличении значения целевой функции, в связи с чем выбираем наибольшее значение x = 5. При этом значении переменная x обращается в нуль и переходит в разряд неосновных. Третье уравнение системы (4), переводящее основную переменную в неосновные называется разрешающим и выделяется рамкой.

Выразим основные переменные через неосновные, начиная с разрешающего уравнения

Второе базисное решение Х = (0; 5; 3; 11; 0; 21) является допустимым и соответствует вершине А(0; 5) многоугольника на рис.1.

Выразив целевую функцию через неосновные переменные, получим

Значение целевой функции F = 15 не является максимальным, т.к. имеется возможность его увеличения переводом переменной x в основные. Система уравнений (5) определяет наибольшее возможное значение x = min(; 3; 11/2; ) = 3. Второе уравнение является разрешающим, а переменная x переходит в неосновные.