2020-04-20
1306
ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ
Графический метод, как наиболее простой и наглядный, применяется преимущественно в целях уяснения сущности задач линейного программирования. Данный метод позволяет решать задачи только с двумя неизвестными. Для решения задач с большим числом неизвестных он неприменим, так как графические построения в многомерном пространстве без использования специальных графопостроителей на базе ЭВМ невозможны.
Методика решения задач графическим методом предусматривает следующий порядок действий:
1. Постановка задачи.
Предполагает словесную формулировку условий задачи и указание функции цели (на максимум или минимум).
2. Составление экономико-математической модели задачи.
Данный этап решения задачи предусматривает математическую формулировку функции цели и условий задачи в виде системы неравенств. Форма записи условий задачи в виде системы неравенств называется стандартной.
Геометрически каждое из неравенств представляет собой полуплоскость, которая может быть расположена по ту или иную сторону от распределительной прямой линии.
3. Вычисление координат точек пересечения граничных прямых и прямых функций цели с осями координат.
Вычисление координат осуществляется в следующей последовательности:
- каждое из неравенств, выражающих условия задачи (ограничения), заменяется уравнением. В геометрическом смысле полуплоскость заменяется прямой линией, математически выраженной в виде уравнения;
- в каждом уравнении Х1 приравнивается к нулю (Х1=0) и по уравнению рассчитываются Х2 (Х2 в этом случае находится как отношение свободного члена в i на коэффициент при Х2). Затем Х2 приравнивается нулю (Х2=0) и определяется значение Х1.
Полученные таким образом координаты точек пересечения граничных прямых (каждому уравнению соответствует своя прямая) с осями прямоугольных координат Х1 и Х2 заносят в специальную таблицу (см. таблицу 1.1);
- целевая функция приравнивается к произвольному круглому числу (выражается в виде уравнения) с таким расчетом, чтобы получить координаты точек пересечения её прямой с прямоугольными осями координат Х1 и Х2 в пределах графика.
Поочередно приравнивая Х1 и Х2 к нулю, как описано выше, вычисляются координаты точек пересечения, которые также заносятся в таблицу 1.1.
Для того, чтобы можно было на графике определить направление оптимизации, необходимо вычислить координаты точек пересечения второй прямой функции цели (Z2) с осями координат Х1 и Х2. Данные координаты получают путем удвоения первоначального значения функции цели (Z1) и значений полученных для нее координат. Координаты прямой также заносятся в таблицу 1.1.
4. Построение графика и установление области допустимых решений.
График строится в следующей последовательности:
- выбирается масштаб построения графика с учетом отражения на графике максимальных значений координат точек пересечения прямых с осями Х1 и Х2;
- строятся оси прямоугольной системы координат Х1 (горизонтальная ось) и Х2 (вертикальная ось) и делается разбивка делений в соответствии с выбранным масштабом для каждой из осей;
- на осях Х1 и Х2 откладываются координаты точек пересечения, полученные для соответствующего уравнения. Через данные точки проводится прямая. Если вычислена только одна координата точки пересечения, то это означает, что через данную точку пройдет прямая, параллельная другой оси координат. Аналогичным образом строятся прямые для всех уравнений и для двух значений функции цели (Z1, Z2);
- после построения на графике граничных прямых относительно каждой из них устанавливается местоположение полуплоскости, содержащей допустимые решения для соответствующего ей неравенства. В каждое неравенство подставляются вместо неизвестных Х1 и Х2 значения начала оси координат, т.е Х1=0, Х2=0. Если подставленные значения удовлетворяют неравенству (т.е. соблюдается его смысл), то область допустимых решений (ОДР) расположена в той полуплоскости, которая находится от прямой со стороны начала координат. Если не удовлетворяют, то область допустимых решений находится с противоположной от начала координат стороны прямой.
Направление расположения области допустимых решений относительно каждой из прямых показывается стрелкой в сторону расположения полуплоскости, удовлетворяющей условиям неравенства. В результате этого устанавливаются границы области допустимых решений (ограничивающие её прямые), а сама область штрихуется (рис. 1.1).
5. Поиск оптимального решения задачи.
Поиск оптимального решения задачи осуществляется в следующей последовательности:
- прямую, параллельно прямым Z1 и Z2 перемещают в направлении оптимизации (в ту сторону, в которой находится Z2 по отношению к Z1) до последней точки или грани касания с областью допустимых решений;
- с графика снимаются координаты точки касания Zопт с областью допустимых решений. Они соответствуют оптимальным значениям неизвестных Х1 и Х2. Если же линия Zопт касается грани ОДР, то координаты любой точки грани являются оптимальным решением задачи. Это означает, что существует бесчисленное множество оптимальных решений, но при этом значение функции цели остается неизменным;
- для контроля правильности решения задачи координаты точки оптимума (точки касания) подставляются в исходные неравенства. В результате данной постановки неравенства превращаются в равенства или сохраняют свой смысл;
- оптимальные значения неизвестных подставляются в функцию цели, и вычисляется её оптимальное значение;
- формулируется полный ответ решенной задачи.
ПРИМЕР РЕШЕНИЯ ЗАДАЧИ ГРАФИЧЕСКИМ МЕТОДОМ
При решении задачи сохраним нумерацию этапов решения, приведенную выше в методике.
1. Требуется определить в фермерском хозяйстве оптимальное соотношение посевных площадей пшеницы и гречихи. Под данные культуры фермер может отвести не более 120 га пашни. При этом фермером заключены контракты на гарантированную продажу партнерам не менее 1000 ц пшеницы и не менее 800 ц гречихи.
Плановая урожайность пшеницы – 20 ц/га, гречихи – 25 ц/га. Закупочная цена 1 ц (условно): пшеницы – 5,0 тыс. руб., гречихи – 10,0 тыс. руб.
Критерий оптимальности – максимум валовой продукции в стоимостном выражении.
2. В задаче примем следующие обозначения:
Х1 - посевная площадь пшеницы, га;
Х2 - посевная площадь гречихи, га.
Сформулируем математически функцию цели и условия задачи в виде системы неравенств:
Z =5,0∙20Х1+10,0∙25Х2→ max
или
Z =100Х1+250Х2→ max
1) Х1+ Х2≤120 – ограничение по площади пашни;
2) 20Х1≥1000 – ограничение по объёму производства пшеницы;
3) 25Х2≥800 - ограничение по объёму производства гречихи;
Х1≥0; Х2≥0 – условие неотрицательности неизвестных.
3. Переходим от неравенств к уравнениям (от стандартной к канонической форме записи условий задачи) с целью последующего вычисления координат точек пересечения граничных прямых с осями координат Х1 и Х2.
1) Х1+ Х2=120
2) 20Х1=1000
3) 25Х2=800
Последовательно приравнивая Х1=0 и Х2=0 и подставляя их в уравнения, вычисляем координаты точек пересечения и заносим их в таблицу 1.1. Так, при Х1=0 в первом уравнении Х2=120 и т.д. по другим уравнениям.
Целевой функции придаем произвольные значения 2000 и записываем её в виде уравнения:
Z 1=100Х1+250Х2=2000.
Подставляя поочередно в уравнение значения Х1=0 и Х2=0, получим координаты точек пересечения прямой Z 1 с осями координат. Удваивая значение функции цели Z 1 и её координат, получим значения функции цели Z 2 (4000) и её координаты.
Заносим их в таблицу 1.1.
Таблица 1.1
Координаты точек пересечения граничных прямых и
прямых функций цели с осями координат Х1 и Х2
| Номер уравнения | Пересечение с осями | |
| Х1 (при Х2=0) | Х2 (при Х1=0) | |
| Граничные прямые | ||
| 1 | 120 | 120 |
| 2 | 50 | - |
| 3 | - | 32 |
| Функция цели | ||
| Z 1=2000 | 20 | 8 |
| Z 2=4000 | 40 | 16 |
4. Строим график, откладывая на осях Х1 и Х2 в заданном координатами масштабе точки пересечения прямых. Через точки пересечения, относящиеся к соответствующему уравнению, проводим прямые (РИС. 1.1) с указанием номеров их уравнений (для граничных прямых) и символов (Z 1 и Z 2 – для прямых функций цели).
Для определения на графике области допустимых решений (ОДР) подставим одновременно в первое неравенство значения, соответствующие началу координат (Х1=0, Х2=0). В результате этого получим, что 0≤120, т.е. неравенство сохраняет свой смысл. Следовательно, ОДР расположена от прямой (1) в направлении начала координат. Покажем это на графике стрелкой от данной прямой.
Подставив Х1=0, Х2=0 во второе неравенство, видим, что неравенство не соблюдается (т.к. получаем 0≥1000). Следовательно, ОДР расположена в противоположной от начала координат стороне относительно прямой (2). То же самое имеем и для прямой (3).
Таким образом, область допустимых решений находится в треугольнике АВС, образованном граничными прямыми.
5. Для поиска оптимального решения задачи ставим линейку на прямую Z 2, на графике и, сохраняя параллельность, двигаем в направлении оптимизации, указанном стрелкой, до последней точки касания с ОДР (до точки В). В точке В проводим на графике прямую Zопт, параллельную Z 2, и снимаем координаты точки оптимума (точки В):
Х1 опт =50, Х2 опт =70.
Для контроля правильности решения задачи подставим координаты точки оптимума (точки В) в исходные неравенства:
1) 50+70=120, согласно неравенству (1) должно быть ≤120;
2) 20∙50=1000, согласно неравенству (2) должно быть ≥1000;
3) 25∙70=1750, согласно неравенству должно быть ≥800.
Следовательно, полученные координаты точки оптимума удовлетворяют всем неравенствам.
Вычислим значение функции цели:
Zопт =100Х1+250Х2=100∙50+250∙70=22500.
Ответ: Оптимальным планом предусматривается отвести под пшеницу 50 га, под гречиху 70 га. В результате этого объем производства зерна пшеницы будет 1000 ц, гречихи 1750 ц. Стоимость валовой продукции составит 22500 тыс. руб.
Рис. 1.1. Область допустимых решений задачи
Задания для самостоятельной работы студентов по решению задач графическим методом представлены в приложении 1.
ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ
1. Перечислите основные этапы решения задач графическим методом.
2. В чем проявляется ограниченность практического применения графического метода?
3. Как определить область допустимых решений двумерной задачи на графике?
4. С какой целью неравенства преобразуются в равенства?
5. Объясните геометрический смысл неравенства и уравнения в двумерной задаче.
6. Как определяется на графике направление оптимизации?
7. При каких условиях оптимальное решение единственное, а при каких – их множество? Как изменяется при этом значение функции цели?
8. Как осуществлять контроль правильности решения задачи?
9. Что такое область допустимых решений?
10. Какое значение для решения задачи имеет расположение полуплоскости относительно граничной прямой?
11. В каком случае задача имеет бесчисленное число оптимальных решений при неизменном значении функции цели?
РАСПРЕДЕЛИТЕЛЬНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Распределительный метод линейного программирования применяется для решения задач, описываемых транспортными моделями, в которых все распределяемые ресурсы выражены в одинаковых единицах измерения (перевозка однородного груза) и каждая переменная участвует не более чем в двух ограничениях. Экономическая сущность задач, решаемых распределительным методом, заключается в отыскании наиболее эффективного плана перевозок (распределения) однородного груза из «m» пунктов отправления в «n» пунктов назначения.
Простота алгоритма распределительного метода позволяет применять его и для решения ряда землеустроительных задач:
- определение оптимальных планов перевозок продукции с полей севооборотов и участков сельскохозяйственных угодий в хозяйственные центры;
- рациональное размещение полей по типам (видам) севооборотов с учетом различия в естественном плодородии почв и технологических свойств земель;
- рациональное размещение сельскохозяйственных культур на участках пашни с учетом различия их производительных и технологических свойств;
- оптимальное размещение вспомогательных хозяйственных центров на территории сельскохозяйственного предприятия (например, зернотоков, летних лагерей и т.д.);
- оптимальное размещение объектов трансформации (улучшения) угодий с учетом различия производительных и технологических свойств участков земель и другие.
Порядок решения задач распределительным методом следующий:
1. Постановка задачи (словесная формулировка с указанием условий задачи и функции цели);
2. Подготовка исходной информации;
3. Составление исходной матрицы и математическая формулировка задачи;
4. Составление исходного допустимого базисного плана;
5. Анализ плана на оптимальность;
6. Улучшение плана;
7. Анализ оптимального решения задачи и возможная его корректировка.
2.1. РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ РАСПРЕДЕЛИТЕЛЬНЫМ МЕТОДОМ
Методика решения транспортных задач по алгоритму распределительного метода приведена ниже.
1. Постановка задачи
Характер постановки задачи предопределяется экономической сущностью землеустроительной задачи, которую предстоит решить с помощью распределительного метода. Функция цели в задаче может быть ориентирована на минимум суммарных транспортных издержек или кратчайшее расстояние перевозок; на максимум чистого дохода или стоимости валовой продукции. Например, требуется составить оптимальный план транспортировки однородного груза Х ij от «m» поставщиков к «n» потребителям, обеспечивающий минимальные суммарные транспортные расходы. Наличие груза в пунктах отправления составляет: а1, а2,….. аm, а потребность в нем в пунктах назначения, соответственно: b1, b2,….. bn. Стоимость перевозки единицы груза от i -го поставщика к j- му потребителю составляет Сij.
2. Подготовка исходной информации
Она заключается в предварительной подготовке информации для получения требуемых по условиям задачи показателей. Например, при решении задачи на минимум транспортных расходов предварительно необходимо на плане землевладения/землепользования измерить расстояние от каждого поставщика до каждого потребителя и определить соответственно стоимость перевозки единицы груза Сij. Полученные значения показателя Сij представляют в виде таблицы. Далее определяются запасы груза в пунктах отправления аi и потребности в нем (bj) в пунктах назначения.
3. Составление исходной матрицы и математическая формулировка задачи
Исходная матрица составляется следующим образом: число строк соответствует числу пунктов отправления «m», а число столбцов – числу пунктов назначения «n». Переменные Х ij, проставленные на пересечении строк и столбцов, выражают искомое количество груза, которое требуется перевезти из i -го пункта отправления в j- й пункт назначения. Стоимость перевозки единицы груза (или расстояние) соответственно обозначается коэффициентами Сij, где i - номер поставщика, j - номер потребителя. Количество груза в пунктах отправления обозначается: а1, а2,….. аm, потребность в пунктах назначения составляет: b1, b2,….. bn (таблица 2.1).
Таблица 2.1
Исходная матрица задачи распределительного типа
| Пункты отправления |
| Запасы груза а i | ||||||||
| 1 | 2 | j | n | |||||||
| 1 | X | С1.1 | X | С1.2 | X | С1.j | X | С1.n | а1 | |
| 2 | X | С2.1 | X | С2.2 | X | С2.j | X | С2.n | а2 | |
| i | X | Сi.1 | X | Сi.2 | X | Сi.j | X | Ci.n | а i | |
| m | X | Сm.1 | X | Сm.2 | X | Cm.j | X | Cm. n | аm | |
|
|
|
| ||||||||
| Потребность в грузах bj | b1 | b2 | bj | bn | ∑ аi | |||||
Математическая модель задачи, решаемой распределительным методом, в общем виде формулируется следующим образом:
Требуется составить оптимальный план перевозок, обеспечивающий минимальную суммарную стоимость перевозимых грузов (Zmin):
(2.1)
при следующих условиях:
1. Количество перевозимых грузов должно быть равно их запасам на пунктах отправления:
/ i=1,2,…m/ (2.2)
2. Количество перевозимых грузов должно быть равно потребностям в них в пунктах назначения:
/ j=1,2,…n/ (2.3)
3. Запасы грузов и потребности в них должны быть равны:
(2.4)
4. Переменные в задаче должны быть неотрицательны:
Х ij≥0
При равенстве запасов и потребностей груза (2.4) модель называется закрытой, а при нарушенном балансе – открытой. Для приведения модели к закрытому виду вводится фиктивный поставщик или фиктивный потребитель в зависимости от типа неравенства. Если потребность в грузе превышает его запасы (
< 
), то вводится фиктивный поставщик с объемом поставок
. (2.5)
Если запасы груза превышают потребность в нем (
> 
), то вводится фиктивный потребитель с объемом спроса
. (2.6)
Для фиктивного поставщика (потребителя) стоимость перевозок груза (Сij) принимается равной нулю, что позволяет исключить его при расчете функции цели.
4. Составление исходного допустимого базисного плана
Исходный (первоначальный) план может быть составлен различными способами: минимального элемента, северо-западного угла, аппроксимации и другими. Наиболее предпочтительным для решения землеустроительных задач является способ минимального элемента матрицы, который сокращает число итераций (улучшений) для получения оптимального плана.
Этот способ основан на предпочтении «дешевого» маршрута или кратчайшего расстояния (при решении задачи на минимум).
Алгоритм способа минимального элемента матрицы заключается в следующем:
- запись поставок начинается в клетку с наименьшим (ненулевым) значением Сij. При этом в качестве поставки (Х ij) записывается меньшее из значений запаса (аi) или потребности (b j), относящихся к данной клетке. Элементы Сij этого столбца (строки) из дальнейшего рассмотрения исключаются;
- среди оставшихся выбирается следующий минимальный элемент матрицы и записывается поставка, полностью удовлетворяющая спрос или исчерпывающая запас. Этот процесс продолжают для полного распределения поставок.
При решении задач на максимум для составления исходного плана, по аналогии с вышеуказанным, применяется способ максимального элемента матрицы.
После распределения поставок исходный план должен быть проанализирован на допустимость и базисность.
Исходный план является:
- допустимым, если полученные значения Х ij (распределенные поставки) удовлетворяют всем условиям задачи, а число занятых в матрице клеток не превышает m+n-1;
- базисным, если число занятых клеток Х ij равно m+n-1;
- недопустимым (составленным неверно), если число занятых клеток больше m+n-1;
- вырожденным, если число занятых в плане клеток меньше, чем m+n-1.
Если в процессе анализа исходного плана выявлено, что он составлен неверно или вырожден, то необходимо добиться, чтобы он стал допустимым и базисным.
В случае, когда исходный план недопустимый, т. е составлен неверно, его составляют заново или повторяют анализ на допустимость и базисность.
Если исходный план оказался вырожденным, то его приводят к допустимому базисному виду, используя нуль-прием. Сущность нуль-приема заключается в том, что одну или несколько свободных клеток матрицы (плана) считают условно занятыми нулевыми поставками (т. е для них Х ij =0) с таким расчетом, чтобы общее количество занятых клеток стало равным m+n-1.
При размещении в матрице задачи нулевых поставок соблюдают следующие требования:
- в каждом столбце и строке должно быть не менее одной занятой клетки, а занятая клетка не может быть единственной одновременно в столбце и строке;
- условно занятая (0) клетка не должна образовывать с другими клетками замкнутых контуров; целесообразно её размещать на пересечении равных запасов и потребностей.
Например, по условиям задачи имеется 3 поставщика груза (m =3) и 4 потребителя (n =4). Если при составлении исходного плана оказалось 5 занятых клеток, то план вырожденный, т.к по выражению m+n-1 их должно быть 6 (3+4-1). Необходимо, используя нуль-прием, привести план к базисному виду.
5. Анализ плана на оптимальность
На оптимальность анализируется допустимый базисный план. При этом соблюдается следующая последовательность действий:
- строятся замкнутые контуры для каждой свободной клетки матрицы (плана);
- для каждого контура (многоугольника) вычисляются числовые характеристики;
- полученные числовые характеристики по контурам для всех свободных клеток матрицы проверяются на соответствие математическим условиям оптимальности плана.
Замкнутые контуры (многоугольники) для каждой свободной клетки плана строятся с соблюдением следующих правил:
а) контур представляет собой замкнутый многоугольник, исходная вершина которого находится в свободной клетке, остальные - в занятых;
б) отрезки контуров могут проходить через занятые клетки, не являющиеся вершинами данного контура;
в) все углы контура прямые, его стороны располагаются по строкам и столбцам матрицы;
г) в сложных контурах стороны многоугольника могут пересекаться в одной из его вершин;
д) число вершин контура четное, минимальное равно четырем, максимальное не превышает m+n;
е) построение контуров можно производить как по ходу часовой стрелки, так и против неё;
ж) для каждой свободной клетки можно построить только один контур;
з) вершинам контура придают чередующиеся знаки, начиная со знака плюс в свободной клетке.
На основе матрицы для каждого построения контура вычисляют характеристику (∑ij) как алгебраическую сумму значений Сij находящихся в его вершинах.
Вычисленные характеристики контуров являются основанием для анализа плана на оптимальность.
Признаками оптимальности плана в зависимости от направления оптимизации задачи (Z) являются:
- при решении задачи на минимум (Zmin) – наличие положительных характеристик (∑ij >0) у всех контуров. Если хоть одна из характеристик отрицательная, то план не оптимален и следует его улучшить;
- при решении задачи на максимум (Zmax) – наличие отрицательных или равных нулю характеристик (∑ij =0) у всех контуров. Если хоть одна из характеристик положительная, то план не оптимален и следует его улучшить.
6. Улучшение плана
Улучшение неоптимального плана заключается в перераспределении поставок по контуру. При этом выбор контура для улучшения осуществляется в зависимости от направления оптимизации функции цели (Z):
1) при решении задач на минимум (Zmin) для улучшения выбирается контур с наибольшей по абсолютной величине отрицательной характеристикой;
2) при решении задачи на максимум (Zmax) для улучшения выбирается контур с наибольшей по абсолютной величине положительной характеристикой.
Если имеется несколько равных по абсолютной величине характеристик, то для улучшения выбирают ту из них, которая относится к контуру, позволяющему передвинуть большую поставку. Это сокращает число последующих итераций (улучшений) плана для получения оптимального решения и вызывает наибольшее изменение целевой функции в направлении оптимизации.
Порядок улучшения плана:
- из матрицы (плана) выносят для отдельного рассмотрения контур, выбранный для улучшения с соответствующими значениями поставок (Х ij) со своими знаками «+», «-» в его вершинах;
- в отрицательных вершинах контура находят наименьшую из поставок и записывают её в исходной вершине контура (расположенной в свободной клетке матрицы), это будет передвигаемая по контуру поставка;
- наименьшую поставку (передвигаемую) последовательно прибавляют к поставкам, стоящим в положительных вершинах контура, и вычитают из поставок, стоящих в отрицательных вершинах улучшаемого контура;
- улучшенный контур с новыми значениями поставок в его вершинах вставляется на свое прежнее место в матрицу улучшенного плана. Значения поставок в остальных клетках матрицы переписываются без изменения из плана, который улучшался. В результате получают улучшенный план, который вновь проверяют на оптимальность (см. п.5), а при необходимости вновь улучшают до получения оптимального решения задачи.
В случае получения оптимального плана определяется значение целевой функции (Z) как сумма произведений поставок Х ij на коэффициенты Сij в занятых клетках плана, т.е. по формуле 2.1
7. Контроль решения задачи
Контроль правильности решения задачи выполняется посредством сравнения значений цели (Z), рассчитанных по указанной выше формуле 2.1 и по формуле:
Z´opt= Z1+ ∆Z1+∆Z2+……+∆Zk, (2.7)
где k – число улучшений (итераций);
Z1 – значение функции цели исходного допустимого базисного плана;
∆Z1, ∆Zk – величина улучшений значений целевой функции при каждом из улучшений плана.
Величина улучшений целевой функции при каждом улучшении плана вычисляется как произведение числовой характеристики улучшаемого контура (его алгебраической суммы со своим знаком) на величину перемещаемой по нему поставки.
При совпадении значений функции цели вычисленных по формуле 2.1 и 2.7 задача решена правильно. При несовпадении следует выполнить данное сравнение для каждого из улучшенных планов и, обнаружив, в каком из планов допущена ошибка, устранить её и повторить контроль правильности решения задачи.
В случае правильного решения задачи формулируют ответ с учетом характера её поставки. При этом отмечается, что оптимальным планом предусматриваются следующие объемы поставок груза от каждого из поставщиков до соответствующих потребителей (согласно распределению поставок в матрице оптимального плана), которые обеспечивают минимальное (максимальное) значение целевой функции.
ПРИМЕР РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ
РАСПРЕДЕЛИТЕЛЬНЫМ МЕТОДОМ
Последовательность решения задачи осуществляется в соответствии с рассмотренной методикой распределительного метода.
1. Постановка задачи (словесная формулировка условий задачи и функции цели)
В сельскохозяйственном предприятии имеются три откормочные площадки, на которых содержится молодняк крупного рогатого скота, зеленый корм для него доставляют с трех разных полей севооборотов. Потребность скота в зеленом корме по откормочным площадкам составляет (т): 1-й – 1600, 2-й – 1300, 3-й – 700.
Валовой запас (выход) зеленого корма с полей севооборотов соответственно составляет (т): 1 – 1800, 2 – 700, 3 – 1500.
Расстояние перевозки зеленого корма с полей на откормочные площадки (км) приведены в таблице 2.2.
Таблица 2.2
Расстояния перевозки зеленого корма с полей севооборотов
на откормочные площадки (км)
| Поля севооборотов | Откормочные площадки | ||
| 1 | 2 | 3 | |
| I | 3 | 6 | 4 |
| II | 5 | 7 | 2 |
| III | 6 | 8 | 9 |
Необходимо получить оптимальный план закрепления полей севооборотов за откормочными площадками, обеспечивающий наименьший общий тонно-километраж на перевозку зеленого корма с полей на откормочные площадки.
2. Подготовка исходной информации
В процессе подготовки измерены на проектом плане расстояния от каждого из полей севооборотов до каждого из откормочных площадок и занесены в таблицу 2.2.
3. Составление исходной матрицы задачи
До составления исходной матрицы необходимо выяснить, открытая или закрытая модель решаемой задачи, т.к. от этого зависит количество строк и столбцов в матрице. В случае открытой модели задачи потребуется вводить в матрицу дополнительную строку для фиктивного поставщика или дополнительную графу для фиктивного потребителя.
Для выяснения вопроса о характере модели задачи (открытая или закрытая) сравним между собой суммарный запас зеленого корма с суммарной потребностью в нем.
Суммарный запас зеленого корма на трех полях севооборотов составил 4000 т, а суммарная потребность в нем скота, размещенного на трех откормочных площадках – 3600 т, т.е. мы имеем открытую модель задачи. Алгоритм распределительного метода позволяет решать задачи только закрытого типа, поэтому открытую модель рассматриваемой задачи преобразуем в закрытую. Для этого введем фиктивную откормочную площадку (т.к. суммарный запас зеленого корма превышает суммарную потребность в нем) с объемом потребления в4=4000-3600=400 (т) и расстояниями до неё от полей Сi4 =0.
Условие задачи занесем в исходную матрицу (таблица 2.3). В исходной матрице по строкам заносятся сведения по поставщикам, а по графам – по потребителям. Кроме этого имеются итоговые: столбец запасов (а i) и строка потребностей (bj).
Таблица 2.3
Исходная матрица задачи
| Поля севооборотов | Откормочные площадки | Запасы а i | |||||||
| 1 | 2 | 3 | 4 (фикт.) | ||||||
| I |
| 3 |
| 6 |
| 4 |
| 0 | 1800 |
| II |
| 5 |
| 7 |
| 2 |
| 0 | 700 |
| III |
| 6 |
| 8 |
| 9 |
| 0 | 1500 |
| Потребности bj | 1600 | 1300 | 700 | 400 | 4000 4000 | ||||
В результате введения фиктивного потребителя (четвертую откормочную площадку с условной потребностью в зеленом корме в4=400 т) полностью сбалансированы между собой запасы (
=4000 т) и потребности (
=4000 т) в зеленом корме. Модель задачи стала закрытой.
В клетках на пересечении соответствующих строк и столбцов матрицы в правом верхнем углу проставляем расстояния (из таблицы 2.2) от поставщиков (полей) до потребителей (откормочных площадок). В клетках столбца фиктивного потребителя (четвертой площадки) расстояния равны 0, т.к. реально этого потребителя нет и зеленый корм не будет перевозиться и, кроме того, данная поставка не должна учитываться при расчете значений функции цели (произведение ХijСij =0).
4. Составление исходного допустимого базисного плана
Исходный план составляем на основе исходной матрицы путем распределения поставок груза (зеленого корма) по способу минимального элемента матрицы. В качестве таких элементов матрицы выступают ненулевые коэффициенты Сij (расстояния).
Минимальным коэффициентом матрицы является С2.3 =2, т.е. расстояние между II-м полем и 3-й площадкой. Следовательно, в клетку с номером 2.3 записываем наименьшую из поставок, расположенных по строке а 2 =700 и столбцу в3=700, на пересечении которых стоит клетка 2.3, т.е. Х 2.3 =700. Поскольку запасы а 2 =700 полностью исчерпаны при переносе данной поставки в клетку 2.3, то строка и столбец выбывают из дальнейшего рассмотрения, т.е. в клетках по данной строке а 2 и столбцу в3 не будет поставок (Х ij =0).
Следующий минимальный элемент матрицы расположен в клетке 1.1 С1.1 =3. Для этой клетки в качестве поставки выбираем наименьшее из чисел, стоящих по строке (а 1 =1800) и столбцу (в1=1600), на пересечении которых расположена данная клетка. Таким наименьшим числом является 1600, следовательно, поставка Х 1.1 =1600 и весь столбец (клетки 2.1 и 3.1) выбывает из дальнейшего рассмотрения поставок.
Однако по строке а 1 остается остаток 200 т, который размещаем в клетке 1.2. Следовательно, поставка Х 1.2 =200, а строка а 1 выбывает из дальнейшего рассмотрения поставок. Оставшуюся нераспределенной в столбце в2 поставку 1100 (1300-200=1100) заносим в единственно не выбывшую из рассмотрения клетку 3.2, т.е. Х 3.2 =1100. По строке а 3 оставшуюся нераспределенной поставку в4=400 записываем в клетку Х 3.4 =400.
Контроль правильности распределения поставок осуществляется следующим образом: суммы поставок (Х ij) по строкам матрицы должны быть равны запасам (а i), а по столбцам – потребностям (bj). Таким образом, исходный план составлен (таблица 2.4).
Таблица 2.4
Исходный план
| Поля севооборотов | Откормочные площадки | Запасы а i | |||||||
| 1 | 2 | 3 | 4 (фикт.) | ||||||
| I | 1600 | 3 | 200 | 6 |
| 4 |
| 0 | 1800 |
| II |
| 5 |
| 7 | 700 | 2 |
| 0 | 700 |
| III |
| 6 | 1100 | 8 | (0) | 9 | 400 | 0 | 1500 |
| Потребности bj | 1600 | 1300 | 700 | 400 | 4000 4000 | ||||
Далее необходимо проверить, является ли составленный план допустимым и базисным. Для этого подсчитываем число занятых поставками клеток (5) и сравниваем с цифрой, полученной по выражению m+n-1 (3+4-1=6). Поскольку число занятых клеток меньше, чем число, полученное по выражению m+n-1, то план вырожден, и следует для приведения его к базисному виду вводить нуль-поставку (0). Такую поставку разместим в клетке 3.3 (Х 3.3 =0), поскольку данная клетка не должна образовывать с другими занятыми клетками замкнутых контуров.
В результате введения нуль-поставки план стал допустимый, базисный и можно приступать к анализу его на оптимальность.
Значение целевой функции:
Z1 =3∙1600+6∙200+2∙700+8∙1100=16200 т/км.
5. Анализ плана на оптимальность
Для проверки плана на оптимальность строим последовательно для свободных клеток плана замкнутые контуры и вычисляем их числовые характеристики (алгебраические суммы ∑ Сij со своими знаками).
Вершины контура, построенного для свободной клетки 1.3 разместятся в занятых клетках 1.2, 3.3 (условно занятая клетка нуль-поставкой) и 3.2. Вершине, расположенной в свободной клетке (1.3), присваивается знак «+», а остальным вершинам – поочередно чередующиеся знаки, продвигаясь в одном направлении по контуру (по часовой или против часовой стрелки). С учетом знаков и коэффициентов Сij, стоящих в занятых клетках, являющихся вершинами контура, вычисляем числовую характеристику: ∑ 1.3 =4–9+8–6=–3.
Аналогичным образом строим замкнутые контуры для других свободных клеток плана и вычисляем их числовые характеристики (∑ ij):
∑ 1.4 =0–0+8–6=2;
∑ 2.1 =5–2+9–8+6–3=7;
∑ 2.2 =7–8+9–2=6;
∑ 2.4 =0–0+9–2=7;
∑ 3.1 =6–8+6–3=1.
Одна из характеристик оказалась отрицательной, следовательно, план не оптимален и его необходимо улучшить.
6. Улучшение плана
Для улучшения плана производим перераспределение поставок
по контуру с отрицательной характеристикой ∑ 1.3 =–3.
Улучшаемый контур целесообразно вынести из плана и рассматривать отдельно (см. таблицу 2.5).
Таблица 2.5
Улучшение плана (контур клетки 1.3)
| 2 | 3 | |||
| I | 200- | 6 | (0)+ | 4 |
| II |
| 7 |
| 2 |
| III | 1100+ | 8 |
| 9 |
Поскольку наименьшей в отрицательной вершине контура оказалась нуль-поставка, то она перемещается в клетку 1.3, а клетка 3.3 становится свободной. Остальные поставки в вершинах данного контура остаются без изменения. Исходя из этого в улучшенном плане (таблица 2.6) по сравнению с исходным планом (таблица 2.4) переместится только нуль-поставка из клетки 3.3 в клетку 1.3. Величина изменения целевой функции ∆Z1 =–3х0=0, т.е. перемещение нуль-поставки не влечет за собой изменения величины целевой функции.
Улучшенный план является допустимым, базисным, т.к. число занятых клеток (6) соответствует выражению m+n-1 =6. Данный план заново анализируется на оптимальность (строятся контуры и вычисляются числовые характеристики, как и в предыдущем случае). В результате получены следующие характеристики (∑ ij):
∑ 1.4 =0–0+8–6=2;
∑ 2.1 =5–2+4–3=4;
∑ 2.2 =7–2+4–6=3;
∑ 2.4 =0–0+8–6+4–2=4;
∑ 3.1 =6–8+6–3=1;
∑ 3.3 =9–8+6–4=3.
Отсутствие отрицательных числовых характеристик свидетельствует, что план оптимален.
Таблица 2.6
Второй план
| Поля севооборотов | Откормочные площадки | Запасы а i | |||||||
| 1 | 2 | 3 | 4 (фикт.) | ||||||
| I | 1600 | 3 | 200 | 6 | 0 | 4 |
| 0 | 1800 |
| II |
| 5 |
| 7 | 700 | 2 |
| 0 | 700 |
| III |
| 6 | 1100 | 8 |
| 9 | 400 | 0 | 1500 |
| Потребности bj | 1600 | 1300 | 700 | 400 | 4000 4000 | ||||
Контроль правильности решения задачи
Вычислим значение целевой функции для оптимального плана:
Zопт =3∙1600+6∙200+2∙700+8∙1100=16200 т/км.
Контроль:
Zопт = Z2=Z1+ ∆Z1= 16200+0=16200 т/км.
Равенство значений целевой функции свидетельствует о правильном решении задачи. Особенностью данной задачи является то, что наглядно видно, как при улучшении плана путем перемещения нуль-поставки значение функции остается неизменным.
Ответ: Оптимальным для условий хозяйства будет следующее распределение поставок зеленого корма с полей севооборотов: с I поля 600 т на 1-ю площадку и 200 т – на 2-ю площадку; со II поля 700 т на 3-ю площадку; с III поля 1100 т – на 2-ю площадку и 400 т зеленой массы остается в резерве /излишек/, который может быть использован для производства сенажа. Общий тонно-километраж будет при этом наименьшим и составит 16200 т/км.
ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ
1. В чем заключается постановка транспортной задачи?
2. Какие отличительные особенности постановки транспортных задач и какие показатели используются в качестве критериев оптимизации?
3. В чем заключается подготовка исходной информации для решения транспортных задач распределительным методом?
4. Какая модель задачи считается открытой и как привести ее к закрытому типу?
5. Как составляется исходный план в задачах распределительного типа?
6. Назовите признаки допустимого, недопустимого и базисного планов при решении задач распределительным методом.
7. Как преодолеть вырожденность плана в задачах распределительного типа?
8. Какие требования предъявляются к размещению нуль-поставок в матрице задачи?
9. В чем заключается отличие термина «открытая модель задачи» от термина «недопустимый план»?
10. Как выполняется анализ плана на оптимальность при решении задач распределительным методом?
11. Какой порядок построения замкнутых контуров в задачах, решаемых распределительным методом. Какие формы могут приобретать контуры?
12. По какому признаку определяется, оптимален ли план: если задача решается на минимум (Zmin); и если – на максимум (Zmax)?
13. Какой порядок улучшения плана?
14. Как выполняется контроль правильности решения задачи распределительным методом?
15. В чем проявляется ограниченность распределительного метода с точки зрения его широкого применения для решения практических задач в землеустройстве?
