Связь с нами Группа в контакте Подписаться на RSS
Поиск по сайту


На каком языке программирования вам нужен симплекс-метод?

C++
Java
Delphi
JavaScript
Objective-C
PHP
Basic
С#
OK



Новое на сайте:

<< Назад

Основы симплекс метода.

У многих возникают трудности с пониманием симплекс метода. В чём его сложность? Главная проблема симплексного метода – в его ужасном изложении. Это относится и к учебникам, и к сайтам. Подозреваю, что им никто не пользуется, потому что из невнятных, некорректных объяснений трудно что-либо понять.

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

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

Рассмотрим такую ситуацию:

Мелкий торговец на оптовой базе.

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

Его возможности ограничены определенной суммой денег, грузоподъёмностью транспорта, а также объемом контейнеров.

У торговца имеется 1110 долларов, он может погрузить на транспорт 8000 кг груза, для размещения груза имеется 120 контейнеров.

Это – ОГРАНИЧЕНИЯ.

Каждый приобретаемый товар оценивается с точки зрения прибыльности, то есть разности цен между закупкой и продажей. Уже на этапе просмотра прайса торговец занимается оптимизацией. Он отбрасывает не прибыльные, убыточные, неходовые товары и останавливается на трех перспективных товарах.

  • Товар 1: цена единицы товара в закупке – 0,1 доллара; , единица товара занимает 1/20 часть контейнера, или 0,05; вес единицы товара – 3 кг. Ожидаемая прибыль от продажи единицы товара – 3 доллара.
  • Товар 2: цена 0,2; 0,02 часть контейнера; вес 1кг, прибыль – 5.
  • Товар 3: цена 0,4; 0,02 часть контейнера; вес 2 кг. Прибыль – 4.

Сколько и чего купить, чтобы получить максимальную прибыль? Чтобы было удобнее соображать, торговец записывает в блокноте:

3*(Товар1)+5*(Товар2)+4*(Товар3)=КАК МОЖНО БОЛЬШЕ.

Или так:

Выражаясь по-научному, это целевая функция.

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

Ограничения по объёму и по весу можно записать так:

То есть получается знакомая система неравенств:

Нужно так распределить покупки, чтобы получить максимальную прибыль, то есть целевая функция должна достигнуть максимума:

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

Конечно, прибыльность товара. В целевой функции самая большая прибыль – 5, и она соответствует Товару2. Количество закупаемого Товара2 обозначено.

Сколько можно купить и увезти единиц этого товара, какую прибыль можно получить, если взять его максимально возможное количество? Чем ограничивается покупка: деньгами, вместимостью кузова или грузоподъёмностью машин?

Рассмотрим систему ограничений. На все деньги, при цене 0,2, можно купить 1100/0,2=5500. Имеющиеся 120 контейнеров можно загрузить 120/0,02=6000 единицами Товара2. Грузоподъемность позволяет увезти 8000/1=8000 единиц Товара2.

То есть количество закупаемого Товара2 ограничивается наличием денег.

В терминах линейной алгебры, мы выбрали столбец 2, строку 1 в системе уравнений. Если купить максимальное количество Товара2 (5550 единиц), то можно рассчитывать на прибыль 5500*5= 27500. То есть значение целевой функции становится равным 27500.

Можно ли увеличить значение целевой функции, приобретая другие товары? Как выбрать перспективный товар?

Купить другой вид товара можно, лишь уменьшив количество закупаемого Товара2. При этом в транспорте есть резерв места. Увеличить загрузку транспорта и общую прибыль можно, направляя часть денег на покупку более дешевого товара, чтобы вместо единицы Товара2 приобретать большее количество другого товара. В имеющемся наборе это Товар1, его цена 0,1, а прибыль 3.

Рассмотрим ограничения, действующие на Товар1. Его можно купить 1100/0,1=11000, в контейнеры помещается 120/0,05= 2400, грузоподъёмность транспорта позволяет увезти 8000/3=2666 единиц. То есть количество вывозимого Товара1 ограничено объёмом контейнеров. (это первый столбец, вторая строка). Отметим, что цена Товара1 (0,1) в два раза меньше, чем Товара2 (0,2). Вместо единицы Товара2 можно купить 2 единицы Товара1, при этом прибыль от двух единиц Товара1 (3*2=6) больше, чем прибыль от одной единицы Товара2, составляющая 5.

То есть на этот раз мы выбрали столбец 1, строку 2.

Товар3 в два раза дороже Товара2 и менее прибыльный, поэтому его не покупаем, это невыгодно.

Теперь можно ограничиться рассмотрением системы двух неравенств:

Чтобы полностью использовать деньги и транспортные возможности, усилим неравенства до уравнений и решим систему уравнений. Получаем результат:

Значение целевой функции: 3*250+5*5375=27625. Ранее получалось значение 27500 (при закупке только Товара2). Как видим, значение целевой функции несколько (не слишком сильно) возросло.

Может быть, если купить больше Товара1, уменьшим долю Товара2, то прибыль можно увеличить? Вместо одного Товара2 можно купить два Товара1, но при этом потребуется дополнительный объём в контейнерах. Товар1 дешевле, но объёмнее Товара2, и для загрузки двух дополнительных единиц Товара1 придётся недогрузить 5 единиц Товара2. Прибыль от двух дополнительных Товаров1 составляет 6, убыль от недогруженных Товаров2 составит 25. Ясно, что это невыгодно.

А теперь займёмся переводом решения в симплекс таблицы.

Комментарии (0):

Имя:

email:

Защита от спама:

Введите число, изображенное на картинке:

Текст комментария:


Copyright © MathZone.Ru, 2012 - 2017
email: alex_ey@mail.ru