Материал: УП - Методы оптимальных решений

План реализации не менее 18000 руб. Сколько изделий каждого типа надо производить, чтобы их общее количество было максимальным?

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

Таблица 11

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

12. Для изготовления двух различных изделий А и B используются три вида сырья. В табл. 12 указаны нормы расхода сырья на производстве единицы изделия каждого вида, объем ресурсов, стоимость изделий.

Таблица 12

Составить план производства, максимизирующий общую стоимость продукции.

13. При подкормке посевов нужно на 1 га почвы химических веществ A, B, C, Д в количествах, не менее указанных в таблице. Совхоз закупает комбинированные удобрения двух видов. В табл. 13 указаны содержание химических веществ и цена единицы каждого вида удобрения.

Таблица 13

Составить план наиболее экономичной закупки удобрений.

14. Предприятие может работать по двум технологическим процессам, причем за единицу времени по первой технологии выпускает 260 изделий, по второй 300 изделий. В табл. 14 указаны затраты каждого ресурса в единицу времени.

Таблица 14

Найти программу максимального выпуска продукции из имеющихся ресурсов.

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

Таблица 15

Найти план выпуска продукции, максимизирующий прибыль.

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

Таблица 16

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

2. Графическое решение задачи линейного программирования

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

2.1. Свойства решений задач линейного программирования

Пусть на плоскости Ох₂ (рис. 1) заданы две точки: А₁ (х , х ) и А₂ (х , х ), определяющие _вектор . Найдем координаты произвольной точки А(х₁, х₂) данного вектора:

рассмотрим вектора ,

_{Так как , коллинеарны и одинаково направлены, то где 0  t } 1

_{Пусть 1 - t = 1, t = 2  и 1  0, 2  0, 1 + 2 =1.}

Рис. 1

Итак: если A = (х₁; х₂), A₁ = ( ; ), A₂ = ( ; ), то

A = ₁A₁ + ₂ A₂, ₁  0, ₂  0, ₁ + ₂ = 1. (4)

Точка А, для которой выполняются условия (4), называется выпук­лой линейной комбинацией точек А₁ и А₂. При х₁ = 1, х₂ = 0 точка А совпа­дает с точкой А₁; при х₁ = 0, х₂ = 1 – с концом A₂. Таким образом для любой внутренней точки А отрезка [А₁А₂] выполняются условия (4).

Точки А₁ и А₂ называются угловыми или крайними точками отрезка [А₁А₂]. Очевидно, что угловая точка не может быть представлена как вы­пуклая линейная комбинация двух других точек отрезка.

Соотношения верны и для n-мерного пространства:

_{Ā = λ1Ā1, + λ2Ā2 + ... + λnĀn, при λ1  0, .}

Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит и их произвольную выпуклую линейную комбинацию. Геометрический смысл этого определения состоит в том, что множеству вместе с его двумя любыми точками полностью принадлежит и весь отрезок, их соединяющий. Примерами выпуклых множеств явля­ется: отрезок, прямая, полуплоскость, круг, шар, куб, пирамида, полупространство и т. д. Пример не выпуклого множества показан на рис. 2., т. к. [А₁ А₂] полностью этому множеству не принадлежит.

Рис. 2

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

Замкнутым называется множество, содержащее все свои граничные точки. Замкнутое множество может быть ограниченным и неограниченным.

Угловой точкой выпуклого множества называется точка, которая принадлежит этому множеству, но не является внутренней ни для какого отрезка, целиком лежащего в заданном множестве. Например, у много­угольника угловыми точками являются его вершины, у круга – точки ок­ружности, которая его ограничивает. Таким образом, выпуклое множе­ство может иметь конечное и бесконечное число угловых точек.

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

Теорема 1

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