В грядущем столетии лучшие учителя будут именно дистанционные, то есть имеющие возможность и умеющие взаимодействовать со всем миром с помощью электронных телекоммуникаций
А.В.Хуторской, доктор педагогических наук
Дистанционное обучение начинающих программистов
Краснодарское Муниципальное 
общеобразовательное учреждение: средняя общеобразовательная школа 99 с 
углубленным изучением технологии Математика. Содержание. Лена. Новосибирск. Учится: мехмат НГУ.  
Сайт http://www.greenage.narod.ru/ 
Папа Лены Кропочкин Сергей Александрович
автор книги: Visual Basic для детей
Главная. Математика. Информатика. Уроки. Термины. Тесты. Факультативы. Книги. Статьи. Рефераты. Исходники. Игры. Лабораторные. Контрольные. Курсовые. Дипломные. Утилиты. Рассылки. Авторы. Письма. Отзывы. Награды. Закажи CD ROM. Web мастер.
| Назад | | Содержание | | Дальше |



Задача 1. Решение задачи симплексным методом линейного программирования.
( автор сайта: Климант Ю.В. )


Задача.

    Для кондитерской фабрики требуется рассчитать оптимальный план выпуска карамели. Весь ассортимент карамели разделен на три однородные группы, условно обозначенные A, B и C. Для производства карамели требуются сахарный песок, патока, фруктовое пюре. Запасы этих видов сырья равны соответственно 700, 300 и 150 тонн. Другие виды сырья, входящие в готовый продукт в небольших количествах, не учитываются. В качестве критерия оптимальности плана принять максимум прибыли. Уровень прибыли на единицу каждого вида выпускаемой карамели ( в денежных единицах за 1 тонну): для A - 1000, для B - 1100, для C - 1200. Нормы расхода сырья на производство единицы каждого вида карамели приведены в таблице.

СырьеРасход сырья на 1 тонну карамели
A B C
Сахарный песок0,70,70,7
Патока0,30,30,2
Фруктовое пюре00,20,3

Требуется:
    1). Составить математическую модель задачи (показатель эффективности - прибыль).
    2). Определить план выпуска карамели, обеспечивающий максимальную прибыль (решить задачу двумя способами: графическим и симплексным методом).
Найти план производства карамели, максимизирующий прибыль.

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

Математическая модель задачи имеет следующий вид:

    F=1000x1 + 1100x2 + 1200x3 (max)

    0,7x1 + 0,7x2 + 0,7x3 <= 700
    0,3x1 + 0,3x2 + 0,2x3 <=300
    0,0x1 + 0,2x2 + 0,3x3 <=150

    x1 >= 0 ; x2 >= 0 ; x3 >= 0 ;

    Приведем задачу линейного программирования к каноническому виду и решим ее симплексным методом. Для этого введем дополнительные переменные
    x4 >= 0 ; x5 >= 0 ; x6 >= 0 такие, что система неравенств превратится в систему равенств.

    0,7x1 + 0,7x2 + 0,7x3 + x4                 <= 700
    0,3x1 + 0,3x2 + 0,2x3        + x5           <=300
    0,0x1 + 0,2x2 + 0,3x3                 + x6  <=150,

    где x1 >= 0 ; x2 >= 0 ; x3 >= 0 ; x4 >= 0 ; x5 >= 0 ; x6 >= 0.

    Линейная форма F(x1, x2, x3) примет следующий вид:

    F = 1000x1 + 1100x2 + 1200x3 + 0x4 + 0x5 + 0x6.

    На основании полученных соотношений составим первую симплексную таблицу.

i Базис С базиса A0 1000 1100 1200 0 0 0
A1 A2 A3 A4 A5 A6
1 A4 0 700 7/10 7/10 7/10 1 0 0
2 A5 0 300 3/10 3/10 1/5 0 1 0
3 A6 0 150 0 1/5 3/10 0 0 1
m + 1 Zj - Cj 0 -1000 -1100 -1200 0 0 0


    Выберем в этой таблице наибольшую по абсолютной величине отрицательную оценку Zj - Cj в (m + 1) строке. Это оценка - 1200, стоящая в столбце A3.
    Найдем минимальное отношение элементов столбца A0 к положительным элементам выбранного столбца A3. Этот столбец называют разрешающим.

    min { 700/0,7; 300/0,2; 150/0,3 } = { 1000, 1500, 500 } = 150/0,3 = 500.

    Итак, мы видим, что минимальное отношение есть отношение 150 к 0,3, то есть 0,3 - это разрешающий элемент ( его называют иногда ключевым или генеральным элементом, а соответствующую ему строку - разрешающей строкой).

    Выполним симплексное преобразование таблицы с выбранным разрешающим элементом. Получим следующую таблицу:

i Базис С базиса A0 1000 1100 1200 0 0 0
A1 A2 A3 A4 A5 A6
1 A4 0 350 7/10 7/30 0 1 0 -7/3
2 A5 0 200 3/10 1/6 0 0 1 -2/3
3 A3 1200 500 0 2/3 1 0 0 10/3
m + 1 Zj - Cj 600000 -1000 -300 0 0 0 4000


    При этом разрешающий элемент становится равным 1, а все остальные элементы разрешающего столбца - нулями.
Элементы разрешающей строки делятся на разрешающий элемент a33=0,3. Остальные элементы матрицы (таблицы) пересчитываются согласно алгоритму симплексного метода по правилу:

Новое aij = Старое aij - ( ai0j * aij0 ) / ai0j0,
где
Старое aij - число до пересчета
ai0j - элемент из разрешающей строки i0 и столбца j.
aij0 - элемент из разрешающего столбца j0 и строки i.
ai0j0 - разрешающий элемент.
Новое aij - число после пересчета.

    Как следует из второй симплексной таблицы, оптимальное решение еще не получено, так как в строке оценок Zj - Cj еще имеются отрицательные элементы. Выберем снова максимальное по абсолютной величине значение оценки. Это будет число -1000 из первого столбца таблицы. Примем первый столбец за разрешающий столбец и будем находить минимальное отношение неотрицательных элементов столбца A0 к положительным элементам нового разрешающего столбца. Делается это для уточнения разрешающего элемента и разрешающей строки.

min ( 350/0,7; 200/0,3; } = { 500; 2000/3 } = 350/0,7 = 500. Таким образом, элемент a11 является новым разрешающим элементом второй симплексной таблицы. Выполним симплексное преобразование таблицы с найденным разрешающим элементом. В результате получим следующую симплексную таблицу:

i Базис С базиса A0 1000 1100 1200 0 0 0
A1 A2 A3 A4 A5 A6
1 A1 1000 500 1 1/3 0 10/7 0 -10/3
2 A5 0 50 0 1/15 0 -3/7 1 1/3
3 A3 1200 500 0 2/3 1 0 0 10/3
m + 1 Zj - Cj 1100000 0 100/3 0 10000/7 0 2000/3


    Строка оценок Zj - Cj последней симплексной таблицы больше не содержит отрицательных чисел. Это свидетельствует о том, что нами получено оптимальное решение задачи линейного программирования на максимум прибыли. Найдено оптимальное решение x1=500, x2=0, x3=500, оптимизирующее получение прибыли при производстве карамели. Прибыль составляет 1100000 рублей.


Климант Юрий Викторович,,
учитель информатики Краснодарской Муниципальной общеобразовательной средней школы 35
и средней школы 48
Страничка подготовлена, проверена и отредактирована 7 марта 2007 года.
Главный администратор сайта: Климант Юрий Викторович.



| Назад | | Содержание | | Дальше |


Главная. Математика. Информатика. Уроки. Термины. Тесты. Факультативы. Книги. Статьи. Рефераты. Исходники. Игры. Лабораторные. Контрольные. Курсовые. Дипломные. Утилиты. Рассылки. Авторы. Письма. Отзывы. Награды. Закажи CD ROM. Web мастер.
X